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: Number Theory

  1. Aug 28, 2005 #1
    I have got another question, this time involving the Euler's Theorem:

    a^(phi(m)) is congruent to 1 (mod m)

    The question is calculate

    7^40002 mod 1000

    I could only reduce it to

    7^402 mod 1000

    What should I do now?

    Thanks
     
  2. jcsd
  3. Aug 28, 2005 #2

    lurflurf

    User Avatar
    Homework Helper

    Again with the vague theorem referrence. This time you clearly mean Eulers Totient Theorem. Why not reduce once more?
    we have 7 relatively prime to 1000.
    phi(1000)=1000-1000/2-1000/5+1000/10=1100-700=400
    so (all mod 1000)
    7^400=1
    7^40002=((7^400)^100)(7^2)=(1^100)(7^2)=7^2=49
     
  4. Aug 28, 2005 #3
    Thanks lurlurf, I didn't apply the Euler Totient theorem fully but I have another one

    11^100 (mod 72)

    This time I reduced it to 11^4 (mod 72)

    I could evaluate it by hand which works out to be 7^4 (mod 72) but is there a better way of doing it.

    Thanks
     
  5. Aug 28, 2005 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    11^4 is 121^2 and you can reduce 121 can't you? so 99^2 then, which is (40+9)^2 whcih is quite easy to work out and reduce esp since 72 divides 1440, hence 1512 and thus 1584 so it's what?

    6+2.40.9+81=6+9=15
     
  6. Aug 28, 2005 #5

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Wait a minute :

    11^4 = 121^2 == (-23)^2 = 529 =(72*7) + 25

    So, 11^4 == 25 (mod 72)....no?
     
  7. Aug 28, 2005 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    oh i don't claim to have got the arithmetic right, only the method. i am a mathematician after all. i know how to solve it, doesn't mean i can get it rgight when i try.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook