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

m (Solution 1)
(Solution 2)
Line 19: Line 19:
 
==Solution 2==
 
==Solution 2==
 
Let <math>x</math> be any odd number above 1
 
Let <math>x</math> be any odd number above 1
 +
 +
 
{{MAA Notice}}
 
{{MAA Notice}}
  
 
==See also==
 
==See also==
 
{{USAJMO newbox|year=2017|beforetext=|before=First Problem|num-a=2}}
 
{{USAJMO newbox|year=2017|beforetext=|before=First Problem|num-a=2}}

Revision as of 18:27, 19 April 2017

Problem

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$.

Solution 1

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.

Solution 2

Let $x$ be any odd number above 1


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