Fermat’s Little Theorem

**charikaar** · Feb 25th 2008, 03:54 AM

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

**PaulRS** · Feb 25th 2008, 06:33 AM

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

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

**PaulRS** · Feb 25th 2008, 07:12 AM

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

Thus: $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 $339\equiv{-1}(\bmod.17)$ so $339^{8356}\equiv{(-1)^{8356}}=1(\bmod.17)$

Thread: Fermat’s Little Theorem

LinkBack

Thread Tools

Display

Fermat’s Little Theorem

Similar Math Help Forum Discussions

Fermat’s Theorem

abstract algebra [primitive root mod n, euler theorem, fermat theorem]

Fermat's Last Theorem

Fermat's Little Theorem

Fermat's Little Theorem Help [again]

Search Tags