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 USAJMO Problems/Problem 1"

m (→‎Solution 1)
(→‎Solution 6 (Motivation for Solution))
 
(31 intermediate revisions by 9 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
  
−
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 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==
 
==Solution 1==
−
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 = 2n-1</math> and <math>b = 2n+1</math>. We see that <math>(2n \pm 1)^2 = 4n^2\pm4n+1 \equiv 1 \pmod{4n}</math>. Therefore, we have <math>(2n+1)^{2n-1} + (2n-1)^{2n+1} \equiv 2n + 1 + 2n - 1  = 4n \equiv 0 \pmod{4n}</math>, as desired.  
  
−
---------------------------
+
(Credits to mathmaster2012)
−
Lemma: <math>(2^k + 1)^{-1} \equiv 2^k + 1 \pmod{2^{k+1}}</math>.
 
  
−
Since every number has a unique modular inverse, the lemma is equivalent to proving that <math>(2^k+1)^2 \equiv 1 \pmod{2^{k+1}}</math>. Expanding, we have the result.  
+
==Solution 2==
 +
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 3==
 +
Because problems such as this usually are related to expressions along the lines of <math>x\pm1</math>, it's tempting to try these. After a few cases, we see that <math>\left(a,b\right)=\left(2x-1,2x+1\right)</math> is convenient due to the repeated occurrence of <math>4x</math> when squared and added. We rewrite the given expressions as: <cmath>\left(2x-1\right)^{2x+1}+\left(2x+1\right)^{2x-1}, \left(2x-1\right)+\left(2x+1\right)=4x.</cmath> After repeatedly factoring the initial equation,we can get: <cmath>\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).</cmath> Expanding each of the squares, we can compute each product independently then sum them: <cmath>\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},</cmath> <cmath>\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}.</cmath> Now we place the values back into the expression: <cmath>\left(2x-1\right)^{2x+1}+\left(2x+1\right)^{2x-1}\equiv\left(2x-1\right)+\left(2x+1\right)\equiv0\mod{4x}.</cmath> Plugging any positive integer value for <math>x</math> into <math>\left(a,b\right)=\left(2x-1,2x+1\right)</math> yields a valid solution, because there is an infinite number of positive integers, there is an infinite number of distinct pairs <math>\left(a,b\right)</math>. <math>\square</math>
 +
 
 +
-fatant
 +
 
 +
==Solution 4==
 +
Let <math>a = 2x + 1</math> and <math>b = 2x-1</math>, where <math>x</math> leaves a remainder of <math>1</math> when divided by <math>4</math>.We seek to show that <math>(2x+1)^{2x-1} + (2x-1)^{2x+1} \equiv 0 \mod 4x</math> because that will show 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>.
 +
 
 +
Claim 1: <math>(2x+1)^{2x-1} + (2x-1)^{2x+1} \equiv 0 \mod 4</math>.
 +
We have that the remainder when <math>2x+1</math> is divided by <math>4</math> is <math>3</math> and the remainder when <math>2x-1</math> is divided by <math>4</math> is always <math>1</math>. Therefore, the remainder when <math>(2x+1)^{2x-1} + (2x-1)^{2x+1}</math> is divided by <math>4</math> is always going to be <math>(-1)^{2x-1} + 1^{2x+1} = 0</math>.
 +
 
 +
Claim 2: <math>(2x+1)^{2x-1} + (2x-1)^{2x+1} \equiv 0 \mod x</math>
 +
We know that <math>(2x+1) \mod x \equiv 1</math> and <math>(2x-1) \mod x \equiv 3</math>, so the remainder when <math>(2x+1)^{2x-1} + (2x-1)^{2x+1}</math> is divided by <math>4</math> is always going to be <math>(-1)^{2x-1} + 1^{2x+1} = 0</math>.
  
−
----------------------------
+
Claim 3: <math>(2x+1)^{2x-1} + (2x-1)^{2x+1} \equiv 0 \mod 4x</math>
 +
Trivial given claim <math>1,2</math>. <math>\boxed{}</math>
 +
 
 +
~AopsUser101
 +
 
 +
==Solution 5==
 +
I claim <math>(a,b) = (2n-1,2n+1)</math>,  <math>n (\in \mathbb{N}) \geq 2</math> 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 <math>(a,b)</math>.
 +
 
 +
We only need to prove:
 +
 
 +
<math>a^b+b^a \equiv 0 \pmod{a+b}</math>
 +
 
 +
We can expand <math>a^b + b^a = (2n-1)^{2n+1} + (2n+1)^{2n-1}</math> using binomial theorem. However, since <math>a + b = 2n-1 + 2n+1 = 4n</math>, all the <math>2n</math> terms (with more than 2 powers of) when evaluated modulo <math>4n</math> equal to 0, and thus can be omitted. We are left with the terms: <math>(2n+1)(2n)^1-1+(2n-1)(2n)^1+1 = 4n \cdot 2n</math>, which is divisible by <math>4n</math>.
 +
 
 +
<math>(2n-1)^{2n+1} + (2n+1)^{2n-1} \equiv (2n+1)(2n)-1+(2n-1)(2n)+1 = 4n \cdot 2n \equiv 0 \pmod{4n}</math>
 +
 
 +
The proof is complete. <math>\blacksquare</math>
 +
 
 +
-AlexLikeMath
 +
 
 +
==Solution 6 (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>
 +
<cmath></cmath>
 +
~BS2012
  
−
Substituting for <math>a</math> and <math>b</math>, we have
 
−
<cmath>(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}},</cmath>
 
−
where we use our lemma and the Euler totient theorem: <math>a^{\phi{n}} \equiv 1 \pmod{n}</math> when <math>a</math> and <math>n</math> are relatively prime.
 
  
−
==Solution 2==
 
−
Let <math>x</math> be any odd number above 1
 
 
{{MAA Notice}}
 
{{MAA Notice}}
  
 
==See also==
 
==See also==
 
{{USAJMO newbox|year=2017|beforetext=|before=First Problem|num-a=2}}
 
{{USAJMO newbox|year=2017|beforetext=|before=First Problem|num-a=2}}

Latest revision as of 16:26, 4 June 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 $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. $\blacksquare$

-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. AMC logo.png

See also

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