compute the remainder when 2^(2^17) + 1 = 19

that + 1 is really throwing me off... I don't know how to deal with it.

Printable View

- Feb 28th 2009, 08:58 AMCoda202fermat's little thm
compute the remainder when 2^(2^17) + 1 = 19

that + 1 is really throwing me off... I don't know how to deal with it. - Feb 28th 2009, 10:37 AMThePerfectHacker
I assume you want to find the remainder of modulo .

By the division algorithm we can write where .

But then, .

To find the remainder we need to simplify modulo .

First, .

Multiply both sides by seven to get, .

Therefore, .

Now, by Fermat's little theorem.

Since we see that .

But this is remainder of only if you want to find remainder of just add 1.