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.

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