素数の秘密を暴く！ウィルソンの定理を徹底解説
目次
ウィルソンの定理とは？
ウィルソンの定理は、数論（整数論）において素数の判定に使われる美しい定理です。 次のように表現されます：
ウィルソンの定理：
自然数 \( p \) が素数であるための必要十分条件は、次の合同式が成り立つことである。
\[ (p – 1)! \equiv -1 \pmod{p} \]
ここで、\((p-1)!\) は \(1 \times 2 \times 3 \times \cdots \times (p – 1)\) を意味し、階乗（ファクトリアル）と呼ばれます。
具体例で理解する
例1：\( p = 5 \) の場合
\[ (5 – 1)! = 4! = 24 \] \[ 24 \mod 5 = 24 \div 5 = 4余り4 \Rightarrow 24 \equiv 4 \pmod{5} \] \[ -1 \mod 5 = 4 \Rightarrow 24 \equiv -1 \pmod{5} \] つまり、条件成立！よって 5 は素数。
例2：\( p = 6 \) の場合（素数でない）
\[ (6 – 1)! = 5! = 120 \] \[ 120 \mod 6 = 0 \Rightarrow 120 \not\equiv -1 \pmod{6} \] 条件不成立。よって 6 は素数ではない。
例3：\( p = 7 \)
\[ 6! = 720,\quad 720 \mod 7 = 6 \] \[ -1 \mod 7 = 6 \Rightarrow 720 \equiv -1 \pmod{7} \] よって 7 は素数。
ウィルソンの定理の証明
ウィルソンの定理の証明には、モジュロ（合同算術）と逆元の概念が重要です。
素数の特徴
素数 \( p \) のとき、\([1, 2, …, p-1]\) の各数には合同式における「逆元」が必ず存在します。 つまり、ある \( a \in \{1, …, p-1\} \) に対して \[ a \cdot a^{-1} \equiv 1 \pmod{p} \] を満たす \( a^{-1} \) が存在します。
逆元のペアと例外
1 から \( p-1 \) の中で、自分自身が逆元になるものは、以下の条件を満たすものです： \[ a^2 \equiv 1 \pmod{p} \Rightarrow a \equiv \pm 1 \pmod{p} \] したがって、逆元が自分自身になるのは \( 1 \) と \( p – 1 \) だけです。 その他の数はすべて逆元とペアを組み、ペアの積は 1 に合同です。
証明まとめ
\[ (p – 1)! = 1 \cdot 2 \cdots (p – 1) \] このうち、\(1\) と \(p – 1\) 以外は逆元とのペアで積が 1 になるため、 \[ (p – 1)! \equiv 1 \cdot (p – 1) \equiv -1 \pmod{p} \] よって定理が成立します。
定理の応用と注意点
素数判定としての応用
ウィルソンの定理は「ある数が素数かどうか」を判断するための方法になります。 ただし、実用上は効率が悪いため、大きな数には向きません。
注意点
- 素数でない数に対しては、\((p – 1)! \not\equiv -1 \pmod{p}\) が成り立つ。
- 計算量が大きく、コンピュータを使っても階乗計算が困難になる。
ウィルソンの定理の歴史
この定理はイギリスの数学者エドマンド・ウィルソンにちなんで名付けられていますが、最初に発見したのは中国の数学者孫子（3世紀頃）や、11世紀のイスラム数学者アル・バイロー二だとも言われています。
18世紀になって、ジョゼフ・ラグランジュが初めてこの定理の厳密な証明を与えました。これによりウィルソンの定理は数学的に確立されたのです。
まとめ
- ウィルソンの定理は、素数 \( p \) に対して \((p – 1)! \equiv -1 \pmod{p}\) が成り立つという定理。
- 素数判定に使えるが、計算量の面で実用性は低い。
- 証明には逆元や合同算術の知識が必要。
- 数学の歴史的発展においても興味深い位置づけにある。
