Fermat's Little Theorem

Question

How do you compute the following using Fermat's Little Theorem?

2^1,000,006 mod 101
2^-1,000,005 mod 11

Answer 1

You know that a^(p-1) === 1 mod p, so...

2^10 === 1 mod 11
2^(-1,000,005) = 2^(-1,000,000)*2^(-5) = 1 * 2^(-5) = 2^(-5)*2^(10) = 32 mod 11 = -1 = 10

From this, can you see how to work the larger number? The process is the same.

It's FLT all the way. I messed up.

Answer 2

Since 101 and 11 are prime, then (respectively) 2^100 and 2^10 are congruent to 1 mod 101 and 11.

Try to express 2^1000006 in terms of 2^100 and 2^-1000005 in terms of 2^10. You should be able to reduce each problem to something easy to calculate.