Thread: Fermat’s Little Theorem

Use Fermat’s Little Theorem to calculate the remainder of 339^8356 when divided by 17.


339^16 = 1 (mod 17) by Fermat theorems.
So (raise to the 522) both sides,
339^8352 = 1 (mod 17)

Does this mean 339^8352 divided by 17 give remainder 1?

How do i get the next step?

339^8352x339^4=339^4(mod 17)

Whats the next step after this? Please help.

Thanks

Just see that $\displaystyle 339\equiv{-1}(\bmod{17})$ then $\displaystyle 339^4\equiv{1}(\bmod{17})$

and so $\displaystyle 339^{8356}\equiv{1}(\bmod{17})$

Or better, $\displaystyle 8356=
{\dot 4}
$ since $\displaystyle 56=
{\dot 4}
$ and we have that $\displaystyle 339^4\equiv{1}(\bmod.17)$

Thus: $\displaystyle 339^{8356}=339^{4\cdot{z}}=(339^{4})^z\equiv{1}(\b mod.17)$ were z is the natural such that 8356=4·z

Directly $\displaystyle 339\equiv{-1}(\bmod.17)$ so $\displaystyle 339^{8356}\equiv{(-1)^{8356}}=1(\bmod.17)$