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

(Solution 2)
(Solution 1)
Line 4: Line 4:
  
 
==Solution 1==
 
==Solution 1==
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 = 2n-1</math> and <math>b = 2n+1</math>. We see that <math>(2n \pm 1)^2 = 4n^2-4n+1 \equiv 1 \pmod{4n}</math>. Therefore, we have <math>(2n+1)^{2n-1} + (2n-1)^{2n+1} \equiv 2n + 1 + 2n - 1  = 4n \equiv 0 \pmod{4n}</math>, as desired.  
  
---------------------------
+
(Credits to laegolas)
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.
 
  
 
==Solution 2==
 
==Solution 2==

Revision as of 18:32, 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 = 2n-1$ and $b = 2n+1$. We see that $(2n \pm 1)^2 = 4n^2-4n+1 \equiv 1 \pmod{4n}$. Therefore, we have $(2n+1)^{2n-1} + (2n-1)^{2n+1} \equiv 2n + 1 + 2n - 1  = 4n \equiv 0 \pmod{4n}$, as desired.

(Credits to laegolas)

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