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