What are the possible remainders when the 100-th power of an integer is divided by 125? This is a solution from Yatir Halevi, Maccabim-Reut High School, Israel.

Every integer can be expressed in the following way: 5p+q, where p and q are certain integers and 0 ≤ q ≤ 4. Expanding 5p + q with the aid of the binomial theorem we get the general term:


ak =
100
k

 5100−kp100−kqk.

All the terms except the last one q100 are divisible by 125. What we get is a number of this sort: 125×something+q100. But we know that 0 ≤ q ≤ 4 so the remainder when the 100th power is divided by 125 is the same as the remainder for q100, with q = 0, 1, 2, 3, or 4.

If q=0 then q100=0; if q=1 then q100=1.

Let q=2; we want the remainder after 2100 is divided by 125, so we work modulo 125. Now 27=128 ≡ 3 where the symbol ' ≡ ' indicates that the numbers have the same remainder after division by 125. For q=3 it follows that 35 = 243 ≡ −7. Thus


2100 ≡ 22×27×14

≡ 4×314

≡ 4×34 ×35×2

≡ 4×34 ×2432

≡ 4×81×(−7)2

= 4×81×49

= 15876 ≡ 1

Similarly


3100 ≡ 35×20

≡ 24320

≡ (−7)20

≡ (−32)6×(−7)2

≡ 230 ×49

≡ 27 ×4×4 ×49

≡ 34 ×4 ×49

= 15876 ≡ 1

If q=4 then
q100 =
2100
 2
 
 ≡ 1.

So we can either get 0 or 1 as a remainder and we get 0 if the original number is a multiple of 5 and 1 otherwise.