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

- 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
Math Forum Home || Math Library || Quick Reference || Math Forum Search