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 26, 2005 #1
    The question is

    Use Fermat's Theorem to compute the following:

    [tex]99^{99} \equiv (mod 47)[/tex]

    I spent over an hour on it but could only reduce it to [tex]99^7 \equiv (mod 47) [/tex]

    I think I am missing something. So if you can help, it would be great. Please provide an explanation as well.

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

    lurflurf

    User Avatar
    Homework Helper

    You are missing something
    99=64+32+2+1
    find
    99^1 (mod 47)
    99^2 (mod 47)
    99^4 (mod 47)
    99^8 (mod 47)
    99^16 (mod 47)
    99^32 (mod 47)
    99^64 (mod 47)
    by repeated squaring
    then find
    (99^64)(99^32)(99^2)(99^1) (mod 47)
    recall that at each step you may reduce mod 47 so in no step do you need to compute with a number larger than 46.
     
  4. Aug 26, 2005 #3

    lurflurf

    User Avatar
    Homework Helper

    I now see the part about Fermats Theorem. Fermat had many theorems, I assume you mean Fermats little theorem.
    So by Fermats little theorem
    99^47=99 (mod 47)
    99^99=(99^47)^2(99^5)=99^7 (mod 47) then the method I listed abouve can be used, but now less squares are needed
    7=1+2+4
    find
    99^1 (mod 47)
    99^2 (mod 47)
    99^4 (mod 47)
    then multiply them and reduce modulo 47
    again making reductions modulo 47 as needed.
     
  5. Aug 26, 2005 #4
    lurflurf, yes I meant Fermat's little theorem but how would you do 99^4 (mod 47) quickly?

    Thanks
     
  6. Aug 26, 2005 #5

    lurflurf

    User Avatar
    Homework Helper

    By repeated squaring with reduction modulo 47 as needed.
    all bellow is mod 47
    99^1=2*47+5=5
    99^2=5^2=25
    99^4=25^2=625=13*47+14=14
    or even easier
    99^4=5^3*5=125*5=(2*47+31)*5=31*5=155=14+3*47=14
     
  7. Aug 26, 2005 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    remember that in mod arithmetic you cah reduce any numver mod whatever anytime you need to. 99=5 mod 47, that should be your first step.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook