Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Last Four Digits of 5^64


Date: 03/27/2001 at 21:38:57
From: Nick Walmer
Subject: Four last digits of exponent

I have a little exponential problem; how to find the last four digits 
of 3^125, or 5^64, something like that which the exponent is an 
exponential number too.

Nick Walmer


Date: 03/28/2001 at 00:54:08
From: Doctor Schwa
Subject: Re: Four last digits of exponent

Hi Nick,

I'll work out 5^64 for you as an example. 5^64 is the same as if you 
take 5 squared, square that, square that, square that, square that, 
and square that. That is, you can get a 64th power by squaring 6 
times.

     5^1 ends in 0005
     5^2 ends in 0025

5^4 is the square of that, which ends in 0625, and now things get a 
little harder to square, but since

     (100n+25)^2 = 10000n^2 + 5000n + 625

the 10000n^2 doesn't affect the last four digits, and if n is even the 
5000n doesn't either, so 5^8 still ends in 0625, and then by the same 
logic, so does 5^16, 5^32, 5^64, and so on ... repeated squares will 
still end in 0625.

Maybe that was a little too easy. How about 3^125? Well,

     3^1 ends in 0003
     3^5 ends in 0243

Now what about that to the 5th power? Well, 5th powers are a little 
messier, aren't they? I don't think it's going to be easiest to take 
that to the 5th. Instead, I'd probably prefer to keep squaring. I can 
find out 3^125 by multiplying 3^64 * 3^32 * 3^16 * 3^8 * 3^4 * 3^1

     3^1 ends in 0003
     3^4 ends in 0081
     3^8 ends in 6561 (in fact it equals that)

3^16 is 6561 * 6561 which ends in 6721, 3^32 ends in 6721*6721 which 
ends in 1841, and 3^64 ends in 1841*1841 which ends in 9281, so 
multiplying 9281*1841*6721*6561*81*3 I find that 3^125 ends in 5443, 
or so my calculator tells me.

Still, that's not a particularly nice method, but I don't see any 
better way to find out the last four digits of 3^125. Then again, just 
because *I* don't see it doesn't mean it doesn't exist... if you find 
out any better way of solving this type of problem, please write back.

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


Date: 03/28/2001 at 09:56:38
From: Doctor Rob
Subject: Re: four last digits of exponent

Thanks for writing to Ask Dr. Math, Nick.

Probably the simplest way to find the last four digits of a^(b^c) is 
as follows.

Start with a. Raise it to the bth power, a^b, and reduce modulo 10000 
(that is, drop all but the last four digits) to get an intermediate 
answer, a[1].

Now take a[1]^b and reduce modulo 10000, to get a[2].

Now take a[2]^b and reduce modulo 10000, to get a[3].

Continue this until you have found a[c], your answer.

This works because a^(b^c) = a^(b*b*...*b) = ([(a^b)^b]...)^b, where 
there are c b's in the last two expressions, and because you can 
reduce all your work modulo 10000 as you go, never having to work with 
numbers of more than eight digits, or to keep intermediate results of 
more than four digits.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/   
    
Associated Topics:
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/