Difference between revisions of "2017 USAJMO Problems/Problem 1"
(→Problem) |
(→Solution) |
||
| Line 4: | Line 4: | ||
==Solution== | ==Solution== | ||
| + | Let <math>a = 2^n - 1</math> and <math>b = 2^n + 1</math>. We see that <math>a</math> and <math>b</math> are relatively prime (they are consecutive positive odd integers). | ||
| + | Lemma: <math>(2^k + 1)^{-1} \equiv 2^k + 1 \pmod{2^{k+1}}</math>. | ||
| + | |||
| + | Since every number has a unique modular inverse, the lemma is equivalent to proving that <math>(2^k+1)^2 \equiv 1 \pmod{2^{k+1}}</math>. Expanding, we have the result. | ||
| + | |||
| + | Substituting for <math>a</math> and <math>b</math>, we have | ||
| + | <cmath>(2^k+1)^{2^k-1} + (2^k-1)^{2^k+1} \equiv 2^k - 1 + 2^k + 1 \equiv 0 \pmod{2^{k+1}},</cmath> | ||
| + | where we use our lemma and the Euler totient theorem: <math>a^\phi{n} \equiv 1 \pmod{n}</math> when <math>a</math> and <math>n</math> are relatively prime. | ||
{{MAA Notice}} | {{MAA Notice}} | ||
Revision as of 19:11, 19 April 2017
Problem
Prove that there are infinitely many distinct pairs 
of relatively prime integers 
and 
such that 
is divisible by 
.
Solution
Let 
and 
. We see that 
and 
are relatively prime (they are consecutive positive odd integers).
Lemma: 
.
Since every number has a unique modular inverse, the lemma is equivalent to proving that 
. Expanding, we have the result.
Substituting for and , we have
![\[(2^k+1)^{2^k-1} + (2^k-1)^{2^k+1} \equiv 2^k - 1 + 2^k + 1 \equiv 0 \pmod{2^{k+1}},\]](http://latex.artofproblemsolving.com/5/5/7/5572c842a8d19ea1e35b514541c85bea6a906030.png)
where we use our lemma and the Euler totient theorem: 
when and 
are relatively prime.
These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. 
See also
| 2017 USAJMO (Problems • Resources) | ||
| First Problem | Followed by Problem 2 | |
| 1 • 2 • 3 • 4 • 5 • 6 | ||
| All USAJMO Problems and Solutions | ||
