Lemma. Let p be a prime and let . if and only if or .
Proof. If , then . If , then
Conversely, suppose . Then
and since p is prime, or . The only number in which satisfies is 1, and the only number in which satisfies is .
Theorem. (Wilson's theorem) Let . p is prime if and only if
Proof. Suppose p is prime. If , then k is relatively prime to p. So there are integers a and b such that
Reducing a mod p, I may assume .
Thus, every element of has a reciprocal mod p in this set. The preceding lemma shows that only 1 and are their own reciprocals. Thus, the elements must pair up into pairs . It follows that their product is 1. Hence,
Now suppose . I want to show p is prime. Begin by rewriting the equation as .
Suppose . I may take . If , the factorization is trivial, so suppose . Then (since it's one of ) and , so shows . Therefore, .
This proves that the only factorization of p is the trivial one, so p is prime.
Example. Wilson's theorem implies that the product of any ten consecutive numbers, none divisible by 11, equals -1 mod 11 (since any ten consecutive numbers reduce mod 11 to . For example,
Example. Find the least nonnegative residue of .
Note that . I'll start by finding the residues of mod 71 and 73.
By Wilson's theorem,
Next, let . Then
Note that . So
Thus,
I'll the the iterative method of the Chinese Remainder Theorem to get a congruence mod 5183. First, means for some . Plugging this into the second congruence yields
The last congruence means that for some . Plugging this into gives
Theorem. (Fermat) Let p be prime, and suppose . Then .
Proof. The idea is to show that the integers
reduce mod p to the standard system of residues , then apply Wilson's theorem.
There are numbers in the set . So all I need to do is show that they're distinct mod p. Suppose that , and
This means , so or . Since the first case is ruled out by assumption, . But since , this is only possible if .
Thus, are distinct numbers mod p. So if I reduce mod p, I must get the numbers in . Hence,
On the other hand, another application of Wilson's theorem shows that
So , or .
Corollary. If p is prime, then for all a.
Proof. If , then and , so .
If , then . Multiplying by a, I get again.
Example. Compute .
If you multiply out , here's what you get:
Now just reduce mod 83. Heh.
If you don't have access to software that can do this, you can use Fermat's theorem. First, 83 is prime and , so Fermat says . Now , so
In other words, if you're trying to reduce mod p, where , factor out as many 's as possible, then reduce the rest "by hand".
Example. Solve .
I'd like to multiply both sides by the reciprocal of 16 mod 41. What is it? Well, I could use the Euclidean algorithm on , or I could do a multiplication table mod 41. A simpler approach is to note that by Fermat, . Hence,
Now this is an answer, but a rather cheesy one. I ought to reduce the right side mod 41 to something a little smaller! I can't use Fermat any more, so I just "divide and conquer".
, so
Now , so
, so
(I reduce down to the point where the arithmetic can be handled by whatever computational tools I have available.)
Copyright 2008 by Bruce Ikenaga