Skip to main content

2024 AMC 12B Problem 14

Problem 14 of 25IntermediateNumber Theory

How many different remainders can result when the 100100th power of an integer is divided by 125?125?

Answer choices

Show solution

Solution

If nn is coprime to 5,5, then since φ(125)=100,\varphi(125) = 100, Euler’s theorem gives n1001(mod125).n^{100} \equiv 1 \pmod{125}. If nn is a multiple of 5,5, then n100n^{100} is divisible by 5100,5^{100}, hence by 125,125, leaving remainder 0.0. So the only possible remainders are 00 and 1,1, which is 22 distinct values. Thus, the correct answer is B.

More practice

Concepts: Euler’s Totient Function · modular exponentiation

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.