ウィルソンの定理

ウィルソンの定理について

ウィルソンの定理は、整数論の分野において素数に関する重要な結果を示す定理です。この定理は素数である整数 p に対して、以下のように表現できます。すなわち、素数 p に対して、

\[(p-1)! \equiv -1 \ (mod \, p)\]

が成り立ちます。この式は、(p-1)!（p-1の階乗）が素数 p で割った余りが -1 になることを示しています。つまり、p が素数の場合に限り、(p-1)! を p で割ったときの余りが -1 に等しくなるという特性があります。これによりウィルソンの定理の条件が確立されます。

歴史的背景

ウィルソンの定理は10世紀のペルシャの数学者イブン・アル・ハイサム（アルハゼン）によって最初に発見されましたが、その後長らくヨーロッパでは知られていませんでした。1766年にイギリスの数学者エドワード・ウェアリングの弟子であるジョン・ウィルソンによって再発見され、1770年にウェアリングがその成果を公表したことで「ウィルソンの定理」と呼ばれるようになりました。ただし、最初にこの定理の証明を行ったのは、1773年のラグランジュです。また、同時期にゴットフリート・ライプニッツもこの事実に気づいていましたが、論文発表は行いませんでした。

計算の実用性

ウィルソンの定理は素数判定の方法として理論的には利用可能ですが、計算量の観点からは実用的ではありません。特に p が大きくなるにつれて (p-1)! の計算は非常に困難になります。そのため、実際の素数判定では他の方法が用いられることが一般的です。たとえば、エラトステネスの篩やミラー・ラビン素数判定法など、より効率的なアルゴリズムが広く採用されています。

ウィルソンの定理の証明

原始根を使った証明

ウィルソンの定理の証明では、主に原始根の概念が使われます。まず、p = 2 の場合は自明であるため、p を奇素数と仮定します。p が素数であれば、法 p に関する原始根 a が存在します。このことからフェルマーの小定理を用いることができます。

\[ a^{p-1} \equiv 1 \ (mod \, p) \]

ここで、a は原始根であり、a1, a2, ... , ap-1 の各値は法 p に関して 1, 2, ..., p-1 の変数によって並べ替えられます。したがって、以下が成り立ちます。

\[ a^1 a^2 \ldots a^{p-1} \equiv (p - 1)! \ (mod \, p) \]

これにより、原始根 a の積としての表現と階乗との関係を導き出します。

一方で、考え方を少し変えて、

\[ a^1 a^2 \ldots a^{p-1} = a^{(1+2+\dots+(p-1))} = a^{p(p-1)/2} \]

と表すことができます。このとき、b を a^(p(p-1)/2) とし、b^2 ≡ 1 (mod p) であることが分かります。よって、b は p で割った余りとして ±1 のどちらかに等しくなります。

明示的に示すと、b ≡ -1 (mod p) を証明したいので、仮に b ≡ 1 (mod p) とすると矛盾が生じます。したがって最終的に指摘されるのは、p が奇数であるからこそこの証明が確立されることになります。

合成数 n に関しても、n が素数でない場合 (n-1)! によって矛盾を導くことができます。

結論

ウィルソンの定理は、素数の特性を深く掘り下げる基盤を形成する重要な理論です。数学の歴史においても多くの数学者の関与や発見があり、現在でも整数論や暗号理論などで幅広く利用されています。

もう一度検索