Difference between revisions of "2021 AIME II Problems/Problem 13"

Latest revision as of 22:16, 26 January 2024

Problem

Find the least positive integer $n$ for which $2^n + 5^n - n$ is a multiple of $1000$ .

Solution 1

Recall that $1000$ divides this expression if $8$ and $125$ both divide it. It should be fairly obvious that $n \geq 3$ ; so we may break up the initial condition into two sub-conditions.

(1) $5^n \equiv n \pmod{8}$ . Notice that the square of any odd integer is $1$ modulo $8$ (proof by plugging in $1^2,3^2,5^2,7^2$ into modulo $8$ ), so the LHS of this expression goes $5,1,5,1,\ldots$ , while the RHS goes $1,2,3,4,5,6,7,8,1,\ldots$ . The cycle length of the LHS is $2$ , RHS is $8$ , so the cycle length of the solution is $\operatorname{lcm}(2,8)=8$ . Indeed, the $n$ that solve this congruence are exactly those such that $n \equiv 5 \pmod{8}$ .

(2) $2^n \equiv n \pmod{125}$ . This is extremely computationally intensive if we try to calculate all $2^1,2^2,\ldots,2^{100} \pmod{125}$ , so we take a divide-and-conquer approach instead. In order for this expression to be true, $2^n \equiv n \pmod{5}$ is necessary; it shouldn't take too long for us to go through the $20$ possible LHS-RHS combinations, considering that $n$ must be odd. We only need to test $10$ values of $n$ and obtain $n \equiv 3 \pmod{20}$ or $n \equiv 17 \pmod{20}$ .

With this in mind we consider $2^n \equiv n \pmod{25}$ . By the Generalized Fermat's Little Theorem, $2^{20} \equiv 1 \pmod{25}$ , but we already have $n$ modulo $20$ . Our calculation is greatly simplified. The LHS's cycle length is $20$ and the RHS's cycle length is $25$ , from which their least common multiple is $100$ . In this step we need to test all the numbers between $1$ to $100$ that $n \equiv 3 \pmod{20}$ or $n \equiv 17 \pmod{20}$ . In the case that $n \equiv 3 \pmod{20}$ , the RHS goes $3,23,43,63,83$ , and we need $2^n \equiv n \equiv 2^3 \pmod{25}$ ; clearly $n \equiv 83 \pmod{100}$ . In the case that $n \equiv 17 \pmod{20}$ , by a similar argument, $n \equiv 97 \pmod{100}$ .

In the final step, we need to calculate $2^{97}$ and $2^{83}$ modulo $125$ :

Note that $2^{97}\equiv2^{-3}$ ; because $8\cdot47=376\equiv1\pmod{125},$ we get $2^{97} \equiv 47\pmod{125}$ .

Note that $2^{83}$ is $2^{-17}=2^{-16}\cdot2^{-1}$ . We have $\begin{align*} 2^{-1}&\equiv63, \\ 2^{-2}&\equiv63^2=3969\equiv-31, \\ 2^{-4}&\equiv(-31)^2=961\equiv-39, \\ 2^{-8}&\equiv1521\equiv21, \\ 2^{-16}&\equiv441, \\ 2^{-17}&\equiv63\cdot441\equiv7\cdot(-31)=-217\equiv33. \end{align*}$ This time, LHS cycle is $100$ , RHS cycle is $125$ , so we need to figure out $n$ modulo $500$ . It should be $n \equiv 283,297 \pmod{500}$ .

Put everything together. By the second subcondition, the only candidates less than $1000$ are $283,297,783,797$ . Apply the first subcondition, $n=\boxed{797}$ is the desired answer.

~Ross Gao (Solution)

~MRENTHUSIASM (Minor Reformatting)

Solution 2

We have that $2^n + 5^n \equiv n\pmod{1000}$ , or $2^n + 5^n \equiv n \pmod{8}$ and $2^n + 5^n \equiv n \pmod{125}$ by CRT. It is easy to check $n < 3$ don't work, so we have that $n \geq 3$ . Then, $2^n \equiv 0 \pmod{8}$ and $5^n \equiv 0 \pmod{125}$ , so we just have $5^n \equiv n \pmod{8}$ and $2^n \equiv n \pmod{125}$ . Let us consider both of these congruences separately.

