ウィルソンの定理
定理: 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つずつの組に分けることができる. よって,
\begin{align*}
(p-1)! &\equiv (p-1)\cdot 1^{\frac{p-3}{2}}\cdot 1\\
&\equiv p-1\\
&\equiv -1 \pmod{p}
\end{align*}
