1. Not finding help here? Sign up for a free 30min 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!

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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Number Theory
  1. Number Theory (Replies: 7)

  2. Number Theory (Replies: 5)

  3. Number Theory (Replies: 2)

  4. Number theory question (Replies: 3)

Loading...