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 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.
     
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...