Let a be a positive integer. Find all positive remainders when a^100 is divided by 125

Question

hitaro9 · Answer

So just by plugging in numbers in to wolfram alpha, it looks like the remainder is going to be 0 (for 5^n as a) and 1 (for all other numbers). I'm having trouble seeing why though.

ganeshie8 · Answer

Familiar with Euler generalization to Fermat's little theorem ?

hitaro9 · Answer

Yes.

ganeshie8 · Answer

then we're done, simply use it :)

ganeshie8 · Answer

when $a=5k$ we have 
$$a^{100}= (5k)^{100} \equiv  0 \pmod{125}$$

when $\gcd(a, 125) = 1$, by euler generelization to fermat's little thm we have
$$a^{\phi(125)}\equiv 1 \pmod{125}$$

ganeshie8 · Answer

not surprisingly $\phi(125) = \phi(5^3) = 5^3 - 5^2 = 100$

hitaro9 · Answer

Oh right. That makes sense. Lot simpler than I was thinking thank you.

ganeshie8 · Answer

np:)