Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m (→‎Problem)
(→‎Problem)
Line 2: Line 2:
  
 
Prove that there are infinitely many distinct pairs <math>(a,b)</math> of relatively prime positive 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 positive 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 ==
 +
Let <math>n=a+b</math>. Since <math>gcd(a,b)=1</math>, we know <math>gcd(a,n)=1</math>. We can rewrite the condition as
 +
 +
<cmath>a^{n-a}+(n-a)^a \equiv 0 \mod{n}</cmath>
 +
<cmath>a^{n-a}\equiv-(-a)^a \mod{n}</cmath>
 +
Assume <math>a</math> is odd. Since we need to prove an infinite number of pairs exist, it suffices to show that infinitely many pairs with <math>a</math> odd exist.
 +
 +
Then we have
 +
<cmath>a^{n-a}\equiv a^a \mod{n}</cmath>
 +
<cmath>1 \equiv a^{2a-n} \mod{n}</cmath>
 +
 +
We know by Euler's theorem that <math>a^{\varphi(n)} \equiv 1 \mod{n}</math>, so if <math>2a-n=\varphi(n)</math> we will have the required condition.
 +
 +
This means <math>a=\frac{n+\varphi(n)}{2}</math>. Let <math>n=2p</math> where <math>p</math> is a prime, <math>p\equiv 1\mod{4}</math>. Then <math>\varphi(n) = 2p*\left(1-\frac{1}{2}\right)\left(1-\frac{1}{p}\right) = p-1</math>, so <cmath>a = \frac{2p+p-1}{2} = \frac{3p-1}{2}</cmath>
 +
Note the condition that <math>p\equiv 1\mod{4}</math> guarantees that <math>a</math> is odd, since <math>3p-1 \equiv 2\mod{4}</math>
 +
 +
This makes <math>b = \frac{p+1}{2}</math>. Now we need to show that <math>a</math> and <math>b</math> are relatively prime. If <math>a</math> and <math>b</math> have a common factor <math>k</math>, then we know <math>k|a+b=2p</math>. Therefore <math>k=1,2,p,</math> or <math>2p</math>. We know <math>b=\frac{p+1}{2}<p</math>, so <math>p \nmid b</math> and <math>2p\nmid b</math>. We also know <math>a</math> is odd, so <math>2\nmid a</math>. This means the only common factor <math>a</math> and <math>b</math> have is <math>1</math>, so <math>a</math> and <math>b</math> are relatively prime.
 +
 +
Therefore, for all primes <math>p \equiv 1\mod{4}</math>, the pair <math>\left(\frac{3p-1}{2},\frac{p+1}{2}\right)</math> satisfies the criteria, so infinitely many such pairs exist.

Revision as of 19:33, 20 April 2017

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

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. If $a$ and $b$ have a common factor $k$, then we know $k|a+b=2p$. Therefore $k=1,2,p,$ or $2p$. We know $b=\frac{p+1}{2}<p$, so $p \nmid b$ and $2p\nmid b$. We also know $a$ is odd, so $2\nmid a$. This means the only common factor $a$ and $b$ have is $1$, so $a$ and $b$ are relatively prime.

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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2017_USAMO_Problems/Problem_1&oldid=85331"