Pequliar Primes

The primes p , q , r p,q,r satisfy :

p q r 1 p|qr-1

q p r 1 q|pr-1

r p q 1 r|pq-1

Find the sum of all possible p q r pqr


The answer is 30.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Bogdan Simeonov
May 28, 2014

Firstly, it is obvious that no two of these primes are equal.Also,

( p q 1 ) ( p r 1 ) ( q r 1 ) p r + p q + q r 1 0 ( m o d p q r ) (pq-1)(pr-1)(qr-1) \equiv pr+pq+qr-1\equiv 0\pmod{pqr}

We can write that as

p q r ( 1 q + 1 r + 1 p ) 1 0 ( m o d p q r ) pqr(\frac{1}{q}+\frac{1}{r}+\frac{1}{p})-1\equiv0\pmod{pqr}

Hence 1 q + 1 r + 1 p > 1 \frac{1}{q}+\frac{1}{r}+\frac{1}{p}>1

But it is easily seen that the only prime numbers satisfying the inequality are 2,3 and 5, because 1 2 + 1 3 + 1 7 < 1 \frac{1}{2}+\frac{1}{3}+\frac{1}{7}<1

If we check, that triple satisfies the divisibility condition, so the only possible product is 30 \boxed{30}

Brilliant solution! This problem is pretty famous, but this is the first time I've seen that solution.

Daniel Liu - 7 years ago

Log in to reply

I've never seen it before , actually I found it on a past BMO2 paper and this is the first thing that came to my mind.How else can it be solved?

Bogdan Simeonov - 7 years ago
The Dark Lord
Feb 23, 2018

WLOG let us assume p > q > r p > q > r .Since if p = q = r p=q=r then p p 2 1 p \nmid p^2-1 and likewise.Thus the equal to sign is removed.

p q r 1 ; q p r 1 ; r p q 1 p \mid qr -1; q \mid pr-1 ; r \mid pq-1

p q r ( p q 1 ) ( q r 1 ) ( p r 1 ) \implies pqr \mid (pq-1)(qr -1)(pr-1)

p q r ( p q + q r + p r 1 ) + p q r ( p q r ( p + q + r ) ) \implies pqr \mid (pq+qr+pr-1)+pqr(pqr-(p+q+r)) if we expand.Notice that p q r pqr is already a factor of one of the terms.Hence

p q r ( p q + q r + p r 1 ) p q r p q + q r + p r 1 p q r < p q + q r + p r 1 p + 1 q + 1 r > 1 \implies pqr \mid (pq+qr+pr-1) \implies pqr \leq pq+qr+pr-1 \implies pqr < pq+qr+pr \implies \dfrac{1}{p} + \dfrac{1}{q} + \dfrac{1}{r} > 1

Suppose now that r 3 r \geq 3 this means q 5 q \geq 5 and p 7 p \geq 7 .Thus 1 p + 1 q + 1 r 71 105 < 1 \dfrac{1}{p} + \dfrac{1}{q} + \dfrac{1}{r} \leq \dfrac{71}{105} < 1 a contradiction.

This forces r = 2 r = 2 .Now suppose q 5 q \geq 5 thus p 7 p \geq 7 but this renders 1 p + 1 q + 1 2 59 70 < 1 \dfrac{1}{p} + \dfrac{1}{q} + \dfrac{1}{2} \leq \dfrac{59}{70} < 1 again a contradiction.

Thus the only solution is p = 5 ; q = 3 ; r = 2 \boxed{p = 5 ;q = 3; r = 2} and its cyclic permutations.

What did you do in the last few steps? How do you know 1 p + 1 q + 1 r 71 105 < 1 \dfrac{1}{p} + \dfrac{1}{q} + \dfrac{1}{r} \leq \dfrac{71}{105} < 1 and further 1 p + 1 q + 1 2 59 70 < 1 \dfrac{1}{p} + \dfrac{1}{q} + \dfrac{1}{2} \leq \dfrac{59}{70} < 1

Harry Potter - 3 years, 3 months ago

Log in to reply

@The Boy who Lived We try to show r = 2 is the only possible solution.To prove this we suppose p > 2 then contradict it.since r 3 r \geq 3 using my WLOG condition we deduce q 5 q \geq 5 and p 7 p \geq 7 It is so obvious that 1 / 3 + 1 / 5 + 1 / 7 i s 71 / 105 1/3 + 1/5 + 1/7 is 71/105 .However look at what i said before that. 1/p + 1/q + 1/r must be more than 1.Contradiction.

Similarly we try to show q = 3.

The Dark Lord - 3 years, 3 months ago

Log in to reply

yeah i actually understood it later.

Harry Potter - 3 years, 3 months ago

Log in to reply

@Harry Potter Here is a problem for u i did it just now (without observing damn patterns)

find all n such that 2^n + 12^n + 2011^n is a perfect square.dont copy from net plz i am thinking of posting it.

