2024 AMC 10B Problems/Problem 18

The following problem is from both the 2024 AMC 10B #18 and 2024 AMC 12B #14, so both problems redirect to this page.

Problem

How many different remainders can result when the $100$ th power of an integer is divided by $125$ ?

$\textbf{(A) } 1 \qquad\textbf{(B) } 2 \qquad\textbf{(C) } 5 \qquad\textbf{(D) } 25 \qquad\textbf{(E) } 125$

Solution 1

First note that the Euler's totient function of $125$ is $100$ . We can set up two cases, which depend on whether a number is relatively prime to $125$ .

If $n$ is relatively prime to $125$ , then $n^{100} \equiv 1 \pmod{125}$ because of Euler's Totient Theorem.

If $n$ is not relatively prime to $125$ , it must be have a factor of $5$ . Express $n$ as $5m$ , where $m$ is some integer. Then $n^{100} \equiv (5m)^{100} \equiv 5^{100}\cdot m^{100} \equiv 125 \cdot 5^{97} \cdot m^{100} \equiv 0 \pmod{125}$ .

Therefore, $n^{100}$ can only be congruent to $0$ or $1 \pmod{125}$ . Our answer is $\boxed{2}$ .

~lprado ~edit by Elephant200

Solution 2 (Euler Totient)

We split the cases into:

1. If $x$ is not a multiple of $5$ : we get $x^{100} \equiv 1 \pmod{125}$

2. If $x$ is a multiple of $5$ : Clearly the only remainder provides $0$

Therefore, the remainders can only be $1$ and $0$ , which gives the answer $\boxed{(B)2}$ .

~mitsuihisashi14 ~BS2012 (Minor corrections) ~andliu766

Solution 3 (No Totient)

Note that

$(5+n)^{100} = {100 \choose 0} 5^{100} + {100 \choose 1} 5^{99} n + {100 \choose 2} 5^{98} n^2 + \cdots + {100 \choose 97} 5^3 n^{97} + {100 \choose 98} 5^2 n^{98} + {100 \choose 99} 5 n^{99} + {100 \choose 100} n^{100}.$

Taking this mod $125$ , we can ignore most of the terms except the for the last $3$ :

${100 \choose 98} 5^2 n^{98} + {100 \choose 99} 5 n^{99} + {100 \choose 100} n^{100} \equiv 4950 \cdot 5^2 n^{98} + 100 \cdot 5 n^{99} + n^{100} \equiv n^{100} \pmod {125},$

so $(5+n)^{100} \equiv n^{100}$ . Substituting $-n$ for $n$ , we get $(5-n)^{100} \equiv n^{100}$ . Therefore, the remainders when divided by $125$ repeat every $5$ integers, so we only need to check the $100$ th powers of $0, 1, 2, 3, 4$ . But we have that $(5-1)^{100} \equiv 1^{100}$ and $(5-2)^{100} \equiv 2^{100}$ , so we really only need to check $0, 1, 2$ . We know that $0, 1$ produce different remainders, so the answer to the problem is either $2$ or $3$ . But $3$ is not an answer choice, so the answer is $\boxed{\textbf{(B) } 2}$ .

Solution 4 (Totient)

Euler's Totient Function, $\phi(n)$ returns $n\cdot\left(1-\dfrac{1}{x}\right)$ as a product of each prime divisor of $n$ .

Euler's Totient Theorem states that if ${a}$ is an integer and $p$ is a positive integer relatively prime to $a$ , then ${a}^{\phi (p)}\equiv 1 \pmod {p}$ .

In this case, $p=125$ , which is convenient because $125$ only has one prime factor, $5$ , therefore $\phi(125)=100$ , so $a^{100}\equiv1\pmod{125}$ where $\gcd(a,125)=1$ . Every single number that isn't a multiple of $5$ is relatively prime to $125$ , therefore we have two cases:

1) $a\%5\neq0\implies a^{100}\equiv1\pmod{125}$

2) $a\%5=0\implies a^{100}=5^3\cdot x\implies a^{100}\equiv0\pmod{125}$

The answer is $\boxed{\text{(B) }2}$ ~Tacos_are_yummy_1

Solution 5 (Binomial Theorem)

~Kathan

Solution 6(Euler's theorem)

We have that $125=5^3,$ so the only prime factor of $125$ is $5.$ Let the positive integer be $x,$ then we have two cases:

The first is if $x \equiv 5 \pmod{125},$ then $x^{100}\equiv 5^{100} \equiv 0 \pmod{125}.$

The second is if $x \not\equiv 5 \pmod{125},$ in which we can conclude that $\gcd(x,125)=1.$ Using Euler's theorem(proven below), we have that $x^{\phi(125)}\equiv 1 \pmod{125}.$ The clever part about this is that $\phi(125)=100,$ since for every $5$ positive integers starting from $1$ , $4$ are coprime with $125$ (since it only has $5$ as a prime factor). Then $\frac{4}{5}\cdot 125 =100,$ so $x^{100}\equiv 1\pmod{125}$ in this case. Therefore there are only $\boxed{2}$ possible remainders.

Solution 7 (Guess)

(Do not use this solution unless you are low on time or do not know how to solve this problem.) Notice that all the answer choices are odd and have some relationship to the number $5$ except for $2$ . $2$ doesn't seem to fit in with the other answer choices, so the test writers likely put it there because they had to. You can assume that it is the answer: $\boxed{\textbf{(B)} 2}$ .

Written by ChristianZhang

Video Solution 1 by Pi Academy (Fast and Easy ⚡🚀)

https://youtu.be/c6nhclB5V1w?feature=shared

~ Pi Academy

Video Solution 2 (Fast!)

https://www.youtube.com/watch?v=S7l_Yv2Sd7E

2024 AMC 10B (Problems • Answer Key • Resources)
Preceded by Problem 17	Followed by Problem 19
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions

2024 AMC 12B (Problems • Answer Key • Resources)
Preceded by Problem 13	Followed by Problem 15
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

Page

Toolbox

Search