First, we look at $5^n \equiv n \pmod{8}$ . By Euler's Totient Theorem (ETT), we have $5^4 \equiv 1 \pmod{8}$ , so $5^5 \equiv 5 \pmod{8}$ . On the RHS of the congruence, the possible values of $n$ are all nonnegative integers less than $8$ and on the RHS the only possible values are $5$ and $1$ . However, for $5^n$ to be $1 \pmod{8}$ we must have $n \equiv 0 \pmod{4}$ , a contradiction. So, the only possible values of $n$ are when $n \equiv 5 \pmod{8} \implies n = 8k+5$ .

Now we look at $2^n \equiv n \pmod{125}$ . Plugging in $n = 8k+5$ , we get $2^{8k+5} \equiv 8k+5 \pmod{125} \implies 2^{8k} \cdot 32 \equiv 8k+5 \pmod{125}$ . Note, for $2^n \equiv n\pmod{125}$ to be satisfied, we must have $2^n \equiv n \pmod{5}$ and $2^n \equiv n\pmod{25}$ . Since $2^{8k} \equiv 1\pmod{5}$ as $8k \equiv 0\pmod{4}$ , we have $2 \equiv -2k \pmod{5} \implies k = 5m-1$ . Then, $n = 8(5m-1) + 5 = 40m-3$ . Now, we get $2^{40m-3} \equiv 40m-3 \pmod{125}$ . Using the fact that $2^n \equiv n\pmod{25}$ , we get $2^{-3} \equiv 15m-3 \pmod{25}$ . The inverse of $2$ modulo $25$ is obviously $13$ , so $2^{-3} \equiv 13^3 \equiv 22 \pmod{25}$ , so $15m \equiv 0 \pmod{25} \implies m = 5s$ . Plugging in $m = 5s$ , we get $n = 200s - 3$ .

Now, we are finally ready to plug $n$ into the congruence modulo $125$ . Plugging in, we get $2^{200s-3} \equiv 200s - 3 \pmod{125}$ . By ETT, we get $2^{100} \equiv 1 \pmod{125}$ , so $2^{200s- 3} \equiv 2^{-3} \equiv 47 \pmod{125}$ . Then, $200s \equiv 50 \pmod{125} \implies s \equiv 4 \pmod{5} \implies s = 5y+4$ . Plugging this in, we get $n = 200(5y+4) - 3 = 1000y+797$ , implying the smallest value of $n$ is simply $\boxed{797}$ .

~rocketsri

Solution 3 (Chinese Remainder Theorem and Binomial Theorem)

We wish to find the least positive integer $n$ for which $2^n+5^n-n\equiv0\pmod{1000}.$ Rearranging gives $2^n+5^n\equiv n\pmod{1000}.$ Applying the Chinese Remainder Theorem, we get the following system of congruences: $\begin{align*} 2^n+5^n &\equiv n \pmod{8}, \\ 2^n+5^n &\equiv n \pmod{125}. \end{align*}$ It is clear that $n\geq3,$ from which we simplify to $\begin{align*} 5^n &\equiv n \pmod{8}, \hspace{15mm} &(1) \\ 2^n &\equiv n \pmod{125}. &(2) \end{align*}$ We solve each congruence separately:

For $(1),$ quick inspections produce that $5^1,5^2,5^3,5^4,\ldots$ are congruent to $5,1,5,1,\ldots$ modulo $8,$ respectively. More generally, $5^n \equiv 5 \pmod{8}$ if $n$ is odd, and $5^n \equiv 1 \pmod{8}$ if $n$ is even. As $5^n$ is always odd (so is $n$ ), we must have $n\equiv5\pmod{8}.$
That is, $\boldsymbol{n=8r+5}$ for some nonnegative integer $\boldsymbol{r.}$

