Math 314 - Number Theory
Lecture Notes #8 - Supplement
Wilson's Theorem Proof
Theorem 39 (Wilson's Theorem). The integer p is a prime if
and only if (p-1)!º -1 (mod p).
Proof:
First assume p is a prime integer.
If p=2, then clearly (2-1)!º-1 (mod 2). So
assume P > 2.
Now let a be any natural number such that 1 £ a £(p-1). Then by Theorem 34, the congruence axº1 (mod p) has a unique solution in the least positive residue class (in the set {1,2,...,p-1}).
We now want to show that 1 and p-1 are the only self-inverses in the least positive residue class. To that end, suppose that x is an element in the least residue class such that x2 º 1 (mod p). This means that p|(x2-1) or p|(x-1)(x+1). Since p is a prime, it follows that p|(x-1) or p|(x+1). Because x is in the least residue, it follows that 0< x+1£p and 0 £x-1 < p. So if p is a prime and p|x+1, it follows that p=x+1; from which it follows that xº-1 (mod p). On the other hand, if p|(x-1) it must be the case that x-1=0 which says that x=1. So these two observations together mean that the only solutions to x2º1 (mod p) in the least positive residue class are x=1 and x=p-1.
As a result, the elements 2,3,...p-2 have distinct inverses in the least positive residue class. So in the product: (2)(3)...(p-2) each element can be paired up with its unique inverse. This being the case, it is clear that the product is º1 (p). That is:
To prove the converse, assume that (p-1)! º -1 (mod p). From this it follows that p|(p-1)!+1. Let q be any divisor of p such that q < p. Since p|(p-1)!+1, it follows that q|(p-1)!+1. Since q<p, it follows that q|(p-1)!. Together the two previous statement about q and Theorem 7, show that q|1. But this is only possible if q=1. Thus the only divisor of p that is less than p is 1. From this it follows that p is prime.
rak - 7/02