1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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