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!

Why Fermat's little theorem not working here

  1. Nov 22, 2014 #1
    1. The problem statement, all variables and given/known data
    Fermats little theorem states that

    ##a^{P-1} \mod P = 1 \mid ## a is coprime to P
    Now I'm trying to solve this equation with the help of above theorem, But I'm ending up with wrong result

    ##2^{133} \mod 133##

    2. Relevant equations
    ##a^{P-1} \mod P = 1##
    ##(A \times B) \mod n = [(A \mod n) \times (B \mod n)] \mod n##

    3. The attempt at a solution
    ##2^{133} \mod 133##
    ##= 2^{132+1} \mod 133##
    ##= 2^{132} \times 2 \mod 133##
    ##= [2^{132} \mod 133] \times [2 \mod 133]##
    ##\because (A \times B) \mod n = [(A \mod n) \times (B \mod n)] \mod n##
    ##= 1 \times 2 = 2##

    But the correct ans is ##2^{133} \mod 133 = 128##
     
  2. jcsd
  3. Nov 22, 2014 #2

    ShayanJ

    User Avatar
    Gold Member

    Because [itex] 133=19 \times 7 [/itex]!
    Actually I don't see any step that you are allowed to use the theorem in!
    Your calculation aren't clear too!
     
  4. Nov 22, 2014 #3

    Orodruin

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Fermat's little theorem holds only if ##P## is prime.

    Edit: Scooped by Shyan. :oops:
     
  5. Nov 22, 2014 #4
    Sorry little mistake

    ##2^{133} \mod 133##
    ##= 2^{18 \times 7 + 7} \mod {19 \times 7}##
    ##= 2^{18 \times 7} \times 2^7 \mod {19 \times 7}##

    Now how can we solve it
     
  6. Nov 23, 2014 #5

    ehild

    User Avatar
    Homework Helper
    Gold Member

    2133=(27)19=12819. p = 19, prime, and 128 is not divisible with 19. Apply Fermat's Little Theorem to a=128 and p=19.
     
  7. Nov 23, 2014 #6
    @ehlid @Shayn
    Actually I was watching an Online lecture, In it the teacher uses the following concept to solve the above problem

    Suppose ##K \mod (A \times B) = R##

    ##K \mod A = r_1 \implies K = A \times x + r_1##
    ##K \mod B = r_2 \implies K = B \times y + r_2##

    Then "R should be in ##A \times x + r_1## and ##B \times y + r_2## form". This statement I didn't understand
     
  8. Nov 24, 2014 #7

    RUber

    User Avatar
    Homework Helper

    If ##K = Ax+r_1## and ##K =By+r_2##, Then look at A mod y=C and B mod x=D.
    Then ## K=myx+Cx+r_1=nxy+Dy+r_2 ##
    Thus ##K \mod xy = Cx+r_1=Dy+r_2##.
    An example might be:
    32 = 2 mod 3 and 32 = 0 mod 2.
    Let 2=x, 3=y, r_1 =0, r_2 = 2, A= 16, B =10.
    A mod y = 16 mod 3 = 1 =C.
    B mod x = 10 mod 2 = 0 = D.
    So 32 mod (2*3) = Cx+r_1=1*2+0=2 and =Dy+r_2=0*3+2=2.
    This method could get ugly fast and is not as efficient as other methods that make use of cycles.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Why Fermat's little theorem not working here
  1. Little math help here? (Replies: 1)

Loading...