Loading [MathJax]/extensions/TeX/mathchoice.js
横画面推奨!
モバイル機器の場合、数式が見切れる場合があります。

2024年12月18日

ウィルソンの定理とその逆

 ウィルソンの定理とは、任意の素数pについて
\begin{equation}\large(p-1)!\equiv-1\pmod p\end{equation}
が成り立つ、という定理のことです。

これが成り立つことを確かめてみます。


 (p-1)!p-1以下の自然数をすべて掛け合わせる階乗を表し、
(p-1)!=1\times2\times\cdots(p-2)(p-1)
となります。

p=2のとき

 (2-1)!=1!=1であり、1\equiv-1\pmod2なので、(1)を満たします。

p>2のとき

(p-1)!\equiv1\times2\times\cdots(p-2)(p-1)\pmod p
と書けるので、右辺が-1と法pに関して合同であることを確かめます。
p-1に着目すると
p-1\equiv-1\pmod p
なので、
(p-1)!\equiv1\times\bigl\{2\times3\times\cdots(p-3)(p-2)\bigr\}(-1)\pmod p
となります。
ただし、p=3のときp-1=2なので上式の\{\ \}にあたる部分はなく
\begin{align*}(3-1)!&\equiv1\times(-1)\pmod3\\[0.5em]&\equiv-1\end{align*}
となり、p=3のとき(1)が成り立つことはこの時点でわかります。
ここで、「ある素数未満の自然数の倍数をある素数で割ったときの余りの性質」より2,3,\cdots,p-3,p-2は適切に2つを選んで掛け合わせると、すべての積は法pに関して1と合同になるので、
\overbrace{2\times3\times\cdots(p-3)(p-2)}^{p-3\text{個}}\equiv\overbrace{1\times1\times\cdots\times1\times1}^{\frac{p-3}{2}\text{個}}\pmod p
となります。
したがって、
\begin{align*}(p-1)!&\equiv1\times\bigl\{\overbrace{1\times1\times\cdots\times1\times1}^{\frac{p-3}{2}\text{個}}\bigr\}\times(-1)\pmod p\\[0.5em]&\equiv-1\end{align*}
となり、(1)が成り立つことがわかります。
例えばp=17のとき、法17に関して1と合同になる2以上15以下の自然数による因数の組み合わせは
\begin{array}{l}(2,9),&(3,6),&(4,13),&(5,7),\\[0.5em](8,15),&(10,12),&(11,14)\end{array}
なので、
\begin{align*}(17-1)!&\equiv1\times2\times3\times4\\ &\quad\times5\times6\times7\times8\\ &\quad\times9\times10\times11\times12\\ &\quad\times13\times14\times15\times16\\[0.5em]&\equiv1\times\textcolor{red}{(2\times9)\times(3\times6)}\\ &\quad\textcolor{red}{\times(4\times13)\times(5\times7)}\\ &\quad\textcolor{red}{\times(8\times15)\times(10\times12)}\\ &\quad\textcolor{red}{\times(11\times14)}\times\textcolor{blue}{16}\\[0.5em]&\equiv1\times\textcolor{red}{1\times1\times1}\\ &\quad\textcolor{red}{\times1\times1\times1\times1}\times\textcolor{blue}{(-1)}\\[0.5em]&\equiv-1\end{align*}
となり、(1)が成り立つことがわかります。

以上より、いかなる素数pにおいても(1)が成り立つことがわかります。


ウィルソンの定理の逆

 ウィルソンの定理は、
自然数nについて、nが素数ならば(n-1)!\equiv-1\pmod n
という命題であるといえ、その逆は
自然数nについて、(n-1)!\equiv-1\pmod nならばnは素数である
となります。
これの真偽を調べてみます。
ウィルソンの定理の逆の対偶
自然数nについて、nが合成数ならば(n-1)!\equiv-1\pmod nでない
の真偽を調べます。
自然数nが合成数であるということは、n
\begin{align*}n&=p^\alpha q^\beta r^\gamma\cdots\\ &\left(\begin{aligned}p,q,r,\cdots:&相異なる素数\\[0.5em]\alpha,\beta,\gamma,\cdots:&自然数\end{aligned}\right.\end{align*}
と表せるということです。
ここで、α個の素因数pβ個の素因数qγ個の素因数r、…を2つのグループに分け、各グループ内の素因数を掛け合わせて2つの2以上の自然数をつくると、その2つの自然数の組には2つの場合が考えられます。

異なる2つの自然数の組の場合

 合成数nの素因数から異なる2つの自然数がつくれる場合、どちらの自然数もnの約数なので、これらはn未満の自然数です。
そして、これらの自然数はどちらも(n-1)!の約数でもある、すなわち(n-1)!nの倍数であるということなので、
(n-1)!\equiv0\pmod n
となります。

1つの自然数のみの組の場合

 合成数nの素因数から同じ自然数が2つつくれる場合、これはnが平方数であるということです。
nが合成数の平方数であるとき、素因数のグループを組み直すと異なる2つの自然数の組をつくることができるので、nは上の場合にも含まれる合成数となります。
しかし、nが自身未満の素数の平方数であるとき、素因数のグループを組み直すことができないので、nはこの場合にしか含まれない合成数となります。
なので、この場合においてはn未満の素数の平方数であるときに着目します。

n2の平方数のとき

 n2の平方数、すなわちn=4のとき
\begin{align*}(4-1)!&=3!\\[0.5em]&=6\equiv2\pmod4\end{align*}
となります。

n2より大きい素数の平方数のとき

 n=p^2p:素数)とおくとnは小さい順でp番目の正のpの倍数です。
すると、n-1までの自然数の中には正のpの倍数がp-1個含まれているということになります。
n2より大きい素数の平方数のとき、n-1までの自然数の中には正のpの倍数が2個以上含まれているので、(n-1)!は少なくともp^2の倍数、すなわちnの倍数であるといえます。
したがって、このとき
(n-1)!\equiv0\pmod n
です。

 以上より、自然数nが合成数のとき(n-1)!\equiv-1\pmod nでないことがわかったので、ウィルソンの定理の逆の対偶は真、すなわちウィルソンの定理の逆も真であることがわかります。
ウィルソンの定理の逆より、(n-1)!\equiv-1\pmod nが成り立つのはnが素数のときだけなので
\large(n-1)!\equiv-1\pmod n
が成り立つかは素数判定に利用することができます。
(2025/1)加筆しました。
Share:
share
◎Amazonのアソシエイトとして、当サイト「数学について考えてみる」は適格販売により収入を得ています。
Powered by Blogger.

PR

blogmura_pvcount
ブログランキング・にほんブログ村へ