Remainder when Dividing Large NumbersDate: 04/17/2001 at 03:47:50 From: Ooi Chin Wah Subject: Number theory Find the remainder when (12371^56 + 34)^28 is divided by 111. Thanks. Date: 04/17/2001 at 12:02:42 From: Doctor Rob Subject: Re: Number theory Thanks for writing to Ask Dr. Math. 111 = 3*37. Solve the problem for 3 and 37, then combine the answers. 12371 = -1 (mod 3) so 12371^56 = (-1)^56 = 1 (mod 3) Then 12371^56 + 34 = -1 (mod 3), and so (12371^56 + 34)^28 = (-1)^28 = 1 (mod 3) Now for the modulus 37, 12371 = 13 (mod 37) 12371^56 = 13^56 (mod 37) To find 13^56, compute in order 13^i where i = 1, 2, 3, 6, 7, 14, 28, and 56, by, at each step, either squaring or multiplying by 13. Reduce modulo 37 after each step. That keeps the numbers small. That gives you 12371^56 = 16 (mod 37) Now add 34, and you are back to powers of 13. Notice that you have 13^28 already calculated as the next-to-last step of the previous computation. Now find a number less than 111 that is congruent to 33 modulo 37 and congruent to 1 modulo 3, and you'll have your answer. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/