Difference between revisions of "2017 USAJMO Problems/Problem 1"
Alexlikemath (talk | contribs) m |
Alexlikemath (talk | contribs) m |
||
Line 38: | Line 38: | ||
Since there are infinitely many integers larger than or equal to 2, the proof is complete .<math>\blacksquare</math> | Since there are infinitely many integers larger than or equal to 2, the proof is complete .<math>\blacksquare</math> | ||
+ | |||
+ | -AlexLikeMath | ||
− | |||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 22:10, 9 June 2020
Contents
[hide]Problem
Prove that there are infinitely many distinct pairs of relatively prime 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 the conditions, n is integer,
,
Proof:
We can expand using binomial theorem. However, since
, all the terms with power
larger than
modulo
evaluate to 0, and thus can be omitted. We are left with the terms:
, which is divisible by
.
Since there are infinitely many integers larger than or equal to 2, the proof is complete .
-AlexLikeMath
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 |