2017 USAJMO Problems/Problem 1

Revision as of 19:12, 19 April 2017 by Thedoge (talk | contribs) (Solution)


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


Let $a = 2^n - 1$ and $b = 2^n + 1$. We see that $a$ and $b$ are relatively prime (they are consecutive positive odd integers).

Lemma: $(2^k + 1)^{-1} \equiv 2^k + 1 \pmod{2^{k+1}}$.

Since every number has a unique modular inverse, the lemma is equivalent to proving that $(2^k+1)^2 \equiv 1 \pmod{2^{k+1}}$. Expanding, we have the result.

Substituting for $a$ and $b$, 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}},\] where we use our lemma and the Euler totient theorem: $a^\phi{n} \equiv 1 \pmod{n}$ when $a$ and $n$ are relatively prime.

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

See also

2017 USAJMO (ProblemsResources)
First Problem Followed by
Problem 2
1 2 3 4 5 6
All USAJMO Problems and Solutions