2024 AMC 12B Problem 14

Problem 14 of 25IntermediateNumber Theory

How many different remainders can result when the

100

th power of an integer is divided by

125?

Show solution

Solution

n

is coprime to

5,

then since

\varphi(125) = 100,

Euler’s theorem gives

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

n

is a multiple of

5,

then

n^{100}

is divisible by

5^{100},

hence by

125,

leaving remainder

0.

So the only possible remainders are

0

and

1,

which is

2

distinct values. Thus, the correct answer is B.

Tagged: Euler’s Totient Function · modular exponentiation