§C3.5ウィルソンの定理

証明.$a^2 \equiv 1 \pmod p$は、$p$が$a^2 - 1 = (a-1)(a+1)$を割り切ることと同じである。$p$が素数であるから、$p$は$a - 1$または$a + 1$を割り切る。

$p$が$a-1$を割り切る場合、$0 \le a - 1 \le p-2$であるから$a - 1 = 0$、すなわち$a = 1$である。

$p$が$a+1$を割り切る場合、$2 \le a + 1 \le p$であるから$a + 1 = p$、すなわち$a = p-1$である。

逆に$a = 1$のとき$a^2 = 1 \equiv 1$であり、$a = p-1$のとき$a \equiv -1$であるから$a^2 \equiv 1$である。▨

証明 (素数であれば合同式が成り立つこと).$p$を素数とする。

$p = 2$のときは$(p-1)! = 1! = 1$であり、法$2$では$1 \equiv -1$であるから、主張が成り立つ。

$p$を奇素数とする。$1 \le a \le p-1$を満たす整数$a$を取る。$p$は$a$を割り切らないので、$p$が素数であることから、$ab \equiv 1 \pmod p$を満たす$1 \le b \le p-1$が存在する。同じ範囲の整数$c$も$ac \equiv 1 \pmod p$を満たすなら、$p$は$a(b-c)$を割り切る。$p$は$a$を割り切らないので、$p$は$b-c$を割り切る。$|b-c|<p$であるから$b=c$である。したがって、$a$の逆元$a^{-1}$は$1$から$p-1$までにただ一つ存在する。

$a a^{-1}\equiv1\pmod p$であり、逆元の一意性から$(a^{-1})^{-1}=a$である。定理 2.1により、$a=a^{-1}$となるのは$a=1$と$a=p-1$の場合に限る。したがって、$1$から$p-1$までの数のうち$1$と$p-1$以外のものは、相異なる二数$a$と$a^{-1}$からなる互いに交わらない対へ分かれる。各対の積は法$p$で$1$と合同であるから、これらの対に属する数をすべて掛けた積も法$p$で$1$と合同である。したがって、$1$と$p-1$も含めて掛けると

を得る。▨

証明 (合同式が成り立てば素数であること).$p$を$1$より大きい正の整数とし、$(p-1)! \equiv -1 \pmod p$が成り立つとする。$p$が素数でないと仮定すると、$1 < d < p$を満たす$p$の約数$d$が存在する。

$1 < d \le p-1$であるから、$d$は積$(p-1)! = 1 \cdot 2 \cdots (p-1)$の因数の一つであり、$d$は$(p-1)!$を割り切る。一方、仮定より$p$は$(p-1)! + 1$を割り切り、$d$は$p$を割り切るので、$d$は$(p-1)! + 1$を割り切る。したがって$d$は差$\bigl((p-1)! + 1\bigr) - (p-1)! = 1$を割り切る。これは$d > 1$と両立しない。よって$p$は素数である。▨

証明.$n$を合成数とし、$n = ab$（$1 < a \le b < n$）と書く。

$a < b$の場合、$a$と$b$は$1$から$n-1$までに現れる相異なる二つの数であるから、積$(n-1)!$は$ab = n$を因数として含み、$n$で割り切れる。

$a = b$の場合、$n = a^2$である。$a > 2$であれば$2a < a^2 = n$であるから、$a$と$2a$は$1$から$n-1$までに現れる相異なる二つの数であり、$(n-1)!$は$a \cdot 2a = 2n$を因数として含み、$n$で割り切れる。$a = 2$であれば$n = 4$であり、$3! = 6$は$4$で割り切れず、$6 \equiv 2 \pmod 4$である。▨