The Dark Lord - 3 years, 3 months ago

Log in to reply

@The Dark Lord I have already tried it. I wasn't able to solve it.

Harry Potter - 3 years, 3 months ago

Log in to reply

@Harry Potter Incase you want to see the solution : U might want to see USAJMO 2011 P-1.It has 2 solutions.Glad to say My solution matches with the second solution.

The Dark Lord - 3 years, 3 months ago

Log in to reply

@The Dark Lord Aren't you preparing for the science examination.

Harry Potter - 3 years, 3 months ago

Log in to reply

@Harry Potter F**k that exam.Anyways bye I am going to a chit party now...(u know housie party...hopefully i will win something.Wish me luck.)

The Dark Lord - 3 years, 3 months ago

Log in to reply

@The Dark Lord What ??? Housie.......... during exams???

Harry Potter - 3 years, 3 months ago

Log in to reply

@Harry Potter Yea I am very versatile I guess.So is my mom. Anyways Bye gotta grab some.good food.

The Dark Lord - 3 years, 3 months ago

Log in to reply

@The Dark Lord Try my new problem that I just posted. and rate its title

Harry Potter - 3 years, 3 months ago

@The Dark Lord Try the problem https://brilliant.org/problems/the-fear-of-lord-voldemort-the-dark-lord/?ref_id=1470720 by me. try it.

Harry Potter - 3 years, 3 months ago

Log in to reply

@Harry Potter Ok sure doing it now.

The Dark Lord - 3 years, 3 months ago

Log in to reply

@The Dark Lord How's the title. and congrats for solving it very quickly so post a solution

Harry Potter - 3 years, 3 months ago

Log in to reply

@Harry Potter Satisfactory...Hey have u tried the RMO 1990 prob posted by me ?? I do hope u have a non bashy solution to it cuz my bashy solution sucks

The Dark Lord - 3 years, 3 months ago

Log in to reply

@The Dark Lord I didn't find any such prob. send the link

Harry Potter - 3 years, 3 months ago

Log in to reply

@Harry Potter Check my profile.

The Dark Lord - 3 years, 3 months ago

Log in to reply

@The Dark Lord yes got it i actuall tried it but was unable to solve can you give a hint.

Harry Potter - 3 years, 3 months ago

Log in to reply

@Harry Potter Try to expand it in base 10 then form a G.P. then use G.P sum formula then FLT. WARNING : This is my bashy tedious method...for non bashy way use divisibility test of 13.

The Dark Lord - 3 years, 3 months ago

Log in to reply

@The Dark Lord will try it after completing a chapter of bio. so bye.

Harry Potter - 3 years, 3 months ago

Log in to reply

@Harry Potter @The Boy who Lived my mom made me deactivate my account...Cuz of that Valentine thing.anyways so bye forever.

The Dark Lord - 3 years, 3 months ago

@Harry Potter And plz dont copy from net.

The Dark Lord - 3 years, 3 months ago

Log in to reply

@The Dark Lord – yes got it i actually tried it but was unable to solve can you give a hint.

Harry Potter - 3 years, 3 months ago

@The Dark Lord First, we prove that n n can't be even by noting that 2 2 k + 1 2 2 k + 201 1 2 k 2 ( m o d 3 ) 2^{2k}+12^{2k}+2011^{2k} \equiv 2 \pmod{3} , which is not a quadratic residue modulo 3 3 . Then, we prove that n n can't be odd and greater than 1 1 by noting that 2 2 k + 1 + 1 2 2 k + 1 + 201 1 2 k + 1 3 ( m o d 4 ) 2^{2k+1}+12^{2k+1}+2011^{2k+1} \equiv 3 \pmod{4} if k 1 k \geq 1 , which is not a quadratic residue. Then we note that n = 1 n=1 works since 2 + 12 + 2011 = 4 5 2 2+12+2011=45^2 and we're done.

Harry Potter - 3 years, 3 months ago

Log in to reply

@Harry Potter Gr8...well done to do it.within 2 minutes...Btw it took me 10 minutes to come up with that !!

The Dark Lord - 3 years, 3 months ago

Log in to reply

@The Dark Lord Thank you. But as I'm very honest, it is an AOPS solution.

Harry Potter - 3 years, 3 months ago

@The Dark Lord Is my solution correct?

Harry Potter - 3 years, 3 months ago

Log in to reply

@Harry Potter Uh sorry...U sure u havent copied it from AoPS Sungato Math adventures ?

The Dark Lord - 3 years, 3 months ago

Well i think that you have accelerated your skills in no. theory.

Harry Potter - 3 years, 3 months ago

Log in to reply

@Harry Potter Not really I just bought a good book Elementary Number Theory David Burton doing it now...Its really good clears all concepts.So I have a lot left to go.

As Robert Frost says : I have miles to go before I sleep.

The Dark Lord - 3 years, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...