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 133=19 \times 7!
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.