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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.