Difference between revisions of "2021 AIME II Problems/Problem 9"
MRENTHUSIASM (talk | contribs) (→Claim) |
MRENTHUSIASM (talk | contribs) m (→Proof 1) |
||
Line 15: | Line 15: | ||
~MRENTHUSIASM | ~MRENTHUSIASM | ||
− | ===Proof 1=== | + | ===Proof 1 (Euclidean Algorithm)=== |
− | <b> | + | If <math>a=b,</math> then <math>\gcd(a,b)=a=b,</math> from which the claim is clearly true. |
+ | |||
+ | Otherwise, let <math>a>b</math> without the loss of generality. Note that for all integers <math>p>q>0,</math> we have <cmath>\gcd(p,q)=\gcd(p-q,q).</cmath> We apply this result repeatedly to reduce the larger number: <cmath>\gcd\left(u^a-1,u^b-1\right)=\gcd\left(u^b-1,u^a-1-u^{a-b}\left(u^b-1\right)\right)=\gcd\left(u^b-1,u^{a-b}-1\right).</cmath> | ||
~MRENTHUSIASM | ~MRENTHUSIASM |
Revision as of 03:24, 1 April 2021
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
If and
are positive integers for which
then
~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
we have
We apply this result repeatedly to reduce the larger number:
~MRENTHUSIASM
Proof 2
Solution in progress. A million thanks for not editing.
~MRENTHUSIASM
Solution
Solution in progress. A million thanks for not editing.
~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.