For $(2),$ we substitute the result from $(1)$ and simplify:

$\begin{align*} 2^{8r+5}&\equiv8r+5\pmod{125} \\ \left(2^8\right)^r\cdot2^5&\equiv8r+5\pmod{125} \\ 256^r\cdot32&\equiv8r+5\pmod{125} \\ 6^r\cdot32&\equiv8r+5\pmod{125}. \end{align*}$ Note that $5^3=125$ and $6=5+1,$ so we apply the Binomial Theorem to the left side: $\begin{align*} (5+1)^r\cdot32&\equiv8r+5\pmod{125} \\ \Biggl[\binom{r}{0}5^0+\binom{r}{1}5^1+\binom{r}{2}5^2+\phantom{ }\underbrace{\binom{r}{3}5^3+\cdots+\binom{r}{r}5^r}_{0\pmod{125}}\phantom{ }\Biggr]\cdot32&\equiv8r+5\pmod{125} \\ \left[1+5r+\frac{25r(r-1)}{2}\right]\cdot32&\equiv8r+5\pmod{125} \\ 32+160r+400r(r-1)&\equiv8r+5\pmod{125} \\ 32+35r+25r(r-1)&\equiv8r+5\pmod{125} \\ 25r^2+2r+27&\equiv0\phantom{r+5}\pmod{125}. \hspace{15mm} (*) \end{align*}$ Since $125\equiv0\pmod{5},$ it follows that $\begin{align*} 25r^2+2r+27&\equiv0\pmod{5} \\ 2r+2&\equiv0\pmod{5} \\ r&\equiv4\pmod{5}. \end{align*}$

That is, $\boldsymbol{r=5s+4}$ for some nonnegative integer $\boldsymbol{s.}$

Substituting this back into $(*),$ we get $\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*}$ As $10(s+6)$ is a multiple of $125,$ it has at least three factors of $5.$ Since $10$ contributes one factor, $s+6$ contributes at least two factors, or $s+6$ must be a multiple of $25.$ Therefore, the least such nonnegative integer $s$ is $19.$

