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"

(Added problem)
 
m (→‎Solution 4)
 
(13 intermediate revisions by 11 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
  
−
Prove that there are infinitely many distinct pairs <math>(a,b)</math> of relatively prime positive integers a>1 and b>1 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 1 ==
 +
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. We see that
 +
<cmath>gcd\left(\frac{3p-1}{2},\frac{p+1}2\right)=\frac{gcd(3p-1,p+1)}{2}</cmath>
 +
<cmath>=\frac{gcd(p-3,4)}{2}=\frac22=1</cmath>
 +
By the Euclidean Algorithm.
 +
 
 +
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.
 +
 
 +
== Solution 2 ==
 +
 
 +
Take <math>a=2n-1, b=2n+1, n\geq 2</math>. It is obvious (use the Euclidean Algorithm, if you like), that <math>\gcd(a,b)=1</math>, and that <math>a,b>1</math>.
 +
 
 +
Note that
 +
 
 +
<cmath>a^2 = 4n^2-4n+1 \equiv 1 \pmod{4n}</cmath>
 +
 
 +
<cmath>b^2 = 4n^2+4n+1 \equiv 1 \pmod{4n}</cmath>
 +
 
 +
So
 +
 
 +
<cmath>a^b+b^a = a(a^2)^n+b(b^2)^{n-1} \equiv </cmath> <cmath>a\cdot 1^n + b\cdot 1^{n-1} \equiv a+b = 4n \equiv 0 \pmod{4n}</cmath>
 +
 
 +
Since <math>a+b=4n</math>, all such pairs work, and we are done.
 +
 
 +
== Solution 3 ==
 +
 
 +
Let <math>x</math> be odd where <math>x>1</math>. We have <math>x^2-1=(x-1)(x+1),</math> so <math>x^2-1 \equiv 0 \pmod{2x+2}.</math> This means that  <math>x^{x+2}-x^x \equiv 0 \pmod{2x+2},</math> and since x is odd, <math>x^{x+2}+(-x)^x \equiv 0 \pmod{2x+2},</math> or <math>x^{x+2}+(x+2)^x \equiv 0 \pmod{2x+2},</math> as desired.
 +
 
 +
==Solution 4==
 +
I claim that the ordered pair <math>(2^{n} - 1, 2^{n} + 1)</math> satisfies the criteria for all <math>n \geq 2.</math>
 +
Proof:
 +
It is easy to see that the order modulo <math>2^{n+1}</math> of <math>(2^{n} - 1)^k</math> is <math>2, </math> since <math>(2^{n} - 1)^2 = 2^{2n} - 2 \cdot 2^{n} + 1 \equiv 1 \mod 2^{n+1}. </math>, and we can assert and prove similarly for the order modulo <math>2^{n+1}</math> of <math>(2^{n} + 1)^k.</math> Thus, the remainders modulo <math>2^{n+1}</math> that the sequences of powers of <math>2^{n} - 1</math> and <math>2^{n} + 1</math> generate are <math>1</math> for even powers and <math>2^{n} - 1</math> and <math>2^{n} + 1</math> for odd powers, respectively. Since <math>2^{n} + 1</math> and <math>2^{n} - 1</math> are both odd for <math>n \geq 2, </math> <cmath>(2^n + 1)^{2^n - 1} + (2^n - 1)^{2^n + 1} \equiv 0 \mod 2^{n+1}. </cmath> Since there are infinitely many powers of <math>2</math> and since all ordered pairs <math>(2^n - 1, 2^n+1)</math> contain relatively prime integers, we are done.
 +
<math>\boxed{}</math>
 +
 
 +
-fidgetboss_4000
 +
 
 +
==Solution 5 (Motivation for Solution)==
 +
Note that <cmath>a^b+b^a=a^b-a^a+a^a+b^a.</cmath> To get rid of the <math>a^a+b^a</math> part <math>\pmod{a+b},</math> we can use the sum of powers factorization. However, <math>a</math> must be odd for us to do this. If we assume that <math>a</math> is odd,
 +
<cmath>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}.</cmath>
 +
Because <math>a</math> and <math>b</math> are relatively prime, <math>a+b</math> cannot divide <math>a^a.</math> Thus, we have to show that there exists an integer <math>b</math> such that for odd <math>a,</math>
 +
<cmath>a^{b-a}\equiv 1 \pmod{a+b}.</cmath>
 +
Suppose that <math>a=2n-1.</math> To keep the powers small, we try <math>b=2n+k</math> for small values of <math>k.</math> We can find that <math>b=2n</math> does not work. <math>b=2n+1</math> works though, as <math>a+b=4n</math> and
 +
<cmath>(2n-1)^{2n+1-2n+1}\equiv (2n-1)^2\equiv 4n^2-4n+1\equiv 4n(n-1)+1 \equiv 1 \pmod{4n}.</cmath>
 +
Because <math>a</math> is odd, <math>b=a+2</math> is relatively prime to <math>a.</math> Thus, <cmath>(a,b)=(2n-1,2n+1)</cmath> is a solution for positive <math>n\ge 2.</math> There are infinitely many possible values for <math>n,</math> so the proof is complete. <math>\blacksquare</math>
 +
 
 +
~BS2012
 +
 
 +
==See Also==
 +
{{USAMO newbox|year= 2017|before=First Problem|num-a=2}}

Latest revision as of 09:51, 29 March 2024

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

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 4

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 5 (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

See Also

2017 USAMO (Problems • Resources)
Preceded by
First Problem 		Followed by
Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2017_USAMO_Problems/Problem_1&oldid=217563"