Finding Last Digits of 3400: Without Calculator or Euler's Totient Function

[mcooper]

Homework Statement

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

The Attempt at a Solution

I know I have to find 3⁴⁰⁰ 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?

thanks in adavnce

 

[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.

 

[mcooper]

Thanks a lot! I am just wondering, when I get 3⁴⁰⁰= 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 5⁶²³? Would I just systematically go through, maybe using the the totient function and Euler's theorem, until I get something manageable?

 

[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?

 

[mcooper]

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

 

[Dick]

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

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.

 

[mcooper]

Sorry that's 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...

 

[Dick]

Sorry that's 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...

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.