ウィルソンの定理とその逆 ~ 数学について考えてみる

　ウィルソンの定理とは、任意の素数

p

$p$ について

\begin{matrix} (1) & (p - 1)! \equiv - 1 (\mod p) \end{matrix}

$\begin{equation}\large(p-1)!\equiv-1\pmod p\end{equation}$

が成り立つ、という定理のことです。

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

(p - 1)!

$(p-1)!$ は

p - 1

$p-1$ 以下の自然数をすべて掛け合わせる階乗を表し、

(p - 1)! = 1 \times 2 \times \dots (p - 2) (p - 1)

$(p-1)!=1\times2\times\cdots(p-2)(p-1)$

となります。

$p=2$ のとき

(2 - 1)! = 1! = 1

$(2-1)!=1!=1$ であり、

1 \equiv - 1 (\mod 2)

$1\equiv-1\pmod2$ なので、

(1)

$(1)$ を満たします。

$p>2$ のとき

(p - 1)! \equiv 1 \times 2 \times \dots (p - 2) (p - 1) (\mod p)

$(p-1)!\equiv1\times2\times\cdots(p-2)(p-1)\pmod p$

と書けるので、右辺が

- 1

$-1$ と法

p

$p$ に関して合同であることを確かめます。

p - 1

$p-1$ に着目すると

p - 1 \equiv - 1 (\mod p)

$p-1\equiv-1\pmod p$

なので、

(p - 1)! \equiv 1 \times {2 \times 3 \times \dots (p - 3) (p - 2)} (- 1) (\mod p)

$(p-1)!\equiv1\times\bigl\{2\times3\times\cdots(p-3)(p-2)\bigr\}(-1)\pmod p$

となります。
ただし、

p = 3

$p=3$ のとき

p - 1 = 2

$p-1=2$ なので上式の

{}

$\{\ \}$ にあたる部分はなく

\begin{aligned} (3 - 1)! & \equiv 1 \times (- 1) (\mod 3) \\ \equiv - 1 \end{aligned}

$\begin{align*}(3-1)!&\equiv1\times(-1)\pmod3\\[0.5em]&\equiv-1\end{align*}$

となり、

p = 3

$p=3$ のとき

(1)

$(1)$ が成り立つことはこの時点でわかります。

ここで、「ある素数未満の自然数の倍数をある素数で割ったときの余りの性質」より

2, 3, \dots, p - 3, p - 2

$2,3,\cdots,p-3,p-2$ は適切に2つを選んで掛け合わせると、すべての積は法

p

$p$ に関して

1

$1$ と合同になるので、

\overset{p - 3 個}{\overset{⏞}{2 \times 3 \times \dots (p - 3) (p - 2)}} \equiv \overset{\frac{p - 3}{2} 個}{\overset{⏞}{1 \times 1 \times \dots \times 1 \times 1}} (\mod p)

$\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{aligned} (p - 1)! & \equiv 1 \times {\overset{\frac{p - 3}{2} 個}{\overset{⏞}{1 \times 1 \times \dots \times 1 \times 1}}} \times (- 1) (\mod p) \\ \equiv - 1 \end{aligned}

$\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)

$(1)$ が成り立つことがわかります。

例えば

p = 17

$p=17$ のとき、法

17

$17$ に関して

1

$1$ と合同になる

2

$2$ 以上

15

$15$ 以下の自然数による因数の組み合わせは

\begin{array}{l} (2, 9), & (3, 6), & (4, 13), & (5, 7), \\ (8, 15), & (10, 12), & (11, 14) \end{array}

$\begin{array}{l}(2,9),&(3,6),&(4,13),&(5,7),\\[0.5em](8,15),&(10,12),&(11,14)\end{array}$

なので、

\begin{aligned} (17 - 1)! & \equiv 1 \times 2 \times 3 \times 4 \\ \times 5 \times 6 \times 7 \times 8 \\ \times 9 \times 10 \times 11 \times 12 \\ \times 13 \times 14 \times 15 \times 16 \\ \equiv 1 \times (2 \times 9) \times (3 \times 6) \\ \times (4 \times 13) \times (5 \times 7) \\ \times (8 \times 15) \times (10 \times 12) \\ \times (11 \times 14) \times 16 \\ \equiv 1 \times 1 \times 1 \times 1 \\ \times 1 \times 1 \times 1 \times 1 \times (- 1) \\ \equiv - 1 \end{aligned}

$\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)

$(1)$ が成り立つことがわかります。

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

