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
  math, but I think it is over your head now.) 

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.
  That number is your solution.

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/