Fermat's little theorem

Question

How do you calculate the following using Fermat Little Theor

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

+1

jinsungy May 19 '09 at 11:25 pm

2 answers

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

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

+2

Steve jessop May 19 '09 at 11:37 pm

Stefan kendall · Accepted Answer · 2009-05-19T23:36:21+0000

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

2 ^ 10 === 1 mod 11
2 ^ (- 1000,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 with a large number? The process is the same.

This is FLT completely. I messed up.