2024 AMC 10B Problem 18

How many different remainders can result when the

100

th power of an integer is divided by

125?

Show solution

Solution

Here

125 = 5^3

and

\varphi(125) = 100.

\gcd(n, 5) = 1,

Euler’s theorem gives

n^{100} \equiv 1 \pmod{125}.

And if

n

is divisible by

5,

then

n^{100}

carries a factor of

5^{100},

hence of

125,

n^{100} \equiv 0 \pmod{125}.

That leaves only two possible remainders,

0

and

1.

Therefore, the answer is B.

Tagged: Euler’s Totient Function · modular exponentiation · casework