2024 AMC 10B Problem 18

Since $125 = 5 \cdot 5 \cdot 5$, whether $n$ has a factor of $5$ matters most. Split into two cases.

Case 1: $n$ is a multiple of $5$.

1. Then $n^3$ has at least three factors of $5$, so it is a multiple of $125$. So $n^{100}$ is too, and the remainder is $0$.

Case 2: $n$ is not a multiple of $5$.

2. Look at fourth powers first. For $n = 1, 2, 3, 4$: $1^4 = 1$, $2^4 = 16$, $3^4 = 81$, $4^4 = 256$. Each is $1$ more than a multiple of $5$. Since only the remainder of $n$ when divided by $5$ matters here, this holds for every $n$ that is not a multiple of $5$. So
$$n^4 = 1 + 5k \text{ for some whole number } k.$$
3. Now raise to the $5$th power. Multiplying out $(1 + a)^5$ gives
$$(1 + a)^5 = 1 + 5a + 10a^2 + 10a^3 + 5a^4 + a^5.$$
Put $a = 5k$. The term $5a = 25k$ is a multiple of $25$, and every later term contains $a^2 = 25k^2$ or more, so it is also a multiple of $25$. So
$$n^{20} = (1 + 5k)^5 = 1 + 25j \text{ for some whole number } j.$$
(Example: $2^{20} = 1048576 = 1 + 25 \cdot 41943$.)
4. Do it once more with $a = 25j$. Now $5a = 125j$ is a multiple of $125$, and $a^2 = 625j^2$ is also a multiple of $125$. So
$$n^{100} = (1 + 25j)^5 = 1 + (\text{a multiple of } 125),$$
and the remainder is $1$.

Counting.

1. Every $100$th power leaves remainder $0$ or $1$, and both happen: $5^{100}$ gives $0$ and $1^{100}$ gives $1$. So there are exactly $2$ remainders.

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

If a number is $1$ more than a multiple of $5$, then its $5$th power is $1$ more than a multiple of $25$, and the $5$th power of that is $1$ more than a multiple of $125$. The exponent $100 = 4 \cdot 5 \cdot 5$ was picked to fit this chain exactly: the $4$ gets you to "$1$ more than a multiple of $5$", and each $5$ adds one more factor of $5$.