Difference between revisions of "2017 USAJMO Problems/Problem 1"
(→Solution 1) |
(→Solution 6 (Motivation for Solution)) |
||
(29 intermediate revisions by 8 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 = 2n-1</math> and <math>b = 2n+1</math>. We see that <math>(2n \pm 1)^2 = 4n^2 | + | 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 | + | (Credits to mathmaster2012) |
==Solution 2== | ==Solution 2== | ||
− | Let <math>x</math> be any | + | 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 | ||
Latest revision as of 16:26, 4 June 2024
Contents
[hide]Problem
Prove that there are infinitely many distinct pairs of relatively prime positive integers
and
such that
is divisible by
.
Solution 1
Let and
. We see that
. Therefore, we have
, as desired.
(Credits to mathmaster2012)
Solution 2
Let be odd where
. We have
so
This means that
and since x is odd,
or
as desired.
Solution 3
Because problems such as this usually are related to expressions along the lines of , it's tempting to try these. After a few cases, we see that
is convenient due to the repeated occurrence of
when squared and added. We rewrite the given expressions as:
After repeatedly factoring the initial equation,we can get:
Expanding each of the squares, we can compute each product independently then sum them:
Now we place the values back into the expression:
Plugging any positive integer value for
into
yields a valid solution, because there is an infinite number of positive integers, there is an infinite number of distinct pairs
.
-fatant
Solution 4
Let and
, where
leaves a remainder of
when divided by
.We seek to show that
because that will show that there are infinitely many distinct pairs
of relatively prime integers
and
such that
is divisible by
.
Claim 1: .
We have that the remainder when
is divided by
is
and the remainder when
is divided by
is always
. Therefore, the remainder when
is divided by
is always going to be
.
Claim 2:
We know that
and
, so the remainder when
is divided by
is always going to be
.
Claim 3:
Trivial given claim
.
~AopsUser101
Solution 5
I claim ,
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 .
We only need to prove:
We can expand using binomial theorem. However, since
, all the
terms (with more than 2 powers of) when evaluated modulo
equal to 0, and thus can be omitted. We are left with the terms:
, which is divisible by
.
The proof is complete.![]()
-AlexLikeMath
Solution 6 (Motivation for Solution)
Note that To get rid of the
part
we can use the sum of powers factorization. However,
must be odd for us to do this. If we assume that
is odd,
Because
and
are relatively prime,
cannot divide
Thus, we have to show that there exists an integer
such that for odd
Suppose that
To keep the powers small, we try
for small values of
We can find that
does not work.
works though, as
and
Because
is odd,
is relatively prime to
Thus,
is a solution for positive
There are infinitely many possible values for
so the proof is complete.
~BS2012
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.
See also
2017 USAJMO (Problems • Resources) | ||
First Problem | Followed by Problem 2 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |