2021 AIME II Problems/Problem 9
Contents
Problem
Find the number of ordered pairs such that
and
are positive integers in the set
and the greatest common divisor of
and
is not
.
Solution 1
We make use of the (olympiad number theory) lemma that .
Noting , we have (by difference of squares)
It is now easy to calculate the answer (with casework on
) as
.
~Lcz
Solution 2 (Generalized and Comprehensive)
Claim (Solution 1's Lemma)
If and
are positive integers with
then
There are two proofs to this claim, as shown below.
~MRENTHUSIASM
Proof 1 (Euclidean Algorithm)
If then
from which the claim is clearly true.
Otherwise, let without the loss of generality. Note that for all integers
the Euclidean Algorithm states that
We apply this result repeatedly to reduce the larger number:
Continuing, we have
from which the proof is complete.
~MRENTHUSIASM
Proof 2 (Bézout's Identity)
Let It follows that
and
By Bézout's Identity, there exist integers and
for which
thus
from which
We know that
Notice that
Since
is a common divisor of
and
we conclude that
and the proof is complete.
~MRENTHUSIASM
Solution
Solution in progress. A million thanks for not editing.
~MRENTHUSIASM
Remark (GCD Fact)
In of the solution, we use the following result:
For positive integers and
if
then
As and
are relatively prime (have no prime factors in common), this result is intuitive.
~MRENTHUSIASM
See Also
2021 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 8 |
Followed by Problem 10 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.