The primes p , q , r satisfy :
p ∣ q r − 1
q ∣ p r − 1
r ∣ p q − 1
Find the sum of all possible p q r
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.
Brilliant solution! This problem is pretty famous, but this is the first time I've seen that solution.
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?
WLOG let us assume p > q > r .Since if p = q = r then p ∤ 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 q r ∣ ( p q − 1 ) ( q r − 1 ) ( p r − 1 )
⟹ p q r ∣ ( p q + q r + p r − 1 ) + p q r ( p q r − ( p + q + r ) ) if we expand.Notice that p q r 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 ⟹ p 1 + q 1 + r 1 > 1
Suppose now that r ≥ 3 this means q ≥ 5 and p ≥ 7 .Thus p 1 + q 1 + r 1 ≤ 1 0 5 7 1 < 1 a contradiction.
This forces r = 2 .Now suppose q ≥ 5 thus p ≥ 7 but this renders p 1 + q 1 + 2 1 ≤ 7 0 5 9 < 1 again a contradiction.
Thus the only solution is p = 5 ; q = 3 ; r = 2 and its cyclic permutations.
What did you do in the last few steps? How do you know p 1 + q 1 + r 1 ≤ 1 0 5 7 1 < 1 and further p 1 + q 1 + 2 1 ≤ 7 0 5 9 < 1
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 using my WLOG condition we deduce q ≥ 5 and p ≥ 7 It is so obvious that 1 / 3 + 1 / 5 + 1 / 7 i s 7 1 / 1 0 5 .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.
Log in to reply
yeah i actually understood it later.
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.
Log in to reply
@The Dark Lord – I have already tried it. I wasn't able to solve it.
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.
Log in to reply
@The Dark Lord – Aren't you preparing for the science examination.
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.)
Log in to reply
@The Dark Lord – What ??? Housie.......... during exams???
Log in to reply
@Harry Potter – Yea I am very versatile I guess.So is my mom. Anyways Bye gotta grab some.good food.
Log in to reply
@The Dark Lord – Try my new problem that I just posted. and rate its title
@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.
Log in to reply
@Harry Potter – Ok sure doing it now.
Log in to reply
@The Dark Lord – How's the title. and congrats for solving it very quickly so post a solution
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
Log in to reply
@The Dark Lord – I didn't find any such prob. send the link
Log in to reply
@Harry Potter – Check my profile.
Log in to reply
@The Dark Lord – yes got it i actuall tried it but was unable to solve can you give a hint.
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.
Log in to reply
@The Dark Lord – will try it after completing a chapter of bio. so bye.
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.
@Harry Potter – And plz dont copy from net.
Log in to reply
@The Dark Lord – – yes got it i actually tried it but was unable to solve can you give a hint.
@The Dark Lord – First, we prove that n can't be even by noting that 2 2 k + 1 2 2 k + 2 0 1 1 2 k ≡ 2 ( m o d 3 ) , which is not a quadratic residue modulo 3 . Then, we prove that n can't be odd and greater than 1 by noting that 2 2 k + 1 + 1 2 2 k + 1 + 2 0 1 1 2 k + 1 ≡ 3 ( m o d 4 ) if k ≥ 1 , which is not a quadratic residue. Then we note that n = 1 works since 2 + 1 2 + 2 0 1 1 = 4 5 2 and we're done.
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 !!
Log in to reply
@The Dark Lord – Thank you. But as I'm very honest, it is an AOPS solution.
@The Dark Lord – Is my solution correct?
Log in to reply
@Harry Potter – Uh sorry...U sure u havent copied it from AoPS Sungato Math adventures ?
Well i think that you have accelerated your skills in no. theory.
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.
Problem Loading...
Note Loading...
Set Loading...
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 )
We can write that as
p q r ( q 1 + r 1 + p 1 ) − 1 ≡ 0 ( m o d p q r )
Hence q 1 + r 1 + p 1 > 1
But it is easily seen that the only prime numbers satisfying the inequality are 2,3 and 5, because 2 1 + 3 1 + 7 1 < 1
If we check, that triple satisfies the divisibility condition, so the only possible product is 3 0