Finally, combining the two results from above (bolded) generates the least such positive integer $n$ at $s=19:$ $\begin{align*} n&=8r+5 \\ &=8(5s+4)+5 \\ &=40s+37 \\ &=\boxed{797}. \end{align*}$ ~MRENTHUSIASM (inspired by Math Jams's 2021 AIME II Discussion)

Solution 4 (Minimal Computation)

$5^n \equiv n \pmod{8}$ Note that $5^n \equiv 5,1,5,1,...$ and $n \equiv 0,..,7$ so $n$ is periodic every $[2,8]=8$ . Easy to check that only $n\equiv 5 \pmod{8}$ satisfy. Let $n=8a+5$ . Note that by binomial theorem, $2^{8a+5}=32\cdot 2^{8a} \equiv 7(1+15)^{2a} \equiv 7(1+30a)\pmod{25}$ So we have $7(1+30a) \equiv 8a+5\pmod{25} \implies 202a \equiv 23 \implies 2a \equiv 23+25 \implies a \equiv 24 \pmod{25}$ . Combining $a\equiv 24\pmod{25}$ with $n \equiv 5 \pmod{8}$ gives that $n$ is in the form of $197+200k$ , $n=197,397,597,797$ . Note that since $\phi(125)=100$ $2^{197+200k} \equiv 2^{197} \equiv 2^{-3} \equiv \underbrace{47}_{\text{Extended Euclidean Algorithm}}\pmod{125}$ Easy to check that only $\boxed{797}\equiv 47\pmod{125},{1797}\equiv 47\pmod{125},{2797}\equiv 47\pmod{125},...$

~Afo

Solution 5 (STEP by step transform)

1. The desired $n$ has the form $n = m + 20l + 100p,$ where $m, l, p$ are integers and $m < 20.$

Really: $(2^{m+ 20} – (m + 20)) – (2^m – m) = (2^{m+ 20} – 2^m) – 20.$ The first term is a multiple of $100$ (Claim).

We denote step an increase in $m$ by 20. At each step, the divisibility by $10$ is preserved, the number of tens is reduced by $2$ .

$(2^{m+ 100} – (m + 100)) – (2^m – m) = (2^{m+ 100} – 2^m) – 100.$ We denote STEP an increase in $m$ by $100.$ At each STEP, the first term is a multiple of $1000,$ which means that at each STEP the divisibility by $100$ is preserved, the number of hundreds decreases by $1.$

2. If the expression $2^n + 5^n – n$ is a multiple of $1000,$ the number $n$ is odd ( $2^n$ is even, $5^n$ is odd), which means that $5^n$ ends in $125.$ Therefore, the number $2^n – n$ ends in $875.$

3. $2^3 – 3 = 8 – 3 = 5.$ The tens digit is even $(0),$ it cannot be transformed into $7$ in several steps, since at each step this digit changes by $2.$

$17 = 20 – 3,$ so $2^{17} + 2^3$ is a multiple of $10,$ $(2^{17} – 17) + (2^3 – 3) = 2^{17} + 2^3 – 20$ is a multiple of $10.$ $2^{17} \pmod {100} = ((2^{10} \pmod {100}) \cdot (2^7 \pmod {100})) \pmod {100} = (24 \cdot 28) \pmod {100} = 72.$ $(2^{17} – 17 ) \pmod {100} = 55.$ The tens digit $5$ is odd, subtracting $2$ at each step in $4$ steps of $20$ will turn it into $7.$ So $(2^{97} – 97 ) \pmod {100} = 75.$ $2^{97} \pmod {1000} = ((2^{49} \pmod {1000}) \cdot 2^7) \pmod {1000} = 672.$ $(2^{97} – 97 ) \pmod {1000} = 575.$ We transform $5$ into $8$ in $7$ STEPS, so $(2^{797} – 797 ) \pmod {1000} = 875.$ $(5^{797} + 2^{797} – 797 ) \pmod {1000} = 0.$ Note, that for $n = 797 + 1000k, k$ is an integer, the expression $2^n + 5^n – n$ is a multiple of $1000.$

Claim

The numbers $2^{n+2\cdot 5^k}+2^n=2^n(2^{2\cdot 5^k}+1)$ and $2^{n+4\cdot 5^k}-2^n=2^n(2^{4\cdot 5^k}-1)$

are a multiple of $10^{k+1}$ for any $n > k$ , where $n,k$ are an integer.

Proof

First, if $m \pmod{10} \equiv 4,$ then $(m^4 – m^3 + m^2 – m + 1) \pmod{10} \equiv 6 – 4 + 6 – 4 + 1 = 5.$

$2^{4n+2}\pmod{10} \equiv 4.$ So, if the number $2^{4n+2} + 1$ is a multiple of $5^k$ , then $2^{20n+10} + 1$ is a multiple of $5^{k +1}.$

Really, denote $m = 2^{4n+2},$ then, $2^{20n+10} + 1 = m^5 + 1 = (m + 1)\cdot (m^4 – m^3 + m^2 – m + 1).$

The first factor is a multiple of $5^k$ , the second factor is a multiple of $5.$ Their product is a multiple of $5^{k +1}.$

For odd $n,$ using Newton's binomial for $4^n$ , we get $2^{2n} + 1$ is a multiple of $5.$ $\begin{align*} 2^{2n} + 1 = 4^n + 1 = (5 - 1)^n + 1 = 5^n -n\cdot 5^{n-1} +...+5n\end{align*}$ If $n = 5^k,$ then $n > k,$ each term is a multiple of $5n$ .

Therefore, the number $4^{5^k}+1$ is a multiple of $5^{k+1}$ and $2^{k+1} (2^{2\cdot 5^k}+1)$ is a multiple of $10^{k+1}$ .

The difference $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)$ is a multiple of $10^{k+1}.$

vladimir.shelomovskii@gmail.com, vvsss

Note

If you are wondering, $\frac{2^{797}+5^{797}-797}{1000}$ is equal to the following $555$ -digit number:

