Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m (→‎Solution 1)
(→‎Solution 1)
 
(29 intermediate revisions by 5 users not shown)
Line 4: Line 4:
 
==Solution 1==
 
==Solution 1==
  
−
<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.
+
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,\cdots</math>, while the RHS goes <math>1,2,3,4,5,6,7,8,1,\cdots</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>\mathrm{lcm}(2,8)=8</math>. Indeed, the <math>n</math> 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,\cdots,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>.  
+
(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 \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 2^3 = 8 \equiv n \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>.  
+
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}</math> and <math>2^{83}</math> modulo <math>125</math>:
 
In the final step, we need to calculate <math>2^{97}</math> and <math>2^{83}</math> modulo <math>125</math>:
Line 27: Line 27:
 
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>.
 
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,782,797</math>. Apply the first subcondition, <math>n=\boxed{797}</math> is the desired answer.
+
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)
 
~Ross Gao (Solution)
Line 35: Line 35:
 
==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 41: 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 systems of linear congruences:
+
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 56: 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,\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>
+
   <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 88: 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, it follows that <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>
+
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 106: 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 5 (STEP by step transform)==
 +
 +
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>
 +
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{,} \\
 +
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 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:

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

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

    3. \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

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_13&oldid=213333"