How do you compute the following using Fermat's Little Theorem?
2^1,000,006 mod 101
2^-1,000,005 mod 11
Yes, this is homework which is completely allowed in SO!
+2
A:
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.
Stefan Kendall
2009-05-19 23:36:21
I don't think 2^-5 === 2^6 (mod 11).
Steve Jessop
2009-05-19 23:49:33
Yeah, there's definitely some errors in this (or at least bad notation). Needs to be corrected, but I'm not sure where to begin.
Noldorin
2009-05-19 23:51:08
so then 2^1,000,006 mod 101...2^1,000,000 * 2^6 = 1 * 32 = 32 mod 101 = -5?
jinsungy
2009-05-20 01:14:15
+2
A:
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.
Steve Jessop
2009-05-19 23:37:18
This seems to be the way to go. Additionally, it only guides the OP, so good answer.
Noldorin
2009-05-19 23:54:11