Question

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

Answer 1

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.

Answer 2

Familiar with Euler generalization to Fermat's little theorem ?

Answer 3

Yes.

Answer 4

then we're done, simply use it :)

Answer 5

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}\]

Answer 6

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

Answer 7

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

Answer 8

np:)