Difference between revisions of "2021 AIME II Problems/Problem 9"
MRENTHUSIASM (talk | contribs) (→Solution (Detailed Explanation of Solution 1)) |
Mathkiddie (talk | contribs) (→Claim 1 (GCD Property)) |
||
(55 intermediate revisions by 5 users not shown) | |||
Line 3: | Line 3: | ||
==Solution 1== | ==Solution 1== | ||
− | + | This solution refers to the <b>Remarks</b> section. | |
− | + | By the Euclidean Algorithm, we have <cmath>\gcd\left(2^m+1,2^m-1\right)=\gcd\left(2,2^m-1\right)=1.</cmath> | |
+ | We are given that <math>\gcd\left(2^m+1,2^n-1\right)>1.</math> Multiplying both sides by <math>\gcd\left(2^m-1,2^n-1\right)</math> gives | ||
+ | <cmath>\begin{align*} | ||
+ | \gcd\left(2^m+1,2^n-1\right)\cdot\gcd\left(2^m-1,2^n-1\right)&>\gcd\left(2^m-1,2^n-1\right) \\ | ||
+ | \gcd\left(\left(2^m+1\right)\left(2^m-1\right),2^n-1\right)&>\gcd\left(2^m-1,2^n-1\right) \hspace{12mm} &&\text{by }\textbf{Claim 1} \\ | ||
+ | \gcd\left(2^{2m}-1,2^n-1\right)&>\gcd\left(2^m-1,2^n-1\right) \\ | ||
+ | 2^{\gcd(2m,n)}-1&>2^{\gcd(m,n)}-1 &&\text{by }\textbf{Claim 2} \\ | ||
+ | \gcd(2m,n)&>\gcd(m,n), | ||
+ | \end{align*}</cmath> | ||
+ | which implies that <math>n</math> must have more factors of <math>2</math> than <math>m</math> does. | ||
+ | |||
+ | We construct the following table for the first <math>30</math> positive integers: | ||
+ | <cmath>\begin{array}{c|c|c} | ||
+ | && \\ [-2.5ex] | ||
+ | \boldsymbol{\#}\textbf{ of Factors of }\boldsymbol{2} & \textbf{Numbers} & \textbf{Count} \\ | ||
+ | \hline | ||
+ | && \\ [-2.25ex] | ||
+ | 0 & 1,3,5,7,9,11,13,15,17,19,21,23,25,27,29 & 15 \\ | ||
+ | && \\ [-2.25ex] | ||
+ | 1 & 2,6,10,14,18,22,26,30 & 8 \\ | ||
+ | && \\ [-2.25ex] | ||
+ | 2 & 4,12,20,28 & 4 \\ | ||
+ | && \\ [-2.25ex] | ||
+ | 3 & 8,24 & 2 \\ | ||
+ | && \\ [-2.25ex] | ||
+ | 4 & 16 & 1 \\ | ||
+ | \end{array}</cmath> | ||
+ | To count the ordered pairs <math>(m,n),</math> we perform casework on the number of factors of <math>2</math> that <math>m</math> has: | ||
+ | <ol style="margin-left: 1.5em;"> | ||
+ | <li>If <math>m</math> has <math>0</math> factors of <math>2,</math> then <math>m</math> has <math>15</math> options and <math>n</math> has <math>8+4+2+1=15</math> options. So, this case has <math>15\cdot15=225</math> ordered pairs.</li><p> | ||
+ | <li>If <math>m</math> has <math>1</math> factor of <math>2,</math> then <math>m</math> has <math>8</math> options and <math>n</math> has <math>4+2+1=7</math> options. So, this case has <math>8\cdot7=56</math> ordered pairs.</li><p> | ||
+ | <li>If <math>m</math> has <math>2</math> factors of <math>2,</math> then <math>m</math> has <math>4</math> options and <math>n</math> has <math>2+1=3</math> options. So, this case has <math>4\cdot3=12</math> ordered pairs.</li><p> | ||
+ | <li>If <math>m</math> has <math>3</math> factors of <math>2,</math> then <math>m</math> has <math>2</math> options and <math>n</math> has <math>1</math> option. So, this case has <math>2\cdot1=2</math> ordered pairs.</li> | ||
+ | </ol> | ||
+ | Together, the answer is <math>225+56+12+2=\boxed{295}.</math> | ||
+ | |||
+ | ~Lcz ~MRENTHUSIASM | ||
+ | |||
+ | ==Solution 2== | ||
+ | |||
+ | Consider any ordered pair <math>(m,n)</math> such that <math>\gcd(2^m+1, 2^n-1) > 1</math>. There must exist some odd number <math>p\ne 1</math> such that <math>2^m \equiv -1 \pmod{p}</math> and <math>2^n \equiv 1 \pmod{p}</math>. Let <math>d</math> be the order of <math>2</math> modulo <math>p</math>. Note that <math>2^{2m} \equiv 1 \pmod{p}</math>. From this, we can say that <math>2m</math> and <math>n</math> are both multiples of <math>d</math>, but <math>m</math> is not. Thus, we have <math>v_2(n) \ge v_2(d)</math> and <math>v_2(m) + 1 = v_2(d)</math>. Substituting the latter equation into the inequality before gives <math>v_2(n) \ge v_2(m)+1</math>. Since <math>v_2(n)</math> and <math>v_2(m)</math> are integers, this implies <math>v_2(n)>v_2(m)</math>. The rest of the solution now proceeds as in Solution 1. | ||
− | ~ | + | ~Sedro |
− | == | + | ==Remarks== |
− | === | + | |
− | If <math>u,a,</math> and <math>b</math> are positive integers | + | ===Claim 1 (GCD Property)=== |
+ | <b>If <math>\boldsymbol{r,s,}</math> and <math>\boldsymbol{t}</math> are positive integers such that <math>\boldsymbol{\gcd(r,s)=1,}</math> then <math>\boldsymbol{\gcd(r,t)\cdot\gcd(s,t)=\gcd(rs,t).}</math></b> | ||
+ | |||
+ | As <math>r</math> and <math>s</math> are relatively prime (have no prime divisors in common), this property is intuitive. | ||
+ | |||
+ | ~MRENTHUSIASM | ||
+ | |||
+ | 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</math>. | ||
+ | |||
+ | 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)=== | ||
+ | <b>If <math>\boldsymbol{u,a,}</math> and <math>\boldsymbol{b}</math> are positive integers such that <math>\boldsymbol{u\geq2,}</math> then <math>\boldsymbol{\gcd\left(u^a-1,u^b-1\right)=u^{\gcd(a,b)}-1.}</math></b> | ||
There are two proofs to this claim, as shown below. | There are two proofs to this claim, as shown below. | ||
Line 17: | Line 73: | ||
~MRENTHUSIASM | ~MRENTHUSIASM | ||
− | ===Proof 1 (Euclidean Algorithm)=== | + | ===Claim 2 Proof 1 (Euclidean Algorithm)=== |
If <math>a=b,</math> then <math>\gcd(a,b)=a=b,</math> from which the claim is clearly true. | 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. | + | Otherwise, let <math>a>b</math> without the loss of generality. For all integers <math>p</math> and <math>q</math> such that <math>p>q>0,</math> the Euclidean Algorithm states that <cmath>\gcd(p,q)=\gcd(p-q,q)=\cdots=\gcd(p\operatorname{mod}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^a-1-u^{a-b}\left(u^b-1\right),u^b-1\right)=\gcd\left(u^{a-b}-1,u^b-1\right).</cmath> |
Continuing, we have | Continuing, we have | ||
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
− | \gcd\left(u^a-1,u^b-1\right) | + | \gcd\left(u^a-1,u^b-1\right)&=\gcd\left(u^{a-b}-1,u^b-1\right) \\ |
− | &=\gcd\left(u^b-1,u^ | + | & \ \vdots \\ |
− | & | ||
&=\gcd\left(u^{\gcd(a,b)}-1,u^{\gcd(a,b)}-1\right) \\ | &=\gcd\left(u^{\gcd(a,b)}-1,u^{\gcd(a,b)}-1\right) \\ | ||
&=u^{\gcd(a,b)}-1, | &=u^{\gcd(a,b)}-1, | ||
Line 33: | Line 88: | ||
~MRENTHUSIASM | ~MRENTHUSIASM | ||
− | ===Proof 2 (Bézout's Identity)=== | + | ===Claim 2 Proof 2 (Bézout's Identity)=== |
Let <math>d=\gcd\left(u^a-1,u^b-1\right).</math> It follows that <math>u^a\equiv1\pmod{d}</math> and <math>u^b\equiv1\pmod{d}.</math> | Let <math>d=\gcd\left(u^a-1,u^b-1\right).</math> It follows that <math>u^a\equiv1\pmod{d}</math> and <math>u^b\equiv1\pmod{d}.</math> | ||
− | By Bézout's Identity, there exist integers <math>x</math> and <math>y</math> | + | By Bézout's Identity, there exist integers <math>x</math> and <math>y</math> such that <math>ax+by=\gcd(a,b),</math> so <cmath>u^{\gcd(a,b)}=u^{ax+by}=(u^a)^x\cdot(u^b)^y\equiv1\pmod{d},</cmath> |
from which <math>u^{\gcd(a,b)}-1\equiv0\pmod{d}.</math> We know that <math>u^{\gcd(a,b)}-1\geq d.</math> | from which <math>u^{\gcd(a,b)}-1\equiv0\pmod{d}.</math> We know that <math>u^{\gcd(a,b)}-1\geq d.</math> | ||
− | + | Next, we notice that | |
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
u^a-1&=\left(u^{\gcd(a,b)}-1\right)\left(u^{a-\gcd{(a,b)}}+u^{a-2\gcd{(a,b)}}+u^{a-3\gcd{(a,b)}}+\cdots+1\right), \\ | u^a-1&=\left(u^{\gcd(a,b)}-1\right)\left(u^{a-\gcd{(a,b)}}+u^{a-2\gcd{(a,b)}}+u^{a-3\gcd{(a,b)}}+\cdots+1\right), \\ | ||
Line 48: | Line 103: | ||
~MRENTHUSIASM | ~MRENTHUSIASM | ||
− | == | + | ==Video Solution== |
− | + | https://youtu.be/h3awf7yhGZ4 | |
− | |||
− | + | ~MathProblemSolvingSkills.com | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | ==Video Solution by Interstigation== | |
+ | https://youtu.be/kasgsb0Rge4 | ||
− | ~ | + | ~Interstigation |
==See Also== | ==See Also== | ||
{{AIME box|year=2021|n=II|num-b=8|num-a=10}} | {{AIME box|year=2021|n=II|num-b=8|num-a=10}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 15:54, 15 April 2024
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
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.