Finding the Last Digits of a Large ExponentialDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/