# Thread: How to solve large mod equation?

1. ## 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

2. 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

3. 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?

4. 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