Difference between revisions of "2017 USAJMO Problems/Problem 2"

Revision as of 18:11, 19 April 2017

Problem:

Prove that there are infinitely many distinct pairs $(a,b)$ of relatively prime positive integers $a > 1$ and $b > 1$ such that $a^b + b^a$ is divisible by $a + b$ .

Solution

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.

@@ Line 3: / Line 3: @@
 ==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}}

2017 USAJMO (Problems • Resources)
Preceded by Problem 1	Followed by Problem 3
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

Page

Toolbox

Search

Difference between revisions of "2017 USAJMO Problems/Problem 2"

Revision as of 18:11, 19 April 2017

Problem:

Solution

See also