リュカ–レーマー・テストの証明

リュカ–レーマー・テストとは

デリック・ヘンリー・レーマーは、数学者エドゥアール・リュカの判定法を発展させ、メルセンヌ数の素数を判定する「リュカ–レーマー・テスト」を確立しました。このテストは、特にメルセンヌ素数を効率よく見極めるための重要な手法となっています。

メルセンヌ数と素数判定

メルセンヌ数は、形状が $M_p = 2^p - 1$ で表される数です。この数が素数であるための条件を以下に示します。ここで、$p$ は奇素数である必要があります。

1. 初期値を $S_0 = 4$ とし、続く数列を $S_n = S_{n−1}^2 − 2$ （$n egin{equation} ext{1}
ight)$）で定義します。

2. この数列の $(p-2)$ 番目の項 $S_{p−2}$ が、メルセンヌ数 $M_p$ で割り切れるとき、$M_p$ が素数であることが示されます。

このようにして、リュカ–レーマー・テストはメルセンヌ数の特異な性質を活用しています。

リュカ–レーマー・テストの証明

リュカ–レーマー・テストの証明には、十分性と必要性の証明が含まれます。

十分性の証明

$S_{p−2} ≡ 0 ext{ (mod } Q ext{)}$ の条件が成り立つとき、$Q$ が素数であることを示す必要があります。もし $Q$ が合成数だとすると、最小素因数 $F$ の存在が必然となります。この条件を考えると、数列の計算から、公算的に $S_n$ が $kF$ と表現される瞬間が訪れます。

この結果、特定の数 $n$ に対して、$S_n$ と $S_{n−1}$ の間には関係があり、最終的に $Q$ が単独の素数か、または逆に合成数であることが示される必要があります。

必要性の証明

次に、$p$ が奇素数で、$Q$ が素数であると仮定した場合、$S_{p−2} ≡ 0 ext{ (mod } Q ext{)}$ が成り立つことを示す必要があります。ここでは、平方剰余の相互法則を用いることで、$S_{p−2}$ の性質に強く依存しています。

この過程では、数列の展開と代数的操作によって、一貫して $S_n ext{の値}$ を $Q$ の法において評価していきます。加えて、$Q ext{が定義される数比}$ や他の相互関係を用いることで、最終的に条件が明示されることになります。

結論

リュカ–レーマー・テストは、メルセンヌ数が素数かどうかを判定するための非常に効率的な手法であり、数学的証明と理論の両方において重要な役割を果たしています。さらに、このテストの一般化として、リュカ–レーマー–リーゼル・テストのような技術も開発されています。これらの研究は、数論の発展に大きく寄与しており、今日の数学的な探求においても重要です。

参考文献

• - 中村滋『フィボナッチ数の小宇宙』日本評論社
• - G.H.ハーディ、E.M.ライト『数論入門』
• - 和田秀男『数の世界　整数論への道』岩波書店

もう一度検索