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

(Solution)
m (Solution)
Line 3: Line 3:
 
Prove that there are infinitely many distinct pairs <math>(a,b)</math> of relatively prime integers <math>a>1</math> and <math>b>1</math> such that <math>a^b+b^a</math> is divisible by <math>a+b</math>.
 
Prove that there are infinitely many distinct pairs <math>(a,b)</math> of relatively prime integers <math>a>1</math> and <math>b>1</math> such that <math>a^b+b^a</math> is divisible by <math>a+b</math>.
  
==Solution==
+
==Solution1==
 
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).  
  

Revision as of 19:26, 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$.

Solution1

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.

These problems are copyrighted © by the Mathematical Association of America, as part of the 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