Associated Topics || Dr. Math Home || Search Dr. Math

### Division of Large Numbers

```
Date: 04/28/98 at 02:54:32
From: Luis Salazar
Subject: Division of large numbers

What is the remainder when 7^100 is divided by 13?
Give a general strategy with explanation for this type of problem.
```

```
Date: 06/24/98 at 16:07:36
From: Doctor Hauke
Subject: Re: Division of large numbers

Hi Luis,

Your problem refers to "computing modulo n," a very effective way to
handle large numbers.

a mod n means the remainder that a leaves when divided by n.
So, for example, 20 mod 13 = -19 mod 13 = 7 (20 and -19 differ by a
multiple of 13, namely 39 = 3*13. 7 and -19 differ by 2*13, and so on.

Can you give another number x with x mod 13 = 7 ?), or another
example: 4 mod 3 = -2 mod 3 = 998 mod 3 = 1? You say "4 is congruent
to 1 modulo 3."

When adding and multiplying modulo n, you can always replace a number
x by another number y as long as x is congruent to y modulo n:
(x*y) mod n = (x mod n) * (y mod n).

Example: Compute 11^2 mod 13.

First look at a smaller number.

11 mod 13 = -2 mod 13, because 11-(-2) = 1*13.

Now replace 11 with -2 everywhere:

11^2 mod 13 = (-2)^2 mod 13 = 4 mod 13 = 4.

Thus we conclude that 11^2 mod 13 = 4.
Check: 11^2 = 121 = 4+9*13, so indeed
11^2 and 4 differ by a multiple of 13.

For powers, you use "Fermat's little theorem":

n always divides a^n-a, or a^n mod n = a mod n.

(Check some examples! The proof of this is easy with a bit of higher

Now back to your problem: 7^100 mod 13 = ?

First we know that 13 divides 7^13-7 = 7*(7^12-1) as above.
13 of course doesn't divide 7, so it divides 7^12-1.
So 7^12 mod 13 = 1 mod 13.

Thus 7^24 mod 13 = (7^12*7^12) mod 13
= (7^12 mod 13)^2
= (1 mod 13)^2 = 1

And 7^36 mod 13  = (7^24*7^12) mod 13 = ... = 1

Can you complete the steps alone? You see this property will hold
for ANY multiple of 12.

7^96 mod 13 = 7^(8*12) mod 13 = 1. We are almost there.

So 7^100 mod 13 = 7^96 mod 13 * 7^4 mod 13 = 49^2 mod 13 = ...
(you can surely continue from here alone, hint: 52 = 4*13).

Just make sure that the number at the end lies between 0 and 12.

This was a rather long explanation (and thus took a bit for me to
write up), so write back if you still have questions.

-Doctor Hauke,  The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
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