2017 USAMO Problems/Problem 1

Problem

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

Solution 1

Let $n=a+b$ . Since $gcd(a,b)=1$ , we know $gcd(a,n)=1$ . We can rewrite the condition as

$a^{n-a}+(n-a)^a \equiv 0 \mod{n}$ $a^{n-a}\equiv-(-a)^a \mod{n}$ Assume $a$ is odd. Since we need to prove an infinite number of pairs exist, it suffices to show that infinitely many pairs with $a$ odd exist.

Then we have $a^{n-a}\equiv a^a \mod{n}$ $1 \equiv a^{2a-n} \mod{n}$

We know by Euler's theorem that $a^{\varphi(n)} \equiv 1 \mod{n}$ , so if $2a-n=\varphi(n)$ we will have the required condition.

This means $a=\frac{n+\varphi(n)}{2}$ . Let $n=2p$ where $p$ is a prime, $p\equiv 1\mod{4}$ . Then $\varphi(n) = 2p*\left(1-\frac{1}{2}\right)\left(1-\frac{1}{p}\right) = p-1$ , so $a = \frac{2p+p-1}{2} = \frac{3p-1}{2}$ Note the condition that $p\equiv 1\mod{4}$ guarantees that $a$ is odd, since $3p-1 \equiv 2\mod{4}$

This makes $b = \frac{p+1}{2}$ . Now we need to show that $a$ and $b$ are relatively prime. We see that $gcd\left(\frac{3p-1}{2},\frac{p+1}2\right)=\frac{gcd(3p-1,p+1)}{2}$ $=\frac{gcd(p-3,4)}{2}=\frac22=1$ By the Euclidean Algorithm.

Therefore, for all primes $p \equiv 1\mod{4}$ , the pair $\left(\frac{3p-1}{2},\frac{p+1}{2}\right)$ satisfies the criteria, so infinitely many such pairs exist.

Solution 2

Take $a=2n-1, b=2n+1, n\geq 2$ . It is obvious (use the Euclidean Algorithm, if you like), that $\gcd(a,b)=1$ , and that $a,b>1$ .

Note that

$a^2 = 4n^2-4n+1 \equiv 1 \pmod{4n}$

$b^2 = 4n^2+4n+1 \equiv 1 \pmod{4n}$

So

$a^b+b^a = a(a^2)^n+b(b^2)^{n-1} \equiv$ $a\cdot 1^n + b\cdot 1^{n-1} \equiv a+b = 4n \equiv 0 \pmod{4n}$

Since $a+b=4n$ , all such pairs work, and we are done.

Solution 3

Consider when $a\equiv b \equiv 2 \pmod{2}$ . Then,

$a^b + b^a \equiv (-b)^b + b^a \equiv b^a + b^b \pmod{a+b}$ .

But also note that

$a^b + b^a \equiv a^b + (-a)^a \equiv a^a + a^b \pmod{a+b}$ .

Combining these two results,

$a^b + b^a \equiv \frac{1}{2} \left( (a^a + b^a) + (a^b + b^b) \right) \pmod{a+b}$ .

Now for $p=2$ , observe that $a^a, b^a, a^b, b^b \in \mathbb{Z}^2$ , so they are all divisible by 4. Even after the $\frac12$ factor in the above expression for $a^b + b^a$ , $v_2 (a^b + b^a) \ge 1$ and we are done. $\blacksquare$

~IbrahimNadeem

Solution 4

Let $x$ be odd where $x>1$ . We have $x^2-1=(x-1)(x+1),$ so $x^2-1 \equiv 0 \pmod{2x+2}.$ This means that $x^{x+2}-x^x \equiv 0 \pmod{2x+2},$ and since x is odd, $x^{x+2}+(-x)^x \equiv 0 \pmod{2x+2},$ or $x^{x+2}+(x+2)^x \equiv 0 \pmod{2x+2},$ as desired.

Solution 5

I claim that the ordered pair $(2^{n} - 1, 2^{n} + 1)$ satisfies the criteria for all $n \geq 2.$ Proof: It is easy to see that the order modulo $2^{n+1}$ of $(2^{n} - 1)^k$ is $2,$ since $(2^{n} - 1)^2 = 2^{2n} - 2 \cdot 2^{n} + 1 \equiv 1 \mod 2^{n+1}.$ , and we can assert and prove similarly for the order modulo $2^{n+1}$ of $(2^{n} + 1)^k.$ Thus, the remainders modulo $2^{n+1}$ that the sequences of powers of $2^{n} - 1$ and $2^{n} + 1$ generate are $1$ for even powers and $2^{n} - 1$ and $2^{n} + 1$ for odd powers, respectively. Since $2^{n} + 1$ and $2^{n} - 1$ are both odd for $n \geq 2,$ $(2^n + 1)^{2^n - 1} + (2^n - 1)^{2^n + 1} \equiv 0 \mod 2^{n+1}.$ Since there are infinitely many powers of $2$ and since all ordered pairs $(2^n - 1, 2^n+1)$ contain relatively prime integers, we are done. $\boxed{}$

-fidgetboss_4000

Solution 6 (Motivation for Solution)

Note that $a^b+b^a=a^b-a^a+a^a+b^a.$ To get rid of the $a^a+b^a$ part $\pmod{a+b},$ we can use the sum of powers factorization. However, $a$ must be odd for us to do this. If we assume that $a$ is odd, $a^b-a^a+a^a+b^a\equiv a^b-a^a+(a+b)(\text{an integer})\equiv a^b-a^a \equiv a^a\left(a^{b-a}-1\right)\pmod{a+b}.$ Because $a$ and $b$ are relatively prime, $a+b$ cannot divide $a^a.$ Thus, we have to show that there exists an integer $b$ such that for odd $a,$ $a^{b-a}\equiv 1 \pmod{a+b}.$ Suppose that $a=2n-1.$ To keep the powers small, we try $b=2n+k$ for small values of $k.$ We can find that $b=2n$ does not work. $b=2n+1$ works though, as $a+b=4n$ and $(2n-1)^{2n+1-2n+1}\equiv (2n-1)^2\equiv 4n^2-4n+1\equiv 4n(n-1)+1 \equiv 1 \pmod{4n}.$ Because $a$ is odd, $b=a+2$ is relatively prime to $a.$ Thus, $(a,b)=(2n-1,2n+1)$ is a solution for positive $n\ge 2.$ There are infinitely many possible values for $n,$ so the proof is complete. $\blacksquare$

~BS2012

2017 USAMO (Problems • Resources)
Preceded by First Problem	Followed by Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search