Difference between revisions of "2021 AIME II Problems/Problem 13"
MRENTHUSIASM (talk | contribs) m (→Solution 3 (Chinese Remainder Theorem and Binomial Theorem)) |
MRENTHUSIASM (talk | contribs) m |
||
(18 intermediate revisions by 2 users not shown) | |||
Line 4: | Line 4: | ||
==Solution 1== | ==Solution 1== | ||
− | 1000 divides this expression iff 8 | + | <math>1000</math> divides this expression iff <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 1 modulo 8 (proof by plugging in <math>1^2 | + | (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>. |
− | (2) <math>2^n \equiv n \pmod{125}</math>. This is extremely computationally intensive if you try to calculate all <math>2^1,2^2, | + | (2) <math>2^n \equiv n \pmod{125}</math>. This is extremely computationally intensive if you try to calculate all <math>2^1,2^2,\ldots,2^{100} \pmod{125}</math>, so instead, we take a divide-and-conquer approach. In order for this expression to be true, <math>2^n \equiv n \pmod{5}</math> is necessary; it shouldn't take too long for you to go through the <math>20</math> possible LHS-RHS combinations and convince yourself that <math>n \equiv 3 \pmod{20}</math> or <math>n \equiv 17 \pmod{20}</math>. |
− | With this in mind we consider <math>2^n \equiv n</math> | + | With this in mind we consider <math>2^n \equiv n \pmod{25}</math>. By the Generalized Fermat's Little Theorem, <math>2^{20} \equiv 1 \pmod{25}</math>, but we already have <math>n</math> modulo <math>20</math>. Our calculation is greatly simplified. The LHS cycle length is <math>20</math>, RHS cycle length is <math>25</math>, the lcm is <math>100</math>, in this step we need to test all the numbers between <math>1</math> to <math>100</math> that <math>n \equiv 3 \pmod{20}</math> or <math>n \equiv 17 \pmod{20}</math>. In the case that <math>n \equiv 3 \pmod{20}</math>, the RHS goes <math>3,23,43,63,83</math>, and we need <math>2^n \equiv n \equiv 2^3 \pmod{25}</math>; clearly <math>n \equiv 83 \pmod{100}</math>. In the case that <math>n \equiv 17 \pmod{20}</math>, by a similar argument, <math>n \equiv 97 \pmod{100}</math>. |
− | In the final step, we need to calculate <math>2^{97} | + | In the final step, we need to calculate <math>2^{97}</math> and <math>2^{83}</math> modulo <math>125</math>: |
+ | |||
+ | Note that <math>2^{97}\equiv2^{-3}</math>; because <math>8\cdot47=376\equiv1\pmod{125},</math> we get <math>2^{97} \equiv 47\pmod{125}</math>. | ||
+ | |||
+ | Note that <math>2^{83}</math> is <math>2^{-17}=2^{-16}\cdot2^{-1}</math>. We have | ||
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
− | 2^{-1}& | + | 2^{-1}&\equiv63, \\ |
− | 2^{-2}& | + | 2^{-2}&\equiv63^2=3969\equiv-31, \\ |
− | 2^{-4}& | + | 2^{-4}&\equiv(-31)^2=961\equiv-39, \\ |
− | 2^{-8}& | + | 2^{-8}&\equiv1521\equiv21, \\ |
− | 2^{-16}& | + | 2^{-16}&\equiv441, \\ |
− | 2^{-17}& | + | 2^{-17}&\equiv63\cdot441\equiv7\cdot(-31)=-217\equiv33. |
\end{align*}</cmath> | \end{align*}</cmath> | ||
− | This time, LHS cycle is 100, RHS cycle is 125, so we need to figure out | + | This time, LHS cycle is <math>100</math>, RHS cycle is <math>125</math>, so we need to figure out <math>n</math> modulo <math>500</math>. It should be <math>n \equiv 283,297 \pmod{500}</math>. |
− | Put everything together. By the second subcondition, the only candidates < | + | Put everything together. By the second subcondition, the only candidates less than <math>1000</math> are <math>283,297,782,797</math>. Apply the first subcondition, <math>n=\boxed{797}</math> is the desired answer. |
− | + | ~Ross Gao (Solution) | |
+ | |||
+ | ~MRENTHUSIASM (Minor Reformatting) | ||
==Solution 2== | ==Solution 2== | ||
We have that <math>2^n + 5^n \equiv n\pmod{1000}</math>, or <math>2^n + 5^n \equiv n \pmod{8}</math> and <math>2^n + 5^n \equiv n \pmod{125}</math> by CRT. It is easy to check <math>n < 3</math> don't work, so we have that <math>n \geq 3</math>. Then, <math>2^n \equiv 0 \pmod{8}</math> and <math>5^n \equiv 0 \pmod{125}</math>, so we just have <math>5^n \equiv n \pmod{8}</math> and <math>2^n \equiv n \pmod{125}</math>. Let us consider both of these congruences separately. | We have that <math>2^n + 5^n \equiv n\pmod{1000}</math>, or <math>2^n + 5^n \equiv n \pmod{8}</math> and <math>2^n + 5^n \equiv n \pmod{125}</math> by CRT. It is easy to check <math>n < 3</math> don't work, so we have that <math>n \geq 3</math>. Then, <math>2^n \equiv 0 \pmod{8}</math> and <math>5^n \equiv 0 \pmod{125}</math>, so we just have <math>5^n \equiv n \pmod{8}</math> and <math>2^n \equiv n \pmod{125}</math>. Let us consider both of these congruences separately. | ||
− | |||
First, we look at <math>5^n \equiv n \pmod{8}</math>. By Euler's Totient Theorem (ETT), we have <math>5^4 \equiv 1 \pmod{8}</math>, so <math>5^5 \equiv 5 \pmod{8}</math>. On the RHS of the congruence, the possible values of <math>n</math> are all nonnegative integers less than <math>8</math> and on the RHS the only possible values are <math>5</math> and <math>1</math>. However, for <math>5^n</math> to be <math>1 \pmod{8}</math> we must have <math>n \equiv 0 \pmod{4}</math>, a contradiction. So, the only possible values of <math>n</math> are when <math>n \equiv 5 \pmod{8} \implies n = 8k+5</math>. | First, we look at <math>5^n \equiv n \pmod{8}</math>. By Euler's Totient Theorem (ETT), we have <math>5^4 \equiv 1 \pmod{8}</math>, so <math>5^5 \equiv 5 \pmod{8}</math>. On the RHS of the congruence, the possible values of <math>n</math> are all nonnegative integers less than <math>8</math> and on the RHS the only possible values are <math>5</math> and <math>1</math>. However, for <math>5^n</math> to be <math>1 \pmod{8}</math> we must have <math>n \equiv 0 \pmod{4}</math>, a contradiction. So, the only possible values of <math>n</math> are when <math>n \equiv 5 \pmod{8} \implies n = 8k+5</math>. | ||
Line 35: | Line 40: | ||
Now we look at <math>2^n \equiv n \pmod{125}</math>. Plugging in <math>n = 8k+5</math>, we get <math>2^{8k+5} \equiv 8k+5 \pmod{125} \implies 2^{8k} \cdot 32 \equiv 8k+5 \pmod{125}</math>. Note, for <math>2^n \equiv n\pmod{125}</math> to be satisfied, we must have <math>2^n \equiv n \pmod{5}</math> and <math>2^n \equiv n\pmod{25}</math>. Since <math>2^{8k} \equiv 1\pmod{5}</math> as <math>8k \equiv 0\pmod{4}</math>, we have <math>2 \equiv -2k \pmod{5} \implies k = 5m-1</math>. Then, <math>n = 8(5m-1) + 5 = 40m-3</math>. Now, we get <math>2^{40m-3} \equiv 40m-3 \pmod{125}</math>. Using the fact that <math>2^n \equiv n\pmod{25}</math>, we get <math>2^{-3} \equiv 15m-3 \pmod{25}</math>. The inverse of <math>2</math> modulo <math>25</math> is obviously <math>13</math>, so <math>2^{-3} \equiv 13^3 \equiv 22 \pmod{25}</math>, so <math>15m \equiv 0 \pmod{25} \implies m = 5s</math>. Plugging in <math>m = 5s</math>, we get <math>n = 200s - 3</math>. | Now we look at <math>2^n \equiv n \pmod{125}</math>. Plugging in <math>n = 8k+5</math>, we get <math>2^{8k+5} \equiv 8k+5 \pmod{125} \implies 2^{8k} \cdot 32 \equiv 8k+5 \pmod{125}</math>. Note, for <math>2^n \equiv n\pmod{125}</math> to be satisfied, we must have <math>2^n \equiv n \pmod{5}</math> and <math>2^n \equiv n\pmod{25}</math>. Since <math>2^{8k} \equiv 1\pmod{5}</math> as <math>8k \equiv 0\pmod{4}</math>, we have <math>2 \equiv -2k \pmod{5} \implies k = 5m-1</math>. Then, <math>n = 8(5m-1) + 5 = 40m-3</math>. Now, we get <math>2^{40m-3} \equiv 40m-3 \pmod{125}</math>. Using the fact that <math>2^n \equiv n\pmod{25}</math>, we get <math>2^{-3} \equiv 15m-3 \pmod{25}</math>. The inverse of <math>2</math> modulo <math>25</math> is obviously <math>13</math>, so <math>2^{-3} \equiv 13^3 \equiv 22 \pmod{25}</math>, so <math>15m \equiv 0 \pmod{25} \implies m = 5s</math>. Plugging in <math>m = 5s</math>, we get <math>n = 200s - 3</math>. | ||
− | Now, we are finally ready to plug <math>n</math> into the congruence modulo <math>125</math>. Plugging in, we get <math>2^{200s-3} \equiv 200s - 3 \pmod{125}</math>. By ETT, we get <math>2^{100} \equiv 1 \pmod{125}</math>, so <math>2^{200s- 3} \equiv 2^{-3} \equiv 47 \pmod{125}</math>. Then, <math>200s \equiv 50 \pmod{125} \implies s \equiv 4 \pmod{5} \implies s = 5y+4</math>. Plugging this in, we get <math>n = 200(5y+4) - 3 = 1000y+797</math>, implying the smallest value of <math>n</math> is simply <math>\boxed{797}</math>. ~rocketsri | + | Now, we are finally ready to plug <math>n</math> into the congruence modulo <math>125</math>. Plugging in, we get <math>2^{200s-3} \equiv 200s - 3 \pmod{125}</math>. By ETT, we get <math>2^{100} \equiv 1 \pmod{125}</math>, so <math>2^{200s- 3} \equiv 2^{-3} \equiv 47 \pmod{125}</math>. Then, <math>200s \equiv 50 \pmod{125} \implies s \equiv 4 \pmod{5} \implies s = 5y+4</math>. Plugging this in, we get <math>n = 200(5y+4) - 3 = 1000y+797</math>, implying the smallest value of <math>n</math> is simply <math>\boxed{797}</math>. |
+ | |||
+ | ~rocketsri | ||
==Solution 3 (Chinese Remainder Theorem and Binomial Theorem)== | ==Solution 3 (Chinese Remainder Theorem and Binomial Theorem)== | ||
− | We wish to find the least positive integer <math>n</math> for which <math>2^n+5^n-n\equiv0\pmod{1000}.</math> Rearranging gives <cmath>2^n+5^n\equiv n\pmod{1000}.</cmath> Applying the Chinese Remainder Theorem, we get the following | + | We wish to find the least positive integer <math>n</math> for which <math>2^n+5^n-n\equiv0\pmod{1000}.</math> Rearranging gives <cmath>2^n+5^n\equiv n\pmod{1000}.</cmath> Applying the Chinese Remainder Theorem, we get the following system of congruences: |
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
2^n+5^n &\equiv n \pmod{8}, \\ | 2^n+5^n &\equiv n \pmod{8}, \\ | ||
Line 50: | Line 57: | ||
We solve each congruence separately: | We solve each congruence separately: | ||
<ol style="margin-left: 1.5em;"> | <ol style="margin-left: 1.5em;"> | ||
− | <li>For <math>(1),</math> quick inspections produce that <math>5^1,5^2,5^3,5^4,\ | + | <li>For <math>(1),</math> quick inspections produce that <math>5^1,5^2,5^3,5^4,\ldots</math> are congruent to <math>5,1,5,1,\ldots</math> modulo <math>8,</math> respectively. More generally, <math>5^n \equiv 5 \pmod{8}</math> if <math>n</math> is odd, and <math>5^n \equiv 1 \pmod{8}</math> if <math>n</math> is even. As <math>5^n</math> is always odd (so is <math>n</math>), we must have <math>n\equiv5\pmod{8}.</math> <p> |
<i><b>That is, <math>\boldsymbol{n=8r+5}</math> for some nonnegative integer <math>\boldsymbol{r.}</math></b></i></li><p> | <i><b>That is, <math>\boldsymbol{n=8r+5}</math> for some nonnegative integer <math>\boldsymbol{r.}</math></b></i></li><p> | ||
<li>For <math>(2),</math> we substitute the result from <math>(1)</math> and simplify:</li> | <li>For <math>(2),</math> we substitute the result from <math>(1)</math> and simplify:</li> | ||
Line 82: | Line 89: | ||
10(s+6)&\equiv0\pmod{125}. | 10(s+6)&\equiv0\pmod{125}. | ||
\end{align*}</cmath> | \end{align*}</cmath> | ||
− | As <math>10(s+6)</math> is a multiple of <math>125,</math> it has at least three factors of <math>5.</math> Since <math>10</math> contributes one factor, | + | As <math>10(s+6)</math> is a multiple of <math>125,</math> it has at least three factors of <math>5.</math> Since <math>10</math> contributes one factor, <math>s+6</math> contributes at least two factors, or <math>s+6</math> must be a multiple of <math>25.</math> Therefore, the least such nonnegative integer <math>s</math> is <math>19.</math> |
</ol> | </ol> | ||
Finally, combining the two results from above (bolded) generates the least such positive integer <math>n</math> at <math>s=19:</math> | Finally, combining the two results from above (bolded) generates the least such positive integer <math>n</math> at <math>s=19:</math> | ||
Line 104: | Line 111: | ||
~Afo | ~Afo | ||
− | ==See | + | ==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 18:03, 8 September 2021
Contents
Problem
Find the least positive integer for which is a multiple of .
Solution 1
divides this expression iff 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 you try to calculate all , so instead, we take a divide-and-conquer approach. In order for this expression to be true, is necessary; it shouldn't take too long for you to go through the possible LHS-RHS combinations and convince yourself that 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 cycle length is , RHS cycle length is , the lcm 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
That is, for some nonnegative integerSubstituting 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
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.