ウィルソンの定理
合同式が関係する有名な定理の一つです. (合同式についてはこちら. )
証明
が素数なら式(1)が成り立つことの証明は1通り, 逆の証明は2通り紹介します. 前半の証明は分かりにくいかもしれませんが, 対偶を示しています. 逆の証明は,- フェルマーの小定理と合同式における剰余の定理を用いる方法.
- ~ を積の剰余が1になる組に分けられることを示す方法.
[1] のとき
\begin{align*}
(4-1)!=6\not\equiv -1 \pmod{4}
\end{align*}
[2] のとき
\begin{align*}
p=p_1^{e_1}\cdot p_2^{e_2}\cdots p_m^{e_m}
\end{align*}
ただし, は素因数の個数で, 各 は素数, , 各 は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*}
但し, 最後の部分では不等式 を用いていますが, これは についての数学的帰納法で示されます. 等号がすべて成り立つのは のときのみ, つまり のときのみなので, なら . 両辺に を掛ければ , つまり 以下に の倍数が最低でも 個は存在する, ということになります. 同様にして, についてもそれぞれの倍数が 以下に 個存在します.
このことから, 以下の自然数を全て掛け合わせたものが で割り切れる, つまり で割り切れます. 故に,
\begin{align*}
(p-1)!\equiv 0 \not\equiv -1 \pmod{p}
\end{align*}
の証明Ⅰ.
の場合は代入すれば成り立つことがすぐにわかるので, の場合, つまり が奇素数の場合を考えます. は と互いに素であるので, フェルマーの小定理より,
\begin{align*}
1^{p-1}\equiv 2^{p-1}\equiv \cdots\equiv (p-1)^{p-1}\equiv 1\pmod{p}
\end{align*}
最右辺の を移項して,
\begin{align*}
1^{p-1}-1\equiv 2^{p-1}-1\equiv\cdots\equiv(p-1)^{p-1}-1\equiv 0
\end{align*}
ここで, とおくと, 上の式は
\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*}
ここに を代入して, また, , が奇数であることを用いて,
\begin{align}
{-1} &\equiv (-1)\cdot(-2)\cdots\{-(p-1)\}\\
&\equiv (p-1)!
\end{align}
となり示された.
の証明Ⅱ.
が素数のとき, を満たす整数 に対して, 以下の方程式はただ一つの解をもつ.\begin{align*}
kx\equiv 1\pmod{p} \ (1\leqq x\leqq p-1)
\end{align*}
() は と互いに素なので, を で割った余りは と1対1に対応する(フェルマーの小定理の証明Ⅱ参照). これは式(11)の解がただ一つ存在することを意味している.
ここで, に対する解は , に対する解は で, に対しては より解 . つまり, は を法としてその積の剰余が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*}