$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.$

Video Solution by Interstigation

Did not use any advanced method, easily understandable:

https://youtu.be/ThF67J8iaS0

~Interstigation

@@ Line 4: / Line 4: @@
 ==Solution 1==
-divides this expression iff 8, 125 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.
+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 1 modulo 8 (why?), 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 <math>lcm(2,8)=8</math>. Indeed, the n that solve this equation 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>.
-(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^{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 20 possible LHS-RHS combinations and convince yourself that <math>n \equiv 3 \pmod{20}</math> or <math>n \equiv 17 \pmod{20}</math>.
+(2) <math>2^n \equiv n \pmod{125}</math>. This is extremely computationally intensive if we try to calculate all <math>2^1,2^2,\ldots,2^{100} \pmod{125}</math>, so we take a divide-and-conquer approach instead. 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 us to go through the <math>20</math> possible LHS-RHS combinations, considering that <math>n</math> must be odd. We only need to test <math>10</math> values of <math>n</math> and obtain <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> modulo 25. By the generalized Fermat's little theorem, <math>2^{20} \equiv 1 \pmod{25}</math>, 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 <math>n \equiv 3 \pmod{20}</math> or <math>n \equiv 17 \pmod{17}</math>. In the case that <math>n \equiv 3 \pmod{20}</math>, <math>2^n \equiv 2^3 \equiv 8</math>, and RHS goes "3,23,43,63,83"; 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>.
+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's cycle length is <math>20</math> and the RHS's cycle length is <math>25</math>, from which their least common multiple 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}, 2^{83}</math> modulo 125. The former is simply <math>2^{-3}</math>; because <math>8*47=376=1</math> modulo 125, <math>2^{97} \equiv 47</math>. <math>2^{83}</math> is <math>2^{-17}=2^{-16}*2^{-1}</math>. <math>2^{-1}=63,2^{-2}=63^2=3969=-31,2^{-4}=(-31)^2=961=-39,2^{-8}=1521=21, 2^{-16}=441,2^{-17}=63*441=7*{-31}=-217=33</math>. This time, LHS cycle is 100, RHS cycle is 125, so we need to figure out what is n modulo 500. It should be <math>n \equiv 283,297 \pmod{500}</math>.
+In the final step, we need to calculate <math>2^{97}</math> and <math>2^{83}</math> modulo <math>125</math>:
-Put everything together. By the second subcondition, the only candidates < 100 are <math>283,297,782,797</math>. Apply the first subcondition, n=797 is the desired answer.
+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>.
--Ross Gao
+Note that <math>2^{83}</math> is <math>2^{-17}=2^{-16}\cdot2^{-1}</math>. We have
+<cmath>\begin{align*}
+^{-1}&\equiv63, \\
+^{-2}&\equiv63^2=3969\equiv-31, \\
+^{-4}&\equiv(-31)^2=961\equiv-39, \\
+^{-8}&\equiv1521\equiv21, \\
+^{-16}&\equiv441, \\
+^{-17}&\equiv63\cdot441\equiv7\cdot(-31)=-217\equiv33.
+\end{align*}</cmath>
+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 less than <math>1000</math> are <math>283,297,783,797</math>. Apply the first subcondition, <math>n=\boxed{797}</math> is the desired answer.
+~Ross Gao (Solution)
+~MRENTHUSIASM (Minor Reformatting)
 ==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.
 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 26: / 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 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)==
