メルセンヌ素数とリュカ=レーマー判定法と、そしてペル方程式と

 「最大の素数が更新された」という報道が今年の1月24日の朝日新聞朝刊でなされたことは、当ブログでも、また、最大の素数が更新された! - hiroyukikojimaの日記でエントリーした。これは2233万ケタという巨大な素数で、アメリカのセントラルミズーリ大学のカーチス・クーパー教授が、世界中のコンピューター約800台のボランティアを利用して発見したものだ。
 発見された素数は、メルセンヌ素数というタイプの素数である。メルセンヌ素数とは、(2のk乗−1)という計算で表される素数。kが素数でないなら、(2のk乗−1)が素数にならないことは簡単にわかるので、kとしては素数だけ試せばよい。今回のものは、(2の74,207,281乗−1)となっており、49番目のメルセンス素数で、当然、74,207,281は素数である。メルセンス素数が発見されることは、偶数の完全数(6=1+2+3のように、自分自身を除く約数の和が自分自身と一致する数)が発見されることと同じである。したがって、49個目の偶数の完全数が見つかったことになる。ちなみに、奇数の完全数はまだ一つもみつかっていないし、「存在しない」と予想されているが、それも証明されていない。
 「任意の」大きな整数が素数かどうかを判定する実用的な判定法は、現在のところない。しかし、メルセンヌ数(2のk乗−1)に対しては、実用的な判定法がある。それが、リュカ=レーマー判定法である。これは、19世紀の数学者リュカが発見した判定法を、20世紀の数学者レーマーが改良したものだ。
 リュカ=レーマー判定法のやり方は簡単である。まず、リュカ=レーマー数列というのを、次のように作る。すなわち、4からスタートし、得られた数を2乗して2を引いて次の数を作るのである。
4→4×4−2=14→14×14−2=194→194×194−2=37634→・・・
というふうに進んでいく。このn項目をS(n)と書くとき、リュカ=レーマー判定法とは、

素数pについて、(2のp乗−1)がS(p−1)を割り切るとき、また、そのときに限り、(2のp乗−1)は素数である

というものである。例えば、k=5のときのメルセンヌ数(2の5乗−1)は31だが、S(4)=37634は確かに31で割り切れる(おみごと、おみごと)。リュカ=レーマー数列は、正直に計算すると、すぐに巨大な数になるが、判定したい(2のp乗−1)で割った余りで数列を計算(mod計算)していけばいいので、オーバーフローしなくて済むのである。
 雑誌『高校への数学』で素数についての連載をしていることもあって、このたび、このリュカ=レーマー判定法のレーマーによる証明をまじめに読んでみた。読んだのは、和田秀男『数の世界 整数論への道』岩波書店だ。

数の世界―整数論への道 (科学ライブラリー) (1981年)

数の世界―整数論への道 (科学ライブラリー) (1981年)

その証明は、理解できてみると、めちゃめちゃ面白いものだった。
なんということでしょう! 最も重要な役割を果たすのは、いわゆる、「ペル方程式」なのである。
ペル方程式というのは、「(xの2乗)−a(yの2乗)=±1」の整数解を求める問題のことで、数論の研究の中でも歴史の古いものだ。本当は「フェルマー方程式」と呼ばれるべきなのに、誤ってペル方程式と定着してしまったものである。ペル方程式について、詳しくは、拙著『世界は2乗でできている』ブルーバックスを参照してほしい。証明に使うペル方程式は、a=3のケース、すなわち、「(xの2乗)−3(yの2乗)=1(☆)」である。
この方程式(☆)の整数解は、次のようにして、実にユニークな方法で得られる。すなわち、無理数α=2+√3に対して、(αのn乗)を展開整理し、(αのn乗)=x(n)+y(n)√3と表したとき、x=x(n), y=y(n)が、ペル方程式(☆)の整数解となるのである。しかも、この方法で、すべての整数解が得られる。
面白いのは、この2つの数列x(n)とy(n)が、三角関数(cosとsin)と類似した、「加法定理」「倍角公式」を持つことなのだ。次のような公式である。

(加法定理)
x(m)=x(n)x(m)±3y(n)y(m)
y(m)=±x(n)y(m)+x(m)y(n)
(倍角公式)
x(2n)=2(x(n)の2乗)−1
y(2n)=2x(n)y(n)

これらの公式を上手に利用すると、いろいろな面白い関係が得られる。まず、
リュカ=レーマー数S(k+1)=2・x(2のk乗)
という関係式がポイントである。
また、3より大きい任意の素数qに対して、
y((q+1)/2)・y((q−1)/2)はqの倍数
が、証明を完成するためのかなめの事実となる。
証明の手法は、典型的な技の組み合わせであり、大学受験の数学問題よりは難しいけれど、数学オリンピック程度のものなので、がんばれば高校生にも理解できる。とりわけ、「2項係数の素因数を評価する」とか、「ある性質を満たす整数が、その性質を満たす最小の整数の倍数となる」という互除法的な発想とか、有名テクニックのオンパレードとなっていて、楽しく、また、随所でうならされる。
こうしてみると、数論の定理というのが、さまざまなアイテムのリンクで成立していて、みごとだなあ、と感心させられる。
 和田秀男『数の世界 整数論への道』は、ものすごい名著だと思うのだけど、現在は版切れのようで残念だ。こんなわかりやすくて、self-containedで、すべての証明を付けている数論の本はほかにないと思う。和田氏が、計算機数学の専門家である、ということが、この本のわかりやすさ・面白さと関係あるのではないか、と推測している。最後の章で「すべての素数を表す19変数37次多項式」についての「マチアセビッチの定理」を取り上げ、証明も含めた完全な解説を行っているのが圧巻である。なんと、この定理にも、本質的に「ペル方程式」が活かされているのである。拍手喝采