Proof.
The statement is clear when
![$ p=2$](img517.png)
, so henceforth we assume
that
![$ p>2$](img518.png)
.
We first assume that
![$ p$](img14.png)
is prime and prove that
![$ (p-1)! \equiv -1\pmod{p}$](img519.png)
. If
![$ a\in\{1,2,\ldots,p-1\}$](img520.png)
then
the equation
has a unique solution
![$ a'\in\{1,2,\ldots,p-1\}$](img522.png)
.
If
![$ a=a'$](img523.png)
, then
![$ a^2\equiv 1\pmod{p}$](img524.png)
, so
![$ p\mid a^2-1 = (a-1)(a+1)$](img525.png)
, so
![$ p\mid (a-1)$](img526.png)
or
![$ p\mid (a+1)$](img527.png)
, so
![$ a\in\{1,p-1\}$](img528.png)
.
We can thus pair off the elements of
![$ \{2,3,\ldots,p-2\}$](img529.png)
,
each with their inverse.
Thus
Multiplying both sides by
![$ p-1$](img531.png)
proves that
![$ (p-1)! \equiv -1\pmod{p}$](img519.png)
.
Next we assume that
and
prove that
must be prime. Suppose not, so that
is a composite number. Let
be a prime divisor
of
. Then
, so
. Also,
by assumption,
This is a contradiction, because a prime can not divide a number
![$ a$](img37.png)
and
also divide
![$ a+1$](img537.png)
, since it would then have to divide
![$ (a+1) - a=1$](img538.png)
.
SAGE Example 2.1
We use SAGE to create a table of triples; the first
column contains
![$ n$](img7.png)
, the second column contains
![$ (n-1)!$](img516.png)
modulo
![$ n$](img7.png)
,
and the third contains
![$ -1$](img53.png)
modulo
![$ n$](img7.png)
. Notice that the first columns contains a prime
precisely when the second and third columns are equal.
(The ... notation indicates indentation in SAGE; you should not type the dots
in explicitly.)
sage: for n in range(1,10):
... print n, factorial(n-1) % n, -1 % n
1 0 0
2 1 1
3 2 2
4 2 3
5 4 4
6 0 5
7 6 6
8 0 7
9 0 8