What remainders can result when the 100th power of an integer is divided by 125?

Answer 1

It depends on the integer. Consider the integer (5n+x), where 1 <= x <= 4
(5+x)^100 = x^100 + 100*x^99 * 5n + ...
= x^100 + 125k


So the possible remainders repeat themselves after every multiple of 5.

For x = 1, the remainder is 1.

For x = 2,
2^7 = 128 = 3 + 125
2^98 = (2^7)^14
= 3^14 + 125k
2^100 = 4*3^14 + 125m
4*3^14 gives a remainder of 1 when divided by 125.

For x = 3,
3^5 = 243 = 250 - 7
3^100 = (3^5)^20 = (-7)^20 + 125k
= 7^20 + 125k
7^20 = (2+5)^20
= 2^20 + 20*5*2^19 + 125k
2^20 + 20*5*2^19 has remainder 1.

For x=4,
4^4 = 256 = 250 + 6
4^100 = 6^25 + 125k
6^25 has the same remainder as 1^25 which is 1.

Conclusion:
If the integer is divisible by 5, the remainder is 0, otherwise the remainder is 1.
Maybe someone with better knowledge of number theory than I have can come up with a more efficient methodology.

Answer 2

Among 125 remainders 0,1,2, ...124 modulo 125
125 * 4/5 = 100 remainders are co-prime with 125.
They form multiplicative group of order 100 modulo 125.
(It follows from Euclidean algorithm for GCD)
Members of the group:
{1,2,3,4,6,7,8,9,11,12... 119,121,122,123,124}

Each such remainder a generates cyclic sub-group
{a^1, a^2, a^3 ... a^n=1}, and n must therefore divide 100:
nk = 100.

Then
a^100 = a^(nk) = (a^n)^k = 1^k = 1.

The rest of remainders which are multiples of 5, have 100th power divisible by 5^100, and therefore
(5m)^100 = 0 mod 125

Dr. D is right:
either 1 or 0.