Finding the Last Digits of a Large Exponential

Date: 01/01/2005 at 17:26:03
From: bras
Subject: Calculating only the last few digits of large exponents

I have a copy of a question I found from an old magazine which seems 
easy but I cannot solve--here it is (word for word):

  George and his son are considering the powers of numbers.
  "What is 7^7, Son?"
  "My 10 digit calculator says it's 823543."
  "Can it calculate 7777777^7777777?"
  "You must be joking, Dad. That number must have millions of digits."
  "53,595,538 digits to be precise, but the last five will do."
 
  What are the last five digits of 7777777^7777777?

Calculating the number of digits is easy using logarithms, but how 
can I calculate the last five digits?  Any help will be appreciated.

Using some simple VBA I have calculated the last 5 digits to be 47697 
(I hope it is correct), but that is just number crunching.  How could
I do this using pen and paper (and perhaps the mentioned 10 digit
calculator)?

Since only 5 digits are required, the expression can be "simplified" 
to 77777^7777777, but that doesn't make it easier.

Date: 01/14/2005 at 10:04:28
From: Doctor Vogler
Subject: Re: Calculating only the last few digits of large exponents

Hi,

Thanks for writing to Dr. Math.  Calculating the last several digits 
of a large power is an exercise in modular arithmetic.  If you are
unfamiliar with the subject, you can start with

  Mod, Modulus, Modular Arithmetic
    http://mathforum.org/library/drmath/view/62930.html 

The idea is that you want

  7777777^7777777 (mod 100000).

As you (correctly) stated, this is the same as

  77777^7777777 (mod 100000).

In general, the efficient method for computing a modular exponent like
the one above is to start by repeatedly squaring, and reducing after
each square, recording only the last five digits, like so:

  77777^2 = 61729 (mod 100000)
  77777^4 = 61729^2 = 69441 (mod 100000)
  77777^8 = 69441^2 = 52481 (mod 100000)
  etc.

Then you see which powers you need, like so:

  77777 = 1 + 16 + 64 + 128 + 256 + 512 + 1024 + 2048 + 8192 + 65536

(This last is the same as writing the exponent in binary.)  And then
you multiply together the appropriate powers, reducing mod 100000
after each product, as in

  77777^77777 = 77777^1 * 77777^16 * 77777^64 * ....

Oh!  Except I forgot that you wanted the exponent 7777777 rather than
77777.  I'll let you convert that one into binary (or a sum of powers
of two).  Notice that each squaring and each product can be done on
the ten-digit calculator, since each is multiplying two five-digit
numbers.  Then you only record the last five digits, and you go on.

This technique is known by mathematicians as "modular exponentiation."

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/