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/