Thursday, July 14, 2011
The remainder when 5^20 is divided by 7 is?
The other answers given here rely on brute force calculation; that really misses point, and wouldn't work if the exponent was for example 100000000000000. The better method is to use modular arithmetic. I'll work it out for you with explaining all the theory. 5^20 = (5^2)^10 = (25)^10, and 25 = 4 mod 7; that means 7 into 25 leaves a remainder of 4, so if all i care about is remainder when dividing by 7, I can replace 25 by 4, getting 4^10 = (4^2)^5 = 16^5 = 2^5 mod 7, since 16 = 2 mod 7. Now 2^5 is 32, which gives a remainder of 4 when divided by 7. Generally speaking, if you're using a calculator in this type of question, you're doing it wrong.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment