Problem:
How many different remainders can result when the 100th power of an integer is divided by 125 ?
Answer Choices:
A. 1
B. 2
C. 5
D. 25
E. 125
Solution:
Write N=5k+r for r=0,1,2, 3, or 4. If r=0, then N=5k and N100 is divisible by 125 , so the remainder is 0 . If r=1,2,3, or 4 , then N2=25k2+10rk+r2=5m±1 for some integer m. Now use the Binomial Theorem:
N100=(N2)50=(5m±1)50=(5m)50​±50(5m)49+(250​)(5m)48±⋯±(4750​)(5m)3+(4850​)(5m)2±50(5m)+1.​
All the terms except the final term have at least 3 factors of 5, so N100 has remainder 1 upon division by 125 . Therefore there are only (B)2​ possible remainders: 0 and 1.
OR
Let ϕ(n) be the number of positive integers less than n that are relatively prime to n; this is Euler's totient function. Then ϕ(125)=53−52=100. By Euler's Totient Theorem, if a is not a multiple of 5 , then a100≡1(mod125). If a is a multiple of 5 , then a100≡0(mod125). Therefore there are only (B)2​ possible remainders: 0 and 1.
The problems on this page are the property of the MAA's American Mathematics Competitions