Why Fermat's little theorem not working here

[22990atinesh]

Homework Statement

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

Homework Equations

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

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

 

[ShayanJ]

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!

 

[Orodruin]

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

Edit: Scooped by Shyan.

 

[22990atinesh]

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

 

[ehild]

2¹³³=(2⁷)¹⁹=128¹⁹. p = 19, prime, and 128 is not divisible with 19. Apply Fermat's Little Theorem to a=128 and p=19.

 

[22990atinesh]

@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

 

[RUber]

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.