Difference between revisions of "2017 USAMO Problems/Problem 1"
(→Solution 2) |
m (→Solution 4) |
||
(6 intermediate revisions by 5 users not shown) | |||
Line 21: | Line 21: | ||
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 | 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>gcd\left(\frac{3p-1}{2},\frac{p+1}2\right)=\frac{gcd(3p-1,p+1)}{2}</cmath> | ||
− | <cmath>=\frac{gcd(p | + | <cmath>=\frac{gcd(p-3,4)}{2}=\frac22=1</cmath> |
By the Euclidean Algorithm. | By the Euclidean Algorithm. | ||
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 == | ||
+ | |||
+ | 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= | + | {{USAMO newbox|year= 2017|before=First Problem|num-a=2}} |
Latest revision as of 09: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 |