ウィルソンの定理

この記事の所要時間: 552

ウィルソンの定理

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

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

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

証明

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

  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*}

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加

コメントをどうぞ

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください