Difference between revisions of "2021 AIME II Problems/Problem 13"
(→Solution 4 (Step by step transform)) |
(→Solution 1) |
||
(14 intermediate revisions by 4 users not shown) | |||
Line 4: | Line 4: | ||
==Solution 1== | ==Solution 1== | ||
− | Recall that <math>1000</math> divides this expression | + | Recall that <math>1000</math> divides this expression if <math>8</math> and <math>125</math> both divide it. It should be fairly obvious that <math>n \geq 3</math>; so we may break up the initial condition into two sub-conditions. |
(1) <math>5^n \equiv n \pmod{8}</math>. Notice that the square of any odd integer is <math>1</math> modulo <math>8</math> (proof by plugging in <math>1^2,3^2,5^2,7^2</math> into modulo <math>8</math>), so the LHS of this expression goes <math>5,1,5,1,\ldots</math>, while the RHS goes <math>1,2,3,4,5,6,7,8,1,\ldots</math>. The cycle length of the LHS is <math>2</math>, RHS is <math>8</math>, so the cycle length of the solution is <math>\operatorname{lcm}(2,8)=8</math>. Indeed, the <math>n</math> that solve this congruence are exactly those such that <math>n \equiv 5 \pmod{8}</math>. | (1) <math>5^n \equiv n \pmod{8}</math>. Notice that the square of any odd integer is <math>1</math> modulo <math>8</math> (proof by plugging in <math>1^2,3^2,5^2,7^2</math> into modulo <math>8</math>), so the LHS of this expression goes <math>5,1,5,1,\ldots</math>, while the RHS goes <math>1,2,3,4,5,6,7,8,1,\ldots</math>. The cycle length of the LHS is <math>2</math>, RHS is <math>8</math>, so the cycle length of the solution is <math>\operatorname{lcm}(2,8)=8</math>. Indeed, the <math>n</math> that solve this congruence are exactly those such that <math>n \equiv 5 \pmod{8}</math>. | ||
Line 107: | Line 107: | ||
Combining <math>a\equiv 24\pmod{25}</math> with <math>n \equiv 5 \pmod{8}</math> gives that <math>n</math> is in the form of <math>197+200k</math>, <math>n=197,397,597,797</math>. Note that since <math>\phi(125)=100</math> | Combining <math>a\equiv 24\pmod{25}</math> with <math>n \equiv 5 \pmod{8}</math> gives that <math>n</math> is in the form of <math>197+200k</math>, <math>n=197,397,597,797</math>. Note that since <math>\phi(125)=100</math> | ||
<cmath>2^{197+200k} \equiv 2^{197} \equiv 2^{-3} \equiv \underbrace{47}_{\text{Extended Euclidean Algorithm}}\pmod{125}</cmath> | <cmath>2^{197+200k} \equiv 2^{197} \equiv 2^{-3} \equiv \underbrace{47}_{\text{Extended Euclidean Algorithm}}\pmod{125}</cmath> | ||
− | Easy to check that only <math>\boxed{797}\equiv 47\pmod{125}</math> | + | Easy to check that only <math>\boxed{797}\equiv 47\pmod{125},{1797}\equiv 47\pmod{125},{2797}\equiv 47\pmod{125},...</math> |
~Afo | ~Afo | ||
− | ==Solution | + | ==Solution 5 (STEP by step transform)== |
− | |||
− | |||
− | |||
− | |||
− | The | + | 1. The desired <math>n</math> has the form <math>n = m + 20l + 100p,</math> where <math>m, l, p</math> are integers and <math>m < 20.</math> |
− | |||
− | |||
− | |||
− | |||
− | + | Really: <cmath>(2^{m+ 20} – (m + 20)) – (2^m – m) = (2^{m+ 20} – 2^m) – 20.</cmath> | |
+ | The first term is a multiple of <math>100</math>(<i><b>Claim</b></i>). | ||
− | + | We denote <i><b>step</b></i> an increase in <math>m</math> by 20. At each <i><b>step</b></i>, the divisibility by <math>10</math> is preserved, the number of tens is reduced by <math>2</math>. | |
+ | |||
+ | <cmath>(2^{m+ 100} – (m + 100)) – (2^m – m) = (2^{m+ 100} – 2^m) – 100.</cmath> | ||
+ | We denote <i><b>STEP</b></i> an increase in <math>m</math> by <math>100.</math> At each <i><b>STEP</b></i>, the first term is a multiple of <math>1000,</math> which means that at each <i><b>STEP</b></i> the divisibility by <math>100</math> is preserved, the number of hundreds decreases by <math>1.</math> | ||
+ | |||
+ | 2. If the expression <math>2^n + 5^n – n</math> is a multiple of <math>1000,</math> the number <math>n</math> is odd (<math>2^n</math> is even, <math>5^n</math> is odd), which means that <math>5^n</math> ends in <math>125.</math> Therefore, the number <math>2^n – n</math> ends in <math>875.</math> | ||
+ | |||
+ | 3. <math>2^3 – 3 = 8 – 3 = 5.</math> The tens digit is even <math>(0),</math> it cannot be transformed into <math>7</math> in several steps, since at each <i><b>step</b></i> this digit changes by <math>2.</math> | ||
+ | |||
+ | <math>17 = 20 – 3,</math> so <math>2^{17} + 2^3</math> is a multiple of <math>10,</math> <math>(2^{17} – 17) + (2^3 – 3) = 2^{17} + 2^3 – 20</math> is a multiple of <math>10.</math> | ||
+ | <cmath>2^{17} \pmod {100} = ((2^{10} \pmod {100}) \cdot (2^7 \pmod {100})) \pmod {100} = (24 \cdot 28) \pmod {100} = 72.</cmath> | ||
+ | <cmath>(2^{17} – 17 ) \pmod {100} = 55.</cmath> | ||
+ | The tens digit <math>5</math> is odd, subtracting <math>2</math> at each <i><b>step</b></i> in <math>4</math> <i><b>steps</b></i> of <math>20</math> will turn it into <math>7.</math> | ||
+ | So <cmath>(2^{97} – 97 ) \pmod {100} = 75.</cmath> | ||
+ | <cmath>2^{97} \pmod {1000} = ((2^{49} \pmod {1000}) \cdot 2^7) \pmod {1000} = 672.</cmath> | ||
+ | <cmath>(2^{97} – 97 ) \pmod {1000} = 575.</cmath> | ||
+ | We transform <math>5</math> into <math>8</math> in <math>7</math> <i><b>STEPS</b></i>, so <cmath>(2^{797} – 797 ) \pmod {1000} = 875. </cmath> | ||
+ | <cmath>(5^{797} + 2^{797} – 797 ) \pmod {1000} = 0.</cmath> | ||
+ | Note, that for <math>n = 797 + 1000k, k</math> is an integer, the expression <math>2^n + 5^n – n</math> is a multiple of <math>1000.</math> | ||
+ | |||
+ | <i><b>Claim</b></i> | ||
+ | |||
+ | The numbers <math>2^{n+2\cdot 5^k}+2^n=2^n(2^{2\cdot 5^k}+1)</math> and <math>2^{n+4\cdot 5^k}-2^n=2^n(2^{4\cdot 5^k}-1)</math> | ||
+ | |||
+ | are a multiple of <math>10^{k+1}</math> for any <math>n > k</math>, where <math>n,k</math> are an integer. | ||
+ | |||
+ | <i><b>Proof</b></i> | ||
+ | |||
+ | First, if <math>m \pmod{10} \equiv 4,</math> then <math>(m^4 – m^3 + m^2 – m + 1) \pmod{10} \equiv 6 – 4 + 6 – 4 + 1 = 5.</math> | ||
+ | |||
+ | <math>2^{4n+2}\pmod{10} \equiv 4.</math> So, if the number <math>2^{4n+2} + 1</math> is a multiple of <math>5^k</math>, then <math>2^{20n+10} + 1</math> is a multiple of <math>5^{k +1}.</math> | ||
+ | |||
+ | Really, denote <math>m = 2^{4n+2},</math> then, <math>2^{20n+10} + 1 = m^5 + 1 = (m + 1)\cdot (m^4 – m^3 + m^2 – m + 1).</math> | ||
The first factor is a multiple of <math>5^k</math>, the second factor is a multiple of <math>5.</math> | The first factor is a multiple of <math>5^k</math>, the second factor is a multiple of <math>5.</math> | ||
Their product is a multiple of <math>5^{k +1}.</math> | Their product is a multiple of <math>5^{k +1}.</math> | ||
− | For odd <math>n,</math> using Newton's binomial, we get: | + | For odd <math>n,</math> using Newton's binomial for <math>4^n</math>, we get <math>2^{2n} + 1</math> is a multiple of <math>5.</math> |
+ | <cmath>\begin{align*} 2^{2n} + 1 = 4^n + 1 = (5 - 1)^n + 1 = 5^n -n\cdot 5^{n-1} +...+5n\end{align*}</cmath> | ||
+ | If <math>n = 5^k,</math> then <math>n > k,</math> each term is a multiple of <math>5n</math>. | ||
+ | |||
+ | Therefore, the number <math>4^{5^k}+1</math> is a multiple of <math>5^{k+1}</math> and <math>2^{k+1} (2^{2\cdot 5^k}+1)</math> is a multiple of <math>10^{k+1}</math>. | ||
+ | |||
+ | The difference <cmath>2^{n+4\cdot 5^k}-2^n=2^n(2^{4\cdot 5^k}-1) = 2^n(2^{2\cdot 5^k}-1)(2^{2\cdot 5^k}+1)</cmath> is a multiple of <math>10^{k+1}.</math> | ||
+ | |||
+ | '''vladimir.shelomovskii@gmail.com, vvsss''' | ||
+ | |||
+ | ==Note== | ||
+ | If you are wondering, <math>\frac{2^{797}+5^{797}-797}{1000}</math> is equal to the following <math>555</math>-digit number: | ||
+ | |||
+ | <math>119{,}975{,}745{,}111{,}650{,}476{,}385{,}411{,}555{,}010{,}245{,}228{,}283{,}196{,}935{,}699{,}128{,}663{,}834{,}986{,}755{,}809{,}416{,}868{,}468{,}175{,}224{,}221{,}677{,} \\ | ||
+ | 450{,}271{,}793{,}186{,}899{,}399{,}171{,}810{,}240{,}468{,}879{,}630{,}691{,}320{,}210{,}517{,}618{,}332{,}910{,}064{,}430{,}017{,}422{,}410{,}572{,}497{,}874{,}327{,}116{,} \\ | ||
+ | 662{,}273{,}049{,}144{,}209{,}532{,}072{,}513{,}248{,}821{,}826{,}125{,}454{,}909{,}131{,}367{,}242{,}561{,}087{,}064{,}439{,}357{,}641{,}814{,}942{,}784{,}478{,}465{,}638{,} \\ | ||
+ | 163{,}997{,}895{,}630{,}266{,}780{,}260{,}171{,}070{,}180{,}244{,}384{,}687{,}160{,}174{,}154{,}618{,}815{,}254{,}719{,}975{,}476{,}350{,}789{,}415{,}969{,}908{,}281{,}131{,} \\ | ||
+ | 044{,}034{,}581{,}864{,}573{,}596{,}962{,}567{,}993{,}948{,}922{,}431{,}587{,}652{,}735{,}290{,}158{,}293{,}666{,}986{,}616{,}531{,}419{,}688{,}663{,}485{,}548{,}648{,}995{,} \\ | ||
+ | 509{,}247{,}893{,}796{,}528{,}146{,}109{,}144{,}143{,}744{,}650{,}882{,}271{,}050{,}771{,}309{,}301{,}498{,}467{,}898{,}226{,}649{,}089{,}924{,}520{,}539{,}820{,}344{,}035{,} \\ | ||
+ | 886{,}481{,}987{,}499{,}589{,}845{,}734{,}228{,}834{,}491{,}187.</math> | ||
+ | |||
+ | ==Video Solution by Interstigation== | ||
+ | Did not use any advanced method, easily understandable: | ||
+ | |||
+ | https://youtu.be/ThF67J8iaS0 | ||
+ | |||
+ | ~Interstigation | ||
==See Also== | ==See Also== | ||
{{AIME box|year=2021|n=II|num-b=12|num-a=14}} | {{AIME box|year=2021|n=II|num-b=12|num-a=14}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 23:16, 26 January 2024
Contents
Problem
Find the least positive integer for which
is a multiple of
.
Solution 1
Recall that divides this expression if
and
both divide it. It should be fairly obvious that
; so we may break up the initial condition into two sub-conditions.
(1) . Notice that the square of any odd integer is
modulo
(proof by plugging in
into modulo
), so the LHS of this expression goes
, while the RHS goes
. The cycle length of the LHS is
, RHS is
, so the cycle length of the solution is
. Indeed, the
that solve this congruence are exactly those such that
.
(2) . This is extremely computationally intensive if we try to calculate all
, so we take a divide-and-conquer approach instead. In order for this expression to be true,
is necessary; it shouldn't take too long for us to go through the
possible LHS-RHS combinations, considering that
must be odd. We only need to test
values of
and obtain
or
.
With this in mind we consider . By the Generalized Fermat's Little Theorem,
, but we already have
modulo
. Our calculation is greatly simplified. The LHS's cycle length is
and the RHS's cycle length is
, from which their least common multiple is
. In this step we need to test all the numbers between
to
that
or
. In the case that
, the RHS goes
, and we need
; clearly
. In the case that
, by a similar argument,
.
In the final step, we need to calculate and
modulo
:
Note that ; because
we get
.
Note that is
. We have
This time, LHS cycle is
, RHS cycle is
, so we need to figure out
modulo
. It should be
.
Put everything together. By the second subcondition, the only candidates less than are
. Apply the first subcondition,
is the desired answer.
~Ross Gao (Solution)
~MRENTHUSIASM (Minor Reformatting)
Solution 2
We have that , or
and
by CRT. It is easy to check
don't work, so we have that
. Then,
and
, so we just have
and
. Let us consider both of these congruences separately.
First, we look at . By Euler's Totient Theorem (ETT), we have
, so
. On the RHS of the congruence, the possible values of
are all nonnegative integers less than
and on the RHS the only possible values are
and
. However, for
to be
we must have
, a contradiction. So, the only possible values of
are when
.
Now we look at . Plugging in
, we get
. Note, for
to be satisfied, we must have
and
. Since
as
, we have
. Then,
. Now, we get
. Using the fact that
, we get
. The inverse of
modulo
is obviously
, so
, so
. Plugging in
, we get
.
Now, we are finally ready to plug into the congruence modulo
. Plugging in, we get
. By ETT, we get
, so
. Then,
. Plugging this in, we get
, implying the smallest value of
is simply
.
~rocketsri
Solution 3 (Chinese Remainder Theorem and Binomial Theorem)
We wish to find the least positive integer for which
Rearranging gives
Applying the Chinese Remainder Theorem, we get the following system of congruences:
It is clear that
from which we simplify to
We solve each congruence separately:
- For
quick inspections produce that
are congruent to
modulo
respectively. More generally,
if
is odd, and
if
is even. As
is always odd (so is
), we must have
That is,
for some nonnegative integer
- For
we substitute the result from
and simplify:
Note that
and
so we apply the Binomial Theorem to the left side:
Since
it follows that
![$\boldsymbol{r=5s+4}$](http://latex.artofproblemsolving.com/7/5/f/75f5b3b1c9f7b524ccdfd2471b0d473a60fe1567.png)
![$\boldsymbol{s.}$](http://latex.artofproblemsolving.com/b/c/9/bc9ff6f1810b9af8c4faac07244012d98b5cfb31.png)
Substituting this back into we get
As
is a multiple of
it has at least three factors of
Since
contributes one factor,
contributes at least two factors, or
must be a multiple of
Therefore, the least such nonnegative integer
is
Finally, combining the two results from above (bolded) generates the least such positive integer at
~MRENTHUSIASM (inspired by Math Jams's 2021 AIME II Discussion)
Solution 4 (Minimal Computation)
Note that
and
so
is periodic every
. Easy to check that only
satisfy. Let
. Note that by binomial theorem,
So we have
.
Combining
with
gives that
is in the form of
,
. Note that since
Easy to check that only
~Afo
Solution 5 (STEP by step transform)
1. The desired has the form
where
are integers and
Really:
The first term is a multiple of
(Claim).
We denote step an increase in by 20. At each step, the divisibility by
is preserved, the number of tens is reduced by
.
We denote STEP an increase in
by
At each STEP, the first term is a multiple of
which means that at each STEP the divisibility by
is preserved, the number of hundreds decreases by
2. If the expression is a multiple of
the number
is odd (
is even,
is odd), which means that
ends in
Therefore, the number
ends in
3. The tens digit is even
it cannot be transformed into
in several steps, since at each step this digit changes by
so
is a multiple of
is a multiple of
The tens digit
is odd, subtracting
at each step in
steps of
will turn it into
So
We transform
into
in
STEPS, so
Note, that for
is an integer, the expression
is a multiple of
Claim
The numbers and
are a multiple of for any
, where
are an integer.
Proof
First, if then
So, if the number
is a multiple of
, then
is a multiple of
Really, denote then,
The first factor is a multiple of , the second factor is a multiple of
Their product is a multiple of
For odd using Newton's binomial for
, we get
is a multiple of
If
then
each term is a multiple of
.
Therefore, the number is a multiple of
and
is a multiple of
.
The difference is a multiple of
vladimir.shelomovskii@gmail.com, vvsss
Note
If you are wondering, is equal to the following
-digit number:
Video Solution by Interstigation
Did not use any advanced method, easily understandable:
~Interstigation
See Also
2021 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 12 |
Followed by Problem 14 | |
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.