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

Revision as of 13:28, 16 July 2021

Problem

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

Solution 1

$1000$ divides this expression iff $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,\cdots$ , while the RHS goes $1,2,3,4,5,6,7,8,1,\cdots$ . The cycle length of the LHS is $2$ , RHS is $8$ , so the cycle length of the solution is $\mathrm{lcm}(2,8)=8$ . Indeed, the $n$ that solve this equation are exactly those such that $n \equiv 5 \pmod{8}$ .

(2) $2^n \equiv n \pmod{125}$ . This is extremely computationally intensive if you try to calculate all $2^1,2^2, ..., 2^{100} \pmod{125}$ , so instead, we take a divide-and-conquer approach. In order for this expression to be true $2^n \equiv n \pmod{5}$ is necessary; it shouldn't take too long for you to go through the $20$ possible LHS-RHS combinations and convince yourself that $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 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 $n \equiv 3 \pmod{20}$ or $n \equiv 17 \pmod{20}$ . In the case that $n \equiv 3 \pmod{20}$ , $2^n \equiv 2^3 = 8$ , and RHS goes $3,23,43,63,83$ ; 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}, 2^{83}$ modulo $125$ . The former is simply $2^{-3}$ ; because $8\cdot47=376\equiv1\pmod{125},$ $2^{97} \equiv 47\pmod{125}$ . $2^{83}$ is $2^{-17}=2^{-16}\cdot2^{-1}$ . $\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,782,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 systems of linear 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,\cdots$ are congruent to $5,1,5,1,\cdots$ 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, it follows that $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}$

~Afo

@@ Line 10: / Line 10: @@
 (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 <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 \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>, <math>2^n \equiv 2^3 = 8</math>, and RHS goes <math>3,23,43,63,83</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>.
+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>, <math>2^n \equiv 2^3 = 8</math>, and RHS goes <math>3,23,43,63,83</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 <math>125</math>. The former is simply <math>2^{-3}</math>; because <math>8\cdot47=376\equiv1\pmod{125},</math> <math>2^{97} \equiv 47\pmod{125}</math>. <math>2^{83}</math> is <math>2^{-17}=2^{-16}\cdot2^{-1}</math>.

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