Difference between revisions of "2017 USAMO Problems/Problem 1"
Vihaankasam (talk | contribs) m (→Solution 1) |
Supermath123 (talk | contribs) (→Solution 2) |
||
Line 41: | Line 41: | ||
Since <math>a+b=4n</math>, all such pairs work, and we are done. | Since <math>a+b=4n</math>, all such pairs work, and we are done. | ||
+ | |||
+ | == Solution 3 == | ||
+ | |||
+ | Let <math>x</math> be odd where <math>x>1</math>. We have <math>x^2-1=(x-1)(x+1),</math> so <math>x^2-1 \equiv 0 \pmod{2x+2}.</math> This means that <math>x^{x+2}-x^x \equiv 0 \pmod{2x+2},</math> and since x is odd, <math>x^{x+2}+(-x)^x \equiv 0 \pmod{2x+2},</math> or <math>x^{x+2}+(x+2)^x \equiv 0 \pmod{2x+2},</math> as desired. | ||
==See Also== | ==See Also== | ||
{{USAMO newbox|year= 2017 |before=[[2016 USAMO]]|after=[[2018 USAMO]]}} | {{USAMO newbox|year= 2017 |before=[[2016 USAMO]]|after=[[2018 USAMO]]}} |
Revision as of 10:42, 27 June 2019
Problem
Prove that there are infinitely many distinct pairs of relatively prime positive integers and such that is divisible by .
Solution 1
Let . Since , we know . We can rewrite the condition as
Assume is odd. Since we need to prove an infinite number of pairs exist, it suffices to show that infinitely many pairs with odd exist.
Then we have
We know by Euler's theorem that , so if we will have the required condition.
This means . Let where is a prime, . Then , so Note the condition that guarantees that is odd, since
This makes . Now we need to show that and are relatively prime. We see that By the Euclidean Algorithm.
Therefore, for all primes , the pair satisfies the criteria, so infinitely many such pairs exist.
Solution 2
Take . It is obvious (use the Euclidean Algorithm, if you like), that , and that .
Note that
So
Since , all such pairs work, and we are done.
Solution 3
Let be odd where . We have so This means that and since x is odd, or as desired.
See Also
2017 USAMO (Problems • Resources) | ||
Preceded by 2016 USAMO |
Followed by 2018 USAMO | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |