Difference between revisions of "2017 USAJMO Problems/Problem 1"
(→Solution) |
(→Solution) |
||
Line 6: | Line 6: | ||
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). | 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>. | 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. | 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 | Substituting for <math>a</math> and <math>b</math>, we have |
Revision as of 19:12, 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 where we use our lemma and the Euler totient theorem: when and are relatively prime.
The problems on this page are copyrighted by the Mathematical Association of America's 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 |