Wilsonの定理

1 ⇒ 2 を示す。$p=n$ を素数とする。$p=2$ なら $1!=1\equiv-1\pmod 2$ である。$p\geq3$ とする。
$1\leq a\leq p-1$ なる各整数 $a$ は $p$ と互いに素なので、Bézoutの等式により $ax+py=1$ となる整数 $x,y$ があり、$x$ を $p$ で割った余りを $b$ とすれば $ab\equiv1\pmod p$、$1\leq b\leq p-1$ である。このような $b$ はただ一つである（$ab\equiv ab'$ なら $p\mid a(b-b')$ で、$p\nmid a$ だから Euclid の補題により $p\mid b-b'$、よって $b=b'$）。$b$ を $a$ の逆元と呼び $a^{*}$ と書くと、$(a^{*})^{*}=a$ である。
$a^{*}=a$ となるのは $a^2\equiv1$、すなわち $p\mid(a-1)(a+1)$ のときであり、Euclid の補題（素数 の記事の補題「Euclidの補題」）により $p\mid a-1$ または $p\mid a+1$、すなわち $a=1$ または $a=p-1$ のときに限る。したがって残りの $p-3$ 個の整数 $2,3,\dots,p-2$ は、$a\neq a^{*}$ となる組 $\{a,a^{*}\}$ に分かれ、各組の積は $1$ と合同である。ゆえに
$$ (p-1)!=1\cdot(p-1)\cdot\prod_{\text{組}}aa^{*}\equiv1\cdot(-1)\cdot1=-1\pmod p $$
である。

1 ⇒ 2 の別証明を与える。$p$ を素数とし、整数係数の多項式
$$ F(x)=\bigl(x^{p-1}-1\bigr)-(x-1)(x-2)\cdots(x-(p-1)) $$
を考える。2 つの項の $x^{p-1}$ の係数はともに $1$ なので、$F$ の次数は $p-2$ 以下である。Fermatの小定理により、$a=1,2,\dots,p-1$ のそれぞれについて $a^{p-1}-1\equiv0$ であり、積の項も $x=a$ で $0$ になるので、$F(a)\equiv0\pmod p$ である。
係数を $p$ で割った余りで考えると、$F$ は有限体 $\mathbb{F}_p=\mathbb{Z}/p\mathbb{Z}$ 上の次数 $p-2$ 以下の多項式で、$p-1$ 個の相異なる根をもつ。体上の $0$ でない多項式の根の個数は次数以下なので（有限体 の記事の補題「体上の多項式の根の個数」）、$F$ の係数はすべて $p$ で割り切れる。すなわち多項式として
$$ x^{p-1}-1\equiv(x-1)(x-2)\cdots(x-(p-1))\pmod p $$
が成り立つ。$x=0$ を代入すると $-1\equiv(-1)^{p-1}(p-1)!\pmod p$ である。$p$ が奇素数なら $(-1)^{p-1}=1$ なので $(p-1)!\equiv-1$ であり、$p=2$ は直接確かめられる。

$n=ab$、$1< a\leq b< n$ と書く。$a< b$ なら、$a$ と $b$ は $1,2,\dots,n-1$ の中の相異なる数なので $ab=n$ が $(n-1)!$ を割り切る。$a=b$、すなわち $n=a^2$ のとき、$a\geq3$ なら $2a< a^2=n$ であり、$a$ と $2a$ は $1,\dots,n-1$ の中の相異なる数なので $a\cdot2a=2n$ が $(n-1)!$ を割り切る。$a=2$ なら $n=4$ で $3!=6\equiv2\pmod 4$ である。
最後の主張：$n\neq4$ なら $(n-1)!\equiv0\not\equiv-1$ である（$n\geq2$ では $n\nmid1$）。$n=4$ では $2\not\equiv-1\equiv3\pmod 4$ である。

$1\leq k\leq h$ について $p-k\equiv-k\pmod p$ なので、
$$ (p-1)!=\prod_{k=1}^{h}k\,(p-k)\equiv\prod_{k=1}^{h}(-k^2)=(-1)^h(h!)^2\pmod p $$
である。thm-wilson により左辺は $-1$ と合同なので、$(h!)^2\equiv-(-1)^h=(-1)^{h+1}$ を得る。$p\equiv1\pmod 4$ なら $h$ は偶数で $(h!)^2\equiv-1$ である。$p\equiv3\pmod 4$ なら $h$ は奇数で $(h!)^2\equiv1$ であり、$p\mid(h!-1)(h!+1)$ から Euclid の補題により $h!\equiv\pm1$ である。

