2017 USAJMO 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 $a = 2n-1$ and $b = 2n+1$ . We see that $(2n \pm 1)^2 = 4n^2\pm4n+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 mathmaster2012)

Solution 2

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 3

Because problems such as this usually are related to expressions along the lines of $x\pm1$ , it's tempting to try these. After a few cases, we see that $\left(a,b\right)=\left(2x-1,2x+1\right)$ is convenient due to the repeated occurrence of $4x$ when squared and added. We rewrite the given expressions as: $\left(2x-1\right)^{2x+1}+\left(2x+1\right)^{2x-1}, \left(2x-1\right)+\left(2x+1\right)=4x.$ After repeatedly factoring the initial equation,we can get: $\left(2x-1\right)^{2}\left(2x-1\right)^{2}...\left(2x-1\right)+\left(2x+1\right)^{2}\left(2x+1\right)^{2}\left(2x+1\right)^{2}...\left(2x+1\right).$ Expanding each of the squares, we can compute each product independently then sum them: $\left(4x^{2}-4x+1\right)\left(4x^{2}-4x+1\right)...\left(2x-1\right)\equiv\left(1\right)\left(1\right)...\left(2x-1\right)\equiv2x-1\mod{4x},$ $\left(4x^{2}+4x+1\right)\left(4x^{2}+4x+1\right)...\left(2x+1\right)\equiv\left(1\right)\left(1\right)...\left(2x+1\right)\equiv2x+1\mod{4x}.$ Now we place the values back into the expression: $\left(2x-1\right)^{2x+1}+\left(2x+1\right)^{2x-1}\equiv\left(2x-1\right)+\left(2x+1\right)\equiv0\mod{4x}.$ Plugging any positive integer value for $x$ into $\left(a,b\right)=\left(2x-1,2x+1\right)$ yields a valid solution, because there is an infinite number of positive integers, there is an infinite number of distinct pairs $\left(a,b\right)$ . $\square$

-fatant

Solution 4

Let $a = 2x + 1$ and $b = 2x-1$ , where $x$ leaves a remainder of $1$ when divided by $4$ .We seek to show that $(2x+1)^{2x-1} + (2x-1)^{2x+1} \equiv 0 \mod 4x$ because that will show 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$ .

Claim 1: $(2x+1)^{2x-1} + (2x-1)^{2x+1} \equiv 0 \mod 4$ . We have that the remainder when $2x+1$ is divided by $4$ is $3$ and the remainder when $2x-1$ is divided by $4$ is always $1$ . Therefore, the remainder when $(2x+1)^{2x-1} + (2x-1)^{2x+1}$ is divided by $4$ is always going to be $(-1)^{2x-1} + 1^{2x+1} = 0$ .

Claim 2: $(2x+1)^{2x-1} + (2x-1)^{2x+1} \equiv 0 \mod x$ We know that $(2x+1) \mod x \equiv 1$ and $(2x-1) \mod x \equiv 3$ , so the remainder when $(2x+1)^{2x-1} + (2x-1)^{2x+1}$ is divided by $4$ is always going to be $(-1)^{2x-1} + 1^{2x+1} = 0$ .

Claim 3: $(2x+1)^{2x-1} + (2x-1)^{2x+1} \equiv 0 \mod 4x$ Trivial given claim $1,2$ . $\boxed{}$

~AopsUser101

Solution 5

I claim $(a,b) = (2n-1,2n+1)$ , $n (\in \mathbb{N}) \geq 2$ always satisfies above conditions.

Note: We could have also substituted 2n with 2^n or 4n, 8n, ... any sequence of numbers such that they are all even. The proof will work the same.

Proof:

Since there are infinitely many integers larger than or equal to 2, there are infinitely many distinct pairs $(a,b)$ .

We only need to prove:

$a^b+b^a \equiv 0 \pmod{a+b}$

We can expand $a^b + b^a = (2n-1)^{2n+1} + (2n+1)^{2n-1}$ using binomial theorem. However, since $a + b = 2n-1 + 2n+1 = 4n$ , all the $2n$ terms (with more than 2 powers of) when evaluated modulo $4n$ equal to 0, and thus can be omitted. We are left with the terms: $(2n+1)(2n)^1-1+(2n-1)(2n)^1+1 = 4n \cdot 2n$ , which is divisible by $4n$ .

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

The proof is complete.

-AlexLikeMath

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.

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

Page

Toolbox

Search