Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Remainder when Dividing Large Numbers


Date: 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/   
    
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/