1：$x\notin T$ なら $x^{-1}\neq x$ であり、$x^{-1}\notin T$ である。よって $G\setminus T$ は組 $\{x,x^{-1}\}$ に分かれ、各組の積は $1$ である。$G$ は可換なので積の順序は変えてよく、全元の積は $T$ の全元の積に等しい。
2：$T=\{1,t\}$ なら 1 により積は $1\cdot t=t$ である。
3：$T$ は部分群である（$x^2=y^2=1$ なら $(xy)^2=x^2y^2=1$）。仮定の $s,t$ について $K=\{1,s,t,st\}$ を考えると、$st\neq1$（$t\neq s^{-1}=s$）、$st\neq s$、$st\neq t$ なので $K$ は $T$ の位数 $4$ の部分群である。$T$ は $K$ の剰余類 $xK$（$x\in T$）の交わらない和に分かれ（Lagrangeの定理 の記事の命題「左剰余類は群を分割する」）、各剰余類の元の積は
$$ x\cdot xs\cdot xt\cdot xst=x^4s^2t^2=1 $$
である。よって $T$ の全元の積は $1$ であり、1 により $G$ の全元の積も $1$ である。

$G=(\mathbb{Z}/n\mathbb{Z})^{\times}$、$T=\{x\in G\mid x^2=1\}$ とする。$n=2$ なら $P(2)=1\equiv-1\pmod 2$ である。以下 $n\geq3$ とすると $-1\not\equiv1\pmod n$ なので、$T$ は少なくとも $1$ と $-1$ を含む。
$n=4,p^k,2p^k$ のとき $T=\{1,-1\}$ であることを示す。$n=4$ なら $G=\{1,3\}$ で明らかである。$n=p^k$ で $x^2\equiv1$ とすると $p^k\mid(x-1)(x+1)$ であり、$(x+1)-(x-1)=2$ と $p\geq3$ から $p$ は $x-1$ と $x+1$ の両方を割ることはない。よって $p^k$ はどちらか一方を割り切り、$x\equiv\pm1\pmod{p^k}$ である。$n=2p^k$ なら $x$ は奇数で、$x\equiv\pm1\pmod{p^k}$ と $x\equiv\pm1\pmod 2$（奇数なので自動的）から $x\equiv\pm1\pmod{2p^k}$ である。したがって lem-wilson-group-product の 2 により $P(n)\equiv-1$ である。
それ以外の $n\geq3$ について、$T$ が $1,-1$ と異なる元 $t$ を含むことを示せば、lem-wilson-group-product の 3（$s=-1$）により $P(n)\equiv1$ となる。

• $n=2^k$、$k\geq3$ のとき、$t=2^{k-1}+1$ とおくと $t^2=2^{2k-2}+2^k+1\equiv1\pmod{2^k}$（$2k-2\geq k$）であり、$t\not\equiv1$、また $t+1=2^{k-1}+2$ は $2^k$ で割り切れないので $t\not\equiv-1$ である。
• $n$ が互いに素な $a,b\geq3$ の積 $n=ab$ に書けるとき、中国剰余定理により $t\equiv1\pmod a$、$t\equiv-1\pmod b$ となる整数 $t$ がとれる。$t^2\equiv1$ は $a$ と $b$ の両方を法として成り立つので $n$ を法としても成り立ち、$t\equiv-1\not\equiv1\pmod b$ から $t\not\equiv1\pmod n$、$t\equiv1\not\equiv-1\pmod a$ から $t\not\equiv-1\pmod n$ である。$t$ は $n$ と互いに素である（$t^2\equiv1$ より）。
  $n\geq3$ が $4,p^k,2p^k$ のいずれでもなければ、上の 2 つの場合のどちらかに当たる。実際、$n$ が 2 の冪なら $n=2^k$、$k\geq3$ である。$n$ が奇素因数 $p$ をもち $n=2^ep^km$（$m$ は $p$ と互いに素な奇数）と書くとき、$m\geq3$ なら $a=2^ep^k$、$b=m$ とすればよく、$m=1$ なら $e\geq2$ で $a=2^e$、$b=p^k$ とすればよい。