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

Printable View

- October 7th 2008, 05:06 PMbigbFermat's Little Theorem 2
Use Fermat's Little Theorem to compute 29^202 mod 13

- October 7th 2008, 06:53 PMo_O
By Fermat's theorem:

Note that .

So:

... - October 7th 2008, 07:01 PMbigb
- October 7th 2008, 07:15 PMicemanfan
Following after o_O:

- October 7th 2008, 07:20 PMbigb
- October 7th 2008, 07:23 PMicemanfan
- October 7th 2008, 07:38 PMbigb
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) - October 7th 2008, 07:40 PMo_O
(Yes) I would do it the second way

- October 7th 2008, 07:43 PMbigb
- October 7th 2008, 07:47 PMo_O
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.