How to solve large mod equation?

• Nov 16th 2010, 12:58 PM
dragstang86
How to solve large mod equation?
I have no problem solving smaller equations and understand the logic but don't know how to go about solving a large one such as the one below:

21^16 mod 17

• Nov 16th 2010, 01:08 PM
tonio
Quote:

Originally Posted by dragstang86
I have no problem solving smaller equations and understand the logic but don't know how to go about solving a large one such as the one below:

21^16 mod 17

Google, or read in a book, about Fermat's Little Theorem: $21^{16}=4^{16}=1\!\!\pmod {17}$

Tonio
• Nov 16th 2010, 02:51 PM
dragstang86
Thanks for the input. I read about Fermat's Little Theorem but I must be missing something. The way I understand it is if 16 was prime then 21^16 would equal 21 mod 16 which would leave me with (21 mod 16) mod 17 but 16 is not prime. What am I missing?
• Nov 16th 2010, 06:19 PM
tonio
Quote:

Originally Posted by dragstang86
Thanks for the input. I read about Fermat's Little Theorem but I must be missing something. The way I understand it is if 16 was prime then 21^16 would equal 21 mod 16 which would leave me with (21 mod 16) mod 17 but 16 is not prime. What am I missing?

Read here Fermat's little theorem - Wikipedia, the free encyclopedia the first few lines, in particular line 6.

Tonio