2024 AMC 10B Problem 18

Split according to whether $5$ divides $n$.

Case 1: $5 \mid n$. Then $125 = 5^3$ divides $n^3$, so $n^{100}$ is a multiple of $125$ and the remainder is $0$.

Case 2: $5 \nmid n$. The fourth powers of $1, 2, 3, 4$ are $1, 16, 81, 256$, all $\equiv 1 \pmod 5$. So $n^4 = 1 + 5k$ for some integer $k$. Raise to the fifth power and expand with the binomial theorem:
$$(1 + 5k)^5 = 1 + 5 \cdot 5k + 10 \cdot 25k^2 + \cdots \equiv 1 \pmod{25},$$
because every term after the first is divisible by $25$. So $n^{20} = 1 + 25j$. The same expansion once more gives
$$n^{100} = (1 + 25j)^5 = 1 + 5 \cdot 25j + \cdots \equiv 1 \pmod{125}.$$
So every $n$ not divisible by $5$ gives remainder $1$.

Both remainders occur ($n = 5$ gives $0$, $n = 1$ gives $1$), so there are exactly $2$.

The answer is $\boxed{\textbf{(B)}\ 2}$.

This is Euler's theorem in disguise: $\varphi(125) = 100$, so $n^{100} \equiv 1 \pmod{125}$ for every $n$ coprime to $5$. Even without that theorem, the "lifting" idea is worth knowing: if $x \equiv 1 \pmod{p}$ then $x^p \equiv 1 \pmod{p^2}$, and each further $p$th power gains another factor of $p$ in the modulus. Exponents like $100 = 4 \cdot 5 \cdot 5$ are chosen to make this chain work.

• Assuming powers spread out over many residues (answering 25 or 125) instead of testing whether 100 is a multiple of the order of every unit mod 125.
• Forgetting the multiples of $5$ and answering $1$, or forgetting that $0$ and $1$ are genuinely different remainders.