Difference between revisions of "2021 AIME II Problems/Problem 9"
Mathkiddie (talk | contribs) (→Claim 1 (GCD Property)) |
Mathkiddie (talk | contribs) (→Claim 1 (GCD Property)) |
||
Line 60: | Line 60: | ||
To prove this rigorously, let <math>\gcd(r, t)=d_1</math> and <math>\gcd(s, t)=d_2</math>. Then, <math>r=x d_1</math>, <math>s=y d_2</math>, and <math>t=k d_1 d_2</math>. Note that <math>\gcd(d_1, k)=1</math> and <math>\gcd(d_2, k)=1</math>. | To prove this rigorously, let <math>\gcd(r, t)=d_1</math> and <math>\gcd(s, t)=d_2</math>. Then, <math>r=x d_1</math>, <math>s=y d_2</math>, and <math>t=k d_1 d_2</math>. Note that <math>\gcd(d_1, k)=1</math> and <math>\gcd(d_2, k)=1</math>. | ||
− | Then, the left hand side of the equation is simply <math>d_1 d_2 | + | Then, the left hand side of the equation is simply <math>d_1 d_2</math>. |
− | ~Mathkiddie | + | For the right hand side, <math>\gcd(rs, t)=\gcd(xy d_1 d_2, k d_1 d_2)</math>. But because <math>xy</math> and <math>k</math> are relatively prime, this simplifies down to <math>d_1 d_2</math>. Therefore, we have shown that <math>\gcd(r, t)\cdot\gcd(s, t)=\gcd(rs, t)</math>. |
+ | |||
+ | ~[[Mathkiddie]] | ||
===Claim 2 (Olympiad Number Theory Lemma)=== | ===Claim 2 (Olympiad Number Theory Lemma)=== |
Revision as of 14:54, 15 April 2024
Contents
[hide]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
This solution refers to the Remarks section.
By the Euclidean Algorithm, we have We are given that Multiplying both sides by gives which implies that must have more factors of than does.
We construct the following table for the first positive integers: To count the ordered pairs we perform casework on the number of factors of that has:
- If has factors of then has options and has options. So, this case has ordered pairs.
- If has factor of then has options and has options. So, this case has ordered pairs.
- If has factors of then has options and has options. So, this case has ordered pairs.
- If has factors of then has options and has option. So, this case has ordered pairs.
Together, the answer is
~Lcz ~MRENTHUSIASM
Solution 2
Consider any ordered pair such that . There must exist some odd number such that and . Let be the order of modulo . Note that . From this, we can say that and are both multiples of , but is not. Thus, we have and . Substituting the latter equation into the inequality before gives . Since and are integers, this implies . The rest of the solution now proceeds as in Solution 1.
~Sedro
Remarks
Claim 1 (GCD Property)
If and are positive integers such that then
As and are relatively prime (have no prime divisors in common), this property is intuitive.
~MRENTHUSIASM
To prove this rigorously, let and . Then, , , and . Note that and .
Then, the left hand side of the equation is simply .
For the right hand side, . But because and are relatively prime, this simplifies down to . Therefore, we have shown that .
Claim 2 (Olympiad Number Theory Lemma)
If and are positive integers such that then
There are two proofs to this claim, as shown below.
~MRENTHUSIASM
Claim 2 Proof 1 (Euclidean Algorithm)
If then from which the claim is clearly true.
Otherwise, let without the loss of generality. For all integers and such that 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
Claim 2 Proof 2 (Bézout's Identity)
Let It follows that and
By Bézout's Identity, there exist integers and such that so from which We know that
Next, we notice that Since is a common divisor of and we conclude that from which the proof is complete.
~MRENTHUSIASM
Video Solution
~MathProblemSolvingSkills.com
Video Solution by Interstigation
~Interstigation
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.