# Thread: Fermat's Little Theorem 2

1. ## Fermat's Little Theorem 2

Use Fermat's Little Theorem to compute 29^202 mod 13

2. By Fermat's theorem: $a^{12} \equiv 1 \ (\text{mod } 13)$

Note that $29 \equiv 3 \ (\text{mod } 13)$.

So: $\left(3^{12}\right)^{17} \equiv 1^{17} \ (\text{mod } 13)$

$\iff 3^{204} \equiv 1 \ (\text{mod } 13)$

$\iff 3^{2} 3^{202} \equiv 1 \ (\text{mod } 13)$

...

3. Originally Posted by o_O
By Fermat's theorem: $a^{12} \equiv 1 \ (\text{mod } 13)$

Note that $29 \equiv 3 \ (\text{mod } 13)$.

So: $\left(3^{12}\right)^{17} \equiv 1^{17} \ (\text{mod } 13)$

$\iff 3^{204} \equiv 1 \ (\text{mod } 13)$

$\iff 3^{2} 3^{202} \equiv 1 \ (\text{mod } 13)$

...
The answer is 81=3mod13..I am messing around with what you did but still cant get the answer. This problem is in my lecture notes but I just cant seem to understand what i wrote.

4. Following after o_O:

$3^23^{202} \equiv 1 (\mod 13)$

$9 \times 3^{202} \equiv 1 (\mod 13)$

$27 \times 3^{202} \equiv 3 (\mod 13)$

$(13 \times 2 + 1) \times 3^{202} \equiv 3 (\mod 13)$

$3^{202} \equiv 3(\mod 13)$

5. Originally Posted by icemanfan
Following after o_O:

$3^23^{202} \equiv 1 (\mod 13)$

$9 \times 3^{202} \equiv 1 (\mod 13)$

$27 \times 3^{202} \equiv 3 (\mod 13)$

$(13 \times 2 + 1) \times 3^{202} \equiv 3 (\mod 13)$

$3^{202} \equiv 3(\mod 13)$

6. Originally Posted by bigb
It became $(13 \times 2 + 1) \equiv 1$.

7. Originally Posted by icemanfan
It became $(13 \times 2 + 1) \equiv 1$.
COmpute 3^302 mod 5

Would this be right??

a^4=1mod5
3=8mod5
8^4=1mod5
8^4*76=1^76mod5
8^2 * 8^302=1mod5
8^2 * 8^302=-64mod5
8^302=-1mod5
8^302=4mod5

or

3^4 = 1 (mod 5) by Fermat theorems.
So (raise to the 75) both sides,
3^300 = 1 (mod 5)
Multiply 3^2 both sides,
3^302 = 3^2 = 9 = 4 (mod 5)

8. I would do it the second way

9. Originally Posted by o_O
I would do it the second way
It can be done the first way right thou?? If not can the second method be applied to the problem 29^202mod13

sry for all the dumb questions. I am just trying to learn the material better

10. Well it really is the same work but you just did the unnecessary work of showing that 3 is congruent to 8 mod 5.

And this method WAS used for your problem. Go through it again. The principle is the same. From Fermat's theorem, you have your number to the power of p - 1 is congruent to 1. Raise it as close to the desired power as possible and manipulate it to get what you need.