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$.

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}$.