Using Mod to Find Digits in Large Numbers

Date: 12/10/96 at 19:14:46
From: Mike Paulson
Subject: Solving exponential equations

I recently took a test for a high school math contest. The test was 
really hard and there is still one question that I do not understand, 
even though the answer sheet shows the process.

The problem was to find the last two digits in 1996^1996.

Obviously a calculator can't solve this - the number is too big. 
However, on the answer sheet they said that the problem could be done 
with: 1996^1996 (mod 100). I have no idea what the (mod 100) is, and 
I have looked everywhere to find an answer.

They then rewrote the equation as (-4)^1996 (mod 100), factored out 
the exponent, and solved the equation by getting rid of all the 
numbers except the tens and ones digit after every step.  They ended 
up with an answer of 96.

Could you please tell me what the (mod 100) means, and how to use this
to change the equation to (-4)^1996? 

Sincerely,

Mike Paulson
Ravenna, Michigan

Date: 12/11/96 at 20:58:13
From: Doctor Rob
Subject: Re: solving exponential equations

The notation (mod 100) is common in a branch of mathematics called 
number theory.  It refers to so-called "modular arithmetic."
When it is taught in school, it is often called "clock arithmetic."

The idea is the same as the one found in "casting out nines," except
you will be "casting out hundreds." The idea is that if you do
addition, subtraction, or multiplication, you can discard multiples
of 100 either before or after the operation, or both, and you will
get an answer that differs from the ordinary operation answer only by
a multiple of 100.

The notation is as follows: If m is a positive whole number, and 
a and b are any whole numbers, then we write a = b (mod m) 
if and only if m divides a - b.  It is easy to see that:

(1) a = a (mod m).
(2) If a = b (mod m), then b = a (mod m).
(3) If a = b (mod m) and b = c (mod m), then a = c (mod m).
(4) If a = b (mod m) and c = d (mod m), then a + c = b + d (mod m).
(5) If a = b (mod m) and c = d (mod m), then a - c = b - d (mod m).
(6) If a = b (mod m) and c = d (mod m), then a * c = b * d (mod m).

You can figure out why it is that when we are only interested in the
last two decimal digits of a whole number, we can work (mod 100).  
You can also figure out why -4 = 1996 (mod 100).

Now you can use the facts (1)-(6) (especially (6)) above to compute
1996^1996 (mod 100), as in the solution to the problem provided with
the test.

-Doctor Rob,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/