ウィルソンの定理

定理: 2以上の正整数 $p$ が素数であることと, 次の合同式が成り立つことは同値です.

\begin{align*}
(p-1)!\equiv-1 \pmod{p}\tag{1}
\end{align*}

合同式が関係する有名な定理の一つです. (合同式についてはこちら. )

証明

$p$ が素数なら式(1)が成り立つことの証明は1通り, 逆の証明は2通り紹介します. 前半の証明は分かりにくいかもしれませんが, 対偶を示しています. 逆の証明は,

フェルマーの小定理と合同式における剰余の定理を用いる方法.
$1$ ～ $p-1$ を積の剰余が1になる組に分けられることを示す方法.

です.

$(\Leftarrow)$

対偶をとって, $p\geqq 2$ が素数でないならば $(p-1)!\equiv -1\pmod{p}$ が成り立たないことを示します.

[1] $p=4$ のとき

\begin{align*}
(4-1)!=6\not\equiv -1 \pmod{4}
\end{align*}

[2] $p\geqq 4$ のとき

素数でない $p$ が次のように素因数分解されたとする.

\begin{align*}
p=p_1^{e_1}\cdot p_2^{e_2}\cdots p_m^{e_m}
\end{align*}

ただし, $m$ は素因数の個数で, 各 $p_i$ は素数, $p_i\neq p_j, i\neq j$ , 各 $e_i$ は1以上とします. このとき,

\begin{align*}
\frac{p}{p_1} &= p_1^{e_1-1}\cdot p_2^{e_2}\cdots p_m^{e_m}\\
&\geqq p_1^{e_1-1}\\
&\geqq 2^{e_1-1}\\
&\geqq e_1
\end{align*}

但し, 最後の部分では不等式 $2^{n-1}\geqq n$ を用いていますが, これは $n$ についての数学的帰納法で示されます. 等号がすべて成り立つのは $m=1, p_1=2, e_1=1, 2$ のときのみ, つまり $p=2, 4$ のときのみなので, $p\geqq4$ なら $\displaystyle\frac{p}{p_1}\geqq e_1$ . 両辺に $p_1$ を掛ければ $\displaystyle p\geqq p_1e_1$ , つまり $p-1$ 以下に $p_1$ の倍数が最低でも $e_1$ 個は存在する, ということになります. 同様にして, $p_2, \ldots, p_m$ についてもそれぞれの倍数が $p-1$ 以下に $e_2, \ldots, e_m$ 個存在します.
このことから, $p-1$ 以下の自然数を全て掛け合わせたものが $p_1^{e_1}, p_2^{e_2}, \ldots, p_m^{e_m}$ で割り切れる, つまり $p$ で割り切れます. 故に,
\begin{align*}
(p-1)!\equiv 0 \not\equiv -1 \pmod{p}
\end{align*}

$(\Rightarrow)$ の証明Ⅰ.

$p=2$ の場合は代入すれば成り立つことがすぐにわかるので, $p>2$ の場合, つまり $p$ が奇素数の場合を考えます.

$1, 2, \cdots, p-1$ は $p$ と互いに素であるので, フェルマーの小定理より,
\begin{align*}
1^{p-1}\equiv 2^{p-1}\equiv \cdots\equiv (p-1)^{p-1}\equiv 1\pmod{p}
\end{align*}

最右辺の $1$ を移項して,

\begin{align*}
1^{p-1}-1\equiv 2^{p-1}-1\equiv\cdots\equiv(p-1)^{p-1}-1\equiv 0
\end{align*}

ここで, $F(x)=x^{p-1}-1$ とおくと, 上の式は

\begin{align*}
F(1)\equiv F(2)\equiv\cdots\equiv F(p-1)\equiv 0
\end{align*}

ここで, 合同式における剰余の定理によって, 次のように書ける.

\begin{align*}
F(x)\equiv (x-1)(x-2)\cdots\{x-(p-1)\}
\end{align*}

ここに $x=0$ を代入して, また, $F(0)=-1$ , $p$ が奇数であることを用いて,

\begin{align}
{-1} &\equiv (-1)\cdot(-2)\cdots\{-(p-1)\}\\
&\equiv (p-1)!
\end{align}

となり示された.

$(\Rightarrow)$ の証明Ⅱ.

$p$ が素数のとき, $1\leqq k\leqq p-1$ を満たす整数 $k$ に対して, 以下の方程式はただ一つの解をもつ.

\begin{align*}
kx\equiv 1\pmod{p} \ (1\leqq x\leqq p-1)
\end{align*}

( $\because$ ) $k$ は $p$ と互いに素なので, $k, 2k, \ldots, (p-1)k$ を $p$ で割った余りは $1, 2, \ldots, p-1$ と1対1に対応する(フェルマーの小定理の証明Ⅱ参照). これは式(11)の解がただ一つ存在することを意味している.

ここで, $k=1$ に対する解は $x=1$ , $k=p-1$ に対する解は $x=p-1$ で, $2\leqq k\leqq p-2$ に対しては $k^2\not\equiv 1$ より解 $x\neq k$ . つまり, $2, 3, \ldots, p-2$ は $p$ を法としてその積の剰余が1となるような2つずつの組に分けることができる. よって,