Wilson's theorem

This proof uses the fact that if p is a prime, then the set of numbers G = (Z/pZ)^× = {1, 2, ... p − 1} forms a group under multiplication modulo p. This means that for each element a in G, there is a unique inverse element b in G such that ab ≡ 1 (mod p). If a ≡ b (mod p), then a^2 ≡ 1 (mod p), which forces a^2 − 1 = (a + 1)(a − 1) ≡ 0 (mod p), and since p is prime, this forces a ≡ 1 or −1 (mod p), i.e. a = 1 or a = p − 1.

In other words, 1 and p − 1 are each their own inverse, but every other element of G has a distinct inverse, and so if we collect the elements of G pairwise in this fashion and multiply them all together, we get the product −1. For example, if p = 11, we have 10!=1(10)(2*6)(3*4)(5*9)(7*8)=-1(mod11)

2008-10-08 10:18:20 補充：
Here is another proof of the first direction: Suppose p is prime. Consider the polynomial
g(x)=(x-1)(x-2)...(x-(p-1))

2008-10-08 10:18:36 補充：
Recall that if f(x) is a nonzero polynomial of degree d over a field F, then f(x) has at most d roots over F. Now, with g(x) as above, consider the polynomial
f(x)=g(x)-(x^(p-1)-1)

2008-10-08 10:18:58 補充：
Since the leading coefficients cancel, we see that f(x) is a polynomial of degree at most p − 2.
Reducing mod p, we see that f(x) has at most p − 2 roots mod p. But by Fermat's little theorem, each of the elements 1, 2, ..., p − 1 is a root of f(x). This is impossible, unless f(x) is identically

2008-10-08 10:19:06 補充：
zero mod p, i.e. unless each coefficient of f(x) is divisible by p.
But since p is odd, the constant term of f(x) is just (p−1)!+1, and the result follows.