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 (→Solution 3 (Chinese Remainder Theorem and Binomial Theorem)) |
||
Line 44: | Line 44: | ||
\end{align*}</cmath> | \end{align*}</cmath> | ||
It is clear that <math>n\geq3,</math> from which we simplify to | It is clear that <math>n\geq3,</math> from which we simplify to | ||
− | <cmath>\begin{align} | + | <cmath>\begin{align*} |
− | 5^n &\equiv n \pmod{8}, \\ | + | 5^n &\equiv n \pmod{8}, \hspace{15mm} &(1) \\ |
− | 2^n &\equiv n \pmod{125}. | + | 2^n &\equiv n \pmod{125}. &(2) |
− | \end{align}</cmath> | + | \end{align*}</cmath> |
<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,\cdots</math> are congruent to <math>5,1,5,1,\cdots</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> <i><b>That is, <math>\boldsymbol{n=8r+5}</math> for some integer <math>\boldsymbol{r.}</math></b></i></li><p> | + | <li>For <math>(1),</math> quick inspections produce that <math>5^1,5^2,5^3,5^4,\cdots</math> are congruent to <math>5,1,5,1,\cdots</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 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> | ||
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
Line 64: | Line 65: | ||
32+160r+400r(r-1)&\equiv8r+5\pmod{125} \\ | 32+160r+400r(r-1)&\equiv8r+5\pmod{125} \\ | ||
32+35r+25r(r-1)&\equiv8r+5\pmod{125} \\ | 32+35r+25r(r-1)&\equiv8r+5\pmod{125} \\ | ||
− | + | 25r^2+2r+27&\equiv0\pmod{125}. \hspace{30mm} (*) | |
− | 25r^2+2r+27&\equiv0\pmod{125}. | ||
\end{align*}</cmath> | \end{align*}</cmath> | ||
Since <math>125\equiv0\pmod{5},</math> it follows that | Since <math>125\equiv0\pmod{5},</math> it follows that | ||
Line 73: | Line 73: | ||
r&\equiv4\pmod{5}. | r&\equiv4\pmod{5}. | ||
\end{align*}</cmath> | \end{align*}</cmath> | ||
− | <i><b>That is, <math>\boldsymbol{r=5s+4}</math> for some integer <math>\boldsymbol{s.}</math></b></i> | + | <i><b>That is, <math>\boldsymbol{r=5s+4}</math> for some integer <math>\boldsymbol{s.}</math></b></i><p> |
+ | Substituting this back into <math>(*),</math> we get | ||
+ | <cmath>\begin{align*} | ||
+ | 25(5s+4)^2+2(5s+4)+27&\equiv0\pmod{125} \\ | ||
+ | 625s^2+1010s+435&\equiv0\pmod{125} \\ | ||
+ | 10s+60&\equiv0\pmod{125} \\ | ||
+ | 10(s+6)&\equiv0\pmod{125} | ||
+ | \end{align*}</cmath> | ||
</ol> | </ol> | ||
+ | Combining the two results above (bolded), we express <math>n</math> in terms of <math>s:</math> <cmath>n=8r+5=8(5s+4)+5=40s+37.</cmath> | ||
<b>SOLUTION IN PROGRESS. WILL FINISH WITHIN TODAY. A MILLION THANKS FOR NOT EDITING.</b> | <b>SOLUTION IN PROGRESS. WILL FINISH WITHIN TODAY. A MILLION THANKS FOR NOT EDITING.</b> |
Revision as of 04:59, 12 April 2021
Contents
Problem
Find the least positive integer for which is a multiple of .
Solution 1
1000 divides this expression iff 8, 125 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 1 modulo 8 (proof by plugging in , , , into modulo 8), so the LHS of this expression goes "5,1,5,1, ...", while the RHS goes "1,2,3,4,5,6,7,8,1, ...". The cycle length of the LHS is 2, RHS is 8, so the cycle length of the solution is . Indeed, the n that solve this equation 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 20 possible LHS-RHS combinations and convince yourself that or .
With this in mind we consider modulo 25. By the generalized Fermat's little theorem, , but we already have n modulo 20! Our calculation is greatly simplified. The LHS cycle length is 20, RHS cycle length is 25, the lcm is 100, in this step we need to test all the numbers between 1 to 100 that or . In the case that , , and RHS goes "3,23,43,63,83"; clearly . In the case that , by a similar argument, .
In the final step, we need to calculate modulo 125. The former is simply ; because modulo 125, . is . This time, LHS cycle is 100, RHS cycle is 125, so we need to figure out what is n modulo 500. It should be .
Put everything together. By the second subcondition, the only candidates < 100 are . Apply the first subcondition, n=797 is the desired answer.
-Ross Gao
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 systems of linear congruences: It is clear that from which we simplify to
- 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 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 integerSubstituting this back into we get
Combining the two results above (bolded), we express in terms of
SOLUTION IN PROGRESS. WILL FINISH WITHIN TODAY. A MILLION THANKS FOR NOT EDITING.
~MRENTHUSIASM (inspired by Math Jams's 2021 AIME II Discussion)
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.