ウィルソンの定理の逆

　ウィルソンの定理は、

自然数

n

$n$ について、

n

$n$ が素数ならば

(n - 1)! \equiv - 1 (\mod n)

$(n-1)!\equiv-1\pmod n$

という命題であるといえ、その逆は

自然数

n

$n$ について、

(n - 1)! \equiv - 1 (\mod n)

$(n-1)!\equiv-1\pmod n$ ならば

n

$n$ は素数である

となります。
これの真偽を調べてみます。

ウィルソンの定理の逆の対偶

自然数

n

$n$ について、

n

$n$ が合成数ならば

(n - 1)! \equiv - 1 (\mod n)

$(n-1)!\equiv-1\pmod n$ でない

の真偽を調べます。

自然数

n

$n$ が合成数であるということは、

n

$n$ は

\begin{aligned} n & = p^{α} q^{β} r^{γ} \dots \\ (\begin{aligned} p, q, r, \dots : & 相 異 な る 素 数 \\ α, β, γ, \dots : & 自 然 数 \end{aligned} \end{aligned}

$\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

$p$ 、

β

$β$ 個の素因数

q

$q$ 、

γ

$γ$ 個の素因数

r

$r$ 、…を2つのグループに分け、各グループ内の素因数を掛け合わせて2つの

2

$2$ 以上の自然数をつくると、その2つの自然数の組には2つの場合が考えられます。

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

　合成数

n

$n$ の素因数から異なる2つの自然数がつくれる場合、どちらの自然数も

n

$n$ の約数なので、これらは

n

$n$ 未満の自然数です。
そして、これらの自然数はどちらも

(n - 1)!

$(n-1)!$ の約数でもある、すなわち

(n - 1)!

$(n-1)!$ は

n

$n$ の倍数であるということなので、

(n - 1)! \equiv 0 (\mod n)

$(n-1)!\equiv0\pmod n$

となります。

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

　合成数

n

$n$ の素因数から同じ自然数が2つつくれる場合、これは

n

$n$ が平方数であるということです。

n

$n$ が合成数の平方数であるとき、素因数のグループを組み直すと異なる2つの自然数の組をつくることができるので、

n

$n$ は上の場合にも含まれる合成数となります。
しかし、

n

$n$ が自身未満の素数の平方数であるとき、素因数のグループを組み直すことができないので、

n

$n$ はこの場合にしか含まれない合成数となります。

なので、この場合においては

n

$n$ 未満の素数の平方数であるときに着目します。

$n$ が $2$ の平方数のとき

n

$n$ が

2

$2$ の平方数、すなわち

n = 4

$n=4$ のとき

\begin{aligned} (4 - 1)! & = 3! \\ = 6 \equiv 2 (\mod 4) \end{aligned}

$\begin{align*}(4-1)!&=3!\\[0.5em]&=6\equiv2\pmod4\end{align*}$

となります。

$n$ が $2$ より大きい素数の平方数のとき

n = p^{2}

$n=p^2$ （

p :

$p:$ 素数）とおくと

n

$n$ は小さい順で

p

$p$ 番目の正の

p

$p$ の倍数です。
すると、

n - 1

$n-1$ までの自然数の中には正の

p

$p$ の倍数が

p - 1

$p-1$ 個含まれているということになります。

n

$n$ が

2

$2$ より大きい素数の平方数のとき、

n - 1

$n-1$ までの自然数の中には正の

p

$p$ の倍数が

2

$2$ 個以上含まれているので、

(n - 1)!

$(n-1)!$ は少なくとも

p^{2}

$p^2$ の倍数、すなわち

n

$n$ の倍数であるといえます。

したがって、このとき

(n - 1)! \equiv 0 (\mod n)

$(n-1)!\equiv0\pmod n$

です。

　以上より、自然数

n

$n$ が合成数のとき

(n - 1)! \equiv - 1 (\mod n)

$(n-1)!\equiv-1\pmod n$ でないことがわかったので、ウィルソンの定理の逆の対偶は真、すなわちウィルソンの定理の逆も真であることがわかります。

ウィルソンの定理の逆より、

(n - 1)! \equiv - 1 (\mod n)

$(n-1)!\equiv-1\pmod n$ が成り立つのは

n

$n$ が素数のときだけなので

(n - 1)! \equiv - 1 (\mod n)

$\large(n-1)!\equiv-1\pmod n$

が成り立つかは素数判定に利用することができます。

(2025/1)加筆しました。

数学について考えてみる

2024年12月18日