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

  2. jcsd
  3. Aug 28, 2005 #2


    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.
    so (all mod 1000)
  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.

  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. Aug 28, 2005 #5


    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