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$

Fast Solution

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

Solution 1

First note that the 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

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 125: Clearly the only remainder provides 0

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

~mitsuihisashi14

Solution 3

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: