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

### 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/
```
Associated Topics:
College Number Theory
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

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/