Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Last 3 digits of 3^400

  1. Feb 18, 2010 #1
    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?

    thanks in adavnce
     
  2. jcsd
  3. Feb 18, 2010 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  4. Feb 18, 2010 #3
    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?
     
  5. Feb 18, 2010 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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
  6. Feb 18, 2010 #5
    Are the powers of 5 easy because (5,1000)=1 so you can use Euler's Theorem?
     
  7. Feb 18, 2010 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  8. Feb 18, 2010 #7
    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....
     
  9. Feb 18, 2010 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook