Homework Help: Last 3 digits of 3^400

1. Feb 18, 2010

mcooper

1. The problem statement, all variables and given/known data

How can I find the last 1,2 and 3 digits of 3400?

3. The attempt at a solution

I know I have to find 3400 mod 10, 100 and 1000 but I want to know how to do this without a calculator. Do I have to use Euler's totient function?

2. Feb 18, 2010

Dick

All you need is 3^(400) mod 1000. That will give you the last three digits. Sure, use the totient function and Euler's theorem. I think it's the easiest way.

3. Feb 18, 2010

mcooper

Thanks alot! I am just wondering, when I get 3400= 1 mod 1000 by Euler's Theorem does that mean the last 3 digits are 001?

Also I kind of cheated a bit because I knew that phi(1000)=400. What can I use if I have a "random" number to calculate such as 5623? Would I just systematically go through, maybe using the the totient function and Euler's theorem, until I get something manageable?

4. Feb 18, 2010

Dick

Sure, if a number is equal to 1 mod 1000 then it's last three digits are 001. And 3^400 mod 1000 is a particularly easy case. 5^623 mod 1000 is harder. You could start with 5^4 mod 1000=625. Then to get 5^8 mod 1000, you square the 625 and take the result mod 1000. Then you can square again to get 5^16 mod 1000. You can get the exponent pretty high pretty fast. But it turns out the powers of 5 mod 1000 are pretty easy for another reason. Can you find it?

Last edited: Feb 18, 2010
5. Feb 18, 2010

mcooper

Are the powers of 5 easy because (5,1000)=1 so you can use Euler's Theorem?

6. Feb 18, 2010

Dick

How do you figure gcd(5,1000)=1??? You can't apply Euler's theorem. Just start looking at increasing powers of 5 mod 1000. There's a simple pattern.

7. Feb 18, 2010

mcooper

Sorry thats poor, its been a long day/night. All powers of 5 are congruent to 625 mod 1000 (hence 25 mod 100). Kind of weird but kind of cool. Is there a mathematical reason/proof for this? mod 10000 they are not all the same....

8. Feb 18, 2010

Dick

That's not true. 5^4 is congruent to 125. 5^5 is conguent to 625. It's just because 125*5 is congruent to 625 and 625*5 is congruent to 125. They keep repeating.