ウィルソンの定理の証明、具体例について
1. ウィルソンの定理とは
ウィルソンの定理は
\[ p が素数 \Leftrightarrow (p – 1)! \equiv -1 \pmod p \]
ここで、\( (p – 1)! \) は \( 1 \) から \( p – 1 \) までの積（階乗）を表します。
つまり、\( p \) が素数であれば、\( (p – 1)! \) を \( p \) で割った余りは \( p – 1 \)（または \( -1 \)）になります。その逆も成り立ちます。
1.1. 具体例 1: \( p = 5 \) の場合
\( p = 5 \) の場合、次のように計算します。
\[ (5-1)! = 4! = 4 \times 3 \times 2 \times 1 = 24 \]
24 を 5 で割った余りを求めると、
\[\begin{align*} 24 &\equiv 4 \pmod 5 \\ &\equiv 4 \pmod 5 \\ &\equiv -1 \pmod 5\end{align*}\]
なので、ウィルソンの定理が成り立っています。
1.2. 具体例 2: \( p = 7 \) の場合
\( p = 7 \) の場合も見てみましょう。
\[ (7-1)! = 6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720 \]
720 を 7 で割った余りを求めると
\[\begin{align*} 720 &\equiv 20 \pmod 7 \\ &\equiv 6 \pmod 7 \\ &\equiv -1 \pmod 7\end{align*}\]
なので、ウィルソンの定理が成り立っています。
2. 証明
2.1. 証明の方針
ウィルソンの定理は
\[ p が素数 \Leftrightarrow (p – 1)! \equiv -1 \pmod p \]
です。つまり、証明するべき内容は次の二つです。
- pが素数ならば、$(p – 1)! \equiv -1 \pmod p$ が成り立つ。
- $(p – 1)! \equiv -1 \pmod p$ならば、p が素数
ここで、命題「$(p – 1)! \equiv -1 \pmod p$ならば、p が素数」という証明は非常に簡単なので、ここで証明します。
何を証明するべきかというと、命題の対偶を考えます。命題の対偶「pが合成数ならば、$(p – 1)! \equiv -1 \pmod p$が成り立たない」ということを証明したらいい。
$$p=p_1^{\lambda_1}p_2^{\lambda_2}\cdots p_m^{\lambda_m}$$
$m\geq 2$のとき、
$1\leq i \leq m-1$のとき、$p_i$は素数、$\lambda_i$は1以上の整数であり、次の不等式が成り立つ。
$$p_i < p \quad かつ \quad p_i^{\lambda_i} < p$$
$p_i^{\lambda_i} < p$であるので、$(p-1)!$のなかに、$p_i^{\lambda_i}$が含まれるので、
$$\begin{align*} (p-1)!&\equiv p_1^{\lambda_1}p_2^{\lambda_2}\cdots p_m^{\lambda_m} \pmod p\\ &\equiv 0 \pmod p \end{align*}$$
$m=1$のとき、
$$p=p_1^{\lambda_1}$$
ここで、pは合成数であるので、$\lambda_1$は2以上の整数で、$p_1$は素数であり$p_1 < p$が成り立つ。
$(p-1)!$には、$p_1$が含まれるので、$p_1$の倍数になる。$p$は$p_1$の倍数であり、$(p-1)!+1$は$p_1$の倍数ではないので、
$$\begin{align*} & (p-1)!+1\not\equiv 0 \pmod p\\ & (p-1)!\not\equiv -1 \pmod p \end{align*}$$
したがって、命題の対偶「pが合成数ならば、$(p – 1)! \equiv -1 \pmod p$が成り立たない」が示されたため、$(p – 1)! \equiv -1 \pmod p$ならば、p が素数になる。
残りの命題「$(p – 1)! \equiv -1 \pmod p$ならば、p が素数」を証明すればいい。
2.2. フェルマーの小定理を利用した証明
フェルマーの小定理によれば、\( p \) が素数であり、\( x \) が \( p \) の倍数でない任意の整数の場合、
\[ x^{p – 1} \equiv 1 \pmod p \]
が成り立ちます。したがって、
\[ x^{p – 1} – 1 \equiv 0 \pmod p \]
となります。$f(x)=x^{p-1}-1$とすると、
\( p \) 以下の\( x = 1, 2, \dots, p – 1 \) に対して、\( f(x) \equiv 0 \pmod p \) であり、これらの \( x \) は合同式上では \( f(x) \) の根（解）であることがわかります。
\( f(x) \) は \( x = 1, 2, \dots, p – 1 \) を（解）に持つ多項式なので、これらの一次式の積で表すことができます。ただし、定数倍を考慮して、
\[ f(x) \equiv A (x – 1)(x – 2) \dotsm (x – (p – 1)) \pmod p \]
とします。ここで、\( A \) は定数です。最高次係数の比較をすると
- 左辺の多項式 \( f(x) = x^{p – 1} – 1 \) の最高次項の係数は \( 1 \) です。
- 右辺の積を展開すると、最高次項は \( x^{p – 1} \) で、その係数は \( A \) になります。
したがって、
\[ 1 = A \]
となり、定数 \( A \) は \( 1 \) であることがわかります。
以上より、
\[ f(x) \equiv (x – 1)(x – 2) \dotsm (x – (p – 1))\pmod p \]
となります。
\( x = 0 \) を代入して、両辺を比較します。
左辺を計算すると、
\[ f(0) = 0^{p – 1} – 1 = -1 \]
右辺を計算すると、
\[ \begin{align*} f(0) &= (0 – 1)(0 – 2) \dotsm (0 – (p – 1)) \\ &= (-1)(-2) \dotsm (-(p – 1)) \\ &=(-1)^{p – 1} \cdot (p – 1)! \end{align*} \]
各項のマイナスをまとめると、
\[ f(0) = (-1)^{p – 1} \cdot (1 \cdot 2 \cdot \dotsm \cdot (p – 1)) = (-1)^{p – 1} \cdot (p – 1)! \]
したがって、
\[ -1 \equiv (-1)^{p – 1} \cdot (p – 1)! \pmod p \]
pが偶数の場合は\( p = 2 \) のみであるか、直接計算すると、
\[ (2 – 1)! = 1! = 1 \equiv -1 \pmod 2 \]
\( p \) が奇数の場合、\( (-1)^{p – 1} =1\) なので、
\[ (p – 1)! \equiv -1 \pmod p \]
以上より、任意の素数 \( p \) に対して、
\[ (p – 1)! \equiv -1 \pmod p \]
が成り立つことが示されました。
2.3. 割った余りが異なることを利用した証明
ウィルソンの定理の証明に先立って、まず次の性質を示します。この性質はフェルマーの小定理の証明にも利用されます。
次に、\( a, 2a, \dots, (p-1)a \) を \( p \) で割った余りを考えます。各 \( ka \) の \( p \) での余りを \( r_k \) とします。すなわち、\( r_k = ka \ (\text{mod} \ p) \) です。
このとき、もし \( r_i = r_j \) （ただし \( i \neq j \)）が成り立つと仮定するなら、次のようになります。
\[ ia \equiv ja \ (\text{mod} \ p) \]
両辺から \( ja \) を引くと、
\[ (i-j)a \equiv 0 \ (\text{mod} \ p) \]
\( p \) と \( a \) は互いに素なので、\( (i-j) \) が \( p \) で割り切れなければなりません。しかし、\( 1 \leq i, j \leq p-1 \) なので、\( i-j \) は \( p \) の倍数ではない。 \( i = j \) となり、これは仮定に反します。したがって、全ての \( r_k \) は異なる余りを持ちます。
(p-1)!は1~pまでの積であるので、この中に二つの積が$\mod p$で１になる部分があれば、計算が楽になると考えられる。ここで、pは素数、$1\leq x \leq p-1$とすると、\( a, 2a, \dots, (p-1)a \) は異なる余りを持つため、合同式の性質より、$ax \equiv 1 \pmod p$となるxが存在する。また、$a=x$のとき、
$$ \begin{align*}& ax \equiv 1 \pmod p \\ & a^2 \equiv 1 \pmod p \\ & a^2 -1 \equiv 0 \pmod p \\ & (a+1)(a-1) \equiv 0 \pmod p \\ & \Leftrightarrow a+1 \equiv 0 \pmod p \quad かつ \quad a-1 \equiv 0 \pmod p \end{align*}$$
したがって、$a=1,p-1$のとき、$a=x$となる。一方で、$a\neq 1,p-1$のとき、$a\neq x$となる。
ここで、$(p-1)!$について考えると、$(p-1)!$は1からpまでの積であり、$1,p-1$以外は積が1になるペアが存在する。$2,3,4,\cdots p-3,p-2$の中で、積が1になるペアを作ると、$\frac{p-3}{2}$個であるから、
$$ \begin{align*}(p-1)!&\equiv 1 \cdot 1^{\frac{p-3}{2}}\cdot p-1 \pmod p \\ &\equiv p-1 \pmod p\\ &\equiv -1 \pmod p \end{align*}$$