+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*}
+^n+5^n &\equiv n \pmod{8}, \\
+^n+5^n &\equiv n \pmod{125}.
+\end{align*}</cmath>
+It is clear that <math>n\geq3,</math> from which we simplify to
+<cmath>\begin{align*}
+^n &\equiv n \pmod{8}, \hspace{15mm} &(1) \\
+^n &\equiv n \pmod{125}. &(2)
+\end{align*}</cmath>
+We solve each congruence separately:
+<ol style="margin-left: 1.5em;">
+  <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>
+  <li>For <math>(2),</math> we substitute the result from <math>(1)</math> and simplify:</li>
+<cmath>\begin{align*}
+^{8r+5}&\equiv8r+5\pmod{125} \\
+\left(2^8\right)^r\cdot2^5&\equiv8r+5\pmod{125} \\
+^r\cdot32&\equiv8r+5\pmod{125} \\
+^r\cdot32&\equiv8r+5\pmod{125}.
+\end{align*}</cmath>
+Note that <math>5^3=125</math> and <math>6=5+1,</math> so we apply the Binomial Theorem to the left side:
+<cmath>\begin{align*}
+(5+1)^r\cdot32&\equiv8r+5\pmod{125} \\
+\Biggl[\binom{r}{0}5^0+\binom{r}{1}5^1+\binom{r}{2}5^2+\phantom{ }\underbrace{\binom{r}{3}5^3+\cdots+\binom{r}{r}5^r}_{0\pmod{125}}\phantom{ }\Biggr]\cdot32&\equiv8r+5\pmod{125} \\
+\left[1+5r+\frac{25r(r-1)}{2}\right]\cdot32&\equiv8r+5\pmod{125} \\
++160r+400r(r-1)&\equiv8r+5\pmod{125} \\
++35r+25r(r-1)&\equiv8r+5\pmod{125} \\
+r^2+2r+27&\equiv0\phantom{r+5}\pmod{125}. \hspace{15mm} (*)
+\end{align*}</cmath>
+Since <math>125\equiv0\pmod{5},</math> it follows that
+<cmath>\begin{align*}
+r^2+2r+27&\equiv0\pmod{5} \\
+r+2&\equiv0\pmod{5} \\
+r&\equiv4\pmod{5}.
+\end{align*}</cmath>
+<i><b>That is, <math>\boldsymbol{r=5s+4}</math> for some nonnegative integer <math>\boldsymbol{s.}</math></b></i><p>
+Substituting this back into <math>(*),</math> we get
+<cmath>\begin{align*}
+(5s+4)^2+2(5s+4)+27&\equiv0\pmod{125} \\
+s^2+1010s+435&\equiv0\pmod{125} \\
+s+60&\equiv0\pmod{125} \\
+(s+6)&\equiv0\pmod{125}.
+\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, <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>
+Finally, combining the two results from above (bolded) generates the least such positive integer <math>n</math> at <math>s=19:</math>
+<cmath>\begin{align*}
+n&=8r+5 \\
+&=8(5s+4)+5 \\
+&=40s+37 \\
+&=\boxed{797}.
+\end{align*}</cmath>
+~MRENTHUSIASM (inspired by Math Jams's <b>2021 AIME II Discussion</b>)
+==Solution 4 (Minimal Computation)==
+<cmath>5^n \equiv n \pmod{8}</cmath>
+Note that <math>5^n \equiv 5,1,5,1,...</math> and <math>n \equiv 0,..,7</math> so <math>n</math> is periodic every <math>[2,8]=8</math>. Easy to check that only <math>n\equiv 5 \pmod{8}</math> satisfy. Let <math>n=8a+5</math>. Note that by binomial theorem,
+<cmath>2^{8a+5}=32\cdot 2^{8a} \equiv 7(1+15)^{2a} \equiv 7(1+30a)\pmod{25}</cmath>
+So we have <math>7(1+30a) \equiv 8a+5\pmod{25} \implies 202a \equiv 23 \implies 2a \equiv 23+25 \implies a \equiv 24 \pmod{25}</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>
+Easy to check that only <math>\boxed{797}\equiv 47\pmod{125},{1797}\equiv 47\pmod{125},{2797}\equiv 47\pmod{125},...</math>
+~Afo
+==Solution 5 (STEP by step transform)==
+. 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>
+. 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>
+. <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>
+Their product is a multiple of  <math>5^{k +1}.</math>
+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{,} \\
+{,}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{,} \\
+{,}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{,} \\
+{,}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{,} \\
+{,}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{,} \\
+{,}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{,} \\
+{,}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}}
 {{MAA Notice}}

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

Page

Toolbox

Search