Transcript exercise congruence modulo n

Fermat’s Little Theorem
(2/24)
• Theorem (flt). If p is prime and GCD(a, p) = 1,
•
•
•
•
then a p – 1 1 (mod p).
Again, this says that in a mod p congruence, we can
reduce exponents by p – 1. Why? If n = k(p – 1) + r, then
a n = a k(p – 1) + r = (a p – 1)k a r 1k a r = a r (mod p),
where the congruence is by the theorem.
The proof of flt requires the following:
Lemma. If GCD(a, p) =1, then the set of numbers
{a, 2a, 3a, ..., (p – 1)a}, after all are reduced mod p, is just
a rearrangement of the set of numbers {1, 2, 3,..., p – 1).
Example: Let p = 7 and let a = 3, then the set is
{3, 6, 9, 12, 15, 18} {3, 6, 2, 5, 1, 4} (mod 7)
Proof of flt
• a and p are as above. If we take the elements of the
•
•
•
•
•
reduced set {a, 2a, 3a, ..., (p – 1)a} and multiply them all
together, we know we get 1 2 3 ... (p – 1) = (p –
1)!
That is, a 2a 3a ... (p – 1)a (p – 1)! (mod p).
How many a’s are there here?
Factoring out the a’s, we get
a p – 1 (p – 1)! (p – 1)! (mod p).
But finally, (p – 1)! is relatively prime to p (why?),
so can cancel it!!
We arrive at a p – 1 1 (mod p).
A Test for Compositeness
• Fermat’s Little Theorem gives us a way to verify that a
•
•
•
•
•
number is composite without factoring it!
Suppose n is some odd number and we’d like to know if
it’s composite, but we’re having trouble factoring it.
Well, compute 2n –1 (mod n). What if the answer is not 1?
Example. I wonder if 376289 is prime? Using a computer,
I find that 2376288 150132 (mod 376289). Conclusion?
In fact 376289 = 571 659, which is why I had trouble
factoring it.
It turns out there are fast algorithms for computing powers
to a modulus, but no known fast algorithms for factoring!
But flt Is NOT “if and only if”
• Unfortunately the converse of flt is not true, i.e., if
•
•
•
•
GCD(a, n) = 1 and if a n – 1 1 (mod n), we CANNOT
conclude that n is prime!
The smallest counterexample with a base of 2 is 341.
That is, 2340 1 (mod 341), BUT 341 is not prime (in fact,
341 = 11 31). Bummer!
341 is called a 2-pseudoprime (i.e., “false prime with
respect to base 2”). There are in fact infinitely many.
The smallest 3-pseudoprime is 91. Etc.
Really disturbing: A Carmichael number is a
k-pseudoprime for every base k to which it is relatively
prime. 561 is the smallest. There are infinitely many!!
Assignment for Wednesday
• Fully absorb these slides and all of Chapter 9.
• We will not pursue pseudoprimes and Carmichael
numbers further in this course, but if you’re interested,
there are lots of things to study, including Chapter 19
in our text.
• Do Exercises 9.2 and 9.4.