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"

(→‎Solution)
(→‎Solution)
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^100=1 \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{17}</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^100=1 \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{17}</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</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>.  
  
−
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}, 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>.
  
 
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.
 
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.

Revision as of 15:45, 22 March 2021

Problem

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

Solution

1000 divides this expression iff 8, 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 (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 $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^100=1 \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{17}$.

With this in mind we consider $2^n \equiv n$ modulo 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{17}$. In the case that $n \equiv 3 \pmod{20}$, $2^n \equiv 2^3 \equiv 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*47=376=1$ modulo 125, $2^{97} \equiv 47$. $2^{83}$ is $2^{-17}=2{-16}*2^{-1}$. $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$. This time, LHS cycle is 100, RHS cycle is 125, so we need to figure out what is n modulo 500. It should be $n \equiv 283,297 \pmod{500}$.

Put everything together. By the second subcondition, the only candidates < 100 are $283,297,782,797$. Apply the first subcondition, n=797 is the desired answer.

-Ross Gao

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=149731"