Difference between revisions of "2017 USAMO Problems/Problem 1"
m |
(formaaaat) |
||
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 == |
Revision as of 09:18, 5 March 2023
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
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 |