Difference between revisions of "2017 USAMO Problems/Problem 1"
m (→Solution 4) |
|||
(2 intermediate revisions by 2 users not shown) | |||
Line 32: | Line 32: | ||
Note that | Note that | ||
− | <cmath>a^2 = 4n^2-4n+1 \equiv 1 | + | <cmath>a^2 = 4n^2-4n+1 \equiv 1 \pmod{4n}</cmath> |
− | <cmath>b^2 = 4n^2+4n+1 \equiv 1 | + | <cmath>b^2 = 4n^2+4n+1 \equiv 1 \pmod{4n}</cmath> |
So | 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 | + | <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. | Since <math>a+b=4n</math>, all such pairs work, and we are done. | ||
− | |||
== Solution 3 == | == 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. | 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== | ==See Also== | ||
{{USAMO newbox|year= 2017|before=First Problem|num-a=2}} | {{USAMO newbox|year= 2017|before=First Problem|num-a=2}} |
Latest revision as of 10:51, 29 March 2024
Contents
Problem
Prove that there are infinitely many distinct pairs of relatively prime positive integers
and
such that
is divisible by
.
Solution 1
Let . Since
, we know
. We can rewrite the condition as
Assume
is odd. Since we need to prove an infinite number of pairs exist, it suffices to show that infinitely many pairs with
odd exist.
Then we have
We know by Euler's theorem that , so if
we will have the required condition.
This means . Let
where
is a prime,
. Then
, so
Note the condition that
guarantees that
is odd, since
This makes . Now we need to show that
and
are relatively prime. We see that
By the Euclidean Algorithm.
Therefore, for all primes , the pair
satisfies the criteria, so infinitely many such pairs exist.
Solution 2
Take . It is obvious (use the Euclidean Algorithm, if you like), that
, and that
.
Note that
So
Since , all such pairs work, and we are done.
Solution 3
Let be odd where
. We have
so
This means that
and since x is odd,
or
as desired.
Solution 4
I claim that the ordered pair satisfies the criteria for all
Proof:
It is easy to see that the order modulo
of
is
since
, and we can assert and prove similarly for the order modulo
of
Thus, the remainders modulo
that the sequences of powers of
and
generate are
for even powers and
and
for odd powers, respectively. Since
and
are both odd for
Since there are infinitely many powers of
and since all ordered pairs
contain relatively prime integers, we are done.
-fidgetboss_4000
Solution 5 (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
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 |