彼らは数学しか勉強できない

素数判定法（総当たり法、エラトステネスの篩、リュカテスト）

「ねぇ、109って素数？」

　家の自習室。机に向かう俺に、幼なじみの友村（ともむら）愛華（あいか）が訊いてきた。

　彼女とは小学校からの付き合いになる。中学に上がってからは、休日に数学を勉強するのが習慣になっている。専ら俺が教えてるけど。

　閑話休題、俺――安藤（あんどう）和人（かずと）は少し考え、頭の中で計算を進める。結論を出すまでに三十秒もかからなかった。

「素数だ」

「……適当に言ってないよね」

　失礼な奴だ。俺は机の引き出しから数学書を取り出した。それを愛華に渡す。

「巻末に素数表がある。確認してみな」

　愛華は本を開き、先頭からさっと目を通す。先に巻末を見ろ。

「あった。確かに素数だね。これ覚えてたんだ」

「ある程度は。でも、109が素数だったかは覚えてなかった」

「じゃあ、なんで素数だって分かったの？　いくらなんでも速すぎない？」

　そりゃあ、素因数の候補が少なかったからな。俺は口早に説明した。

「ある数が素数かどうかを判定するには、その数の平方根より小さい素数で割りきれるかを調べればいい」

　愛華は首を傾げた。表現が分かりづらかったか。

「今やった109の場合、平方根は大ざっぱに10だ。10より小さい素数は2、3、5、7。109はこの4ついずれも割りきれないから素数だ」　

「109以外の数字でも同じ方法でできるの？」

「ああ。証明も比較的簡単だ」

　俺はそう言ってから、ノートに証明を記した。

　ある自然数nの素因数をx、yとする。つまり、n＝xy

　数の大小関係を√n＜x＜yと仮定して、3つの数を2乗すると、n＜x（　２）＜y（　２）

　n＝xyより、xy＜x（　２）＜y（　２）だが、xはyより小さいのでx（　２）＜xyでなければならない。

　矛盾が生じたのは仮定が間違っていたから。

　素因数の個数を増やしても同様の結果が得られる。

　したがって、nの素因数の中に、√n以下の素数が必ず1つは存在する。

　ノートを愛華に見せると、彼女は顔をしかめた。

「これ、簡単？」

「高校数学の範囲内だと思うぞ。背理法は知ってるだろ」

「知ってるけど……。ていうかさ、『素因数の個数を増やしても同様の結果が得られる』って書いてるけどホント？」

「納得できないなら3つで考えてみよう。nの素因数をx、y、zとしてn＝xyzとする。このとき、√nとx、y、zの大小関係はどうなる」

　俺が訊くと、愛華は少し悩んでから、

「分かんない」

「……じゃあ、仮に√n＜x＜y＜zとしよう。全部2乗したらn＜x（　２）＜y（　２）＜z（　２）だ。これは分かるな」

　愛華は首肯した。

「そんで、n＝xyzだから、xyz＜x（　２）＜y（　２）＜z（　２）だ。この式で矛盾してるところはあるか」

「えーと、zはyより大きいから、xyz＞y（　２）で、yはxより大きいからy（　２）＞x（　２）……分かった！　x（　２）＜y（　２）＜z（　２）＜xyzが正しいんだね」

「いや、z（　２）＜xyzはxとyの値によるから一概には言えない。まあ、示したいのはnの素因数に、少なくとも1つは√n以下の素数があるかどうかだ。だからz（　２）とxyzの大小は別にどっちでもいい」

「なるほど」

　ただ、この判定法はnの値が大きくなるとあまり役に立たない。107123803とかだと、おおよそ1万以下の素数で調べる必要がある。

「私さ、『素因数』っていうのがイマイチ分からないんだよね。因数分解の『因数』

と何が違うの？」　

「因数は約数のことだ。例えば12なら約数は1、2、3、4、6、12の6つ。そのうち素数である2と3が素因数だ」

「素数の約数が素因数？」

「簡単に言えばそうだ。だから、12＝2・6は因数分解だが素因数分解ではない」

　文字式ならa（　２）－b（　２）＝(a＋b)(a－b)のa＋bとa－bが因数にあたる。

「少し思ったんだけど、これまどろっこしくない？　小さい順から割っていくとか」

「まあな。でも、1万以下の合成数で調べるなら充分使えると思う。1万の平方根は100だろ。100以下の素数は25個。電卓を使えば五分程度で素数か判定できる」

「ふぅん」

　2と5の倍数は一の位を見ればすぐ分かるし、3の倍数は各位の数を足せばいい。この方法は数学好きなら大体の人は知っているだろう。

　さっきの109の場合、各位の数の和が10で3の倍数ではないから、3で割り切れない。だから10007が素数かどうか調べたい場合、実質22個の素数で割っていけばいい。ちなみに、このような素数判定法は総当たり法と呼ばれる。

「ほかに素数を判定する方法はあるの？」

「判定法と言えるかは微妙だけど、有名なのはエラトステネスの篩（ふるい）だな」

「それ聞いたことある。倍数を消していくんだよね。2の倍数や3の倍数を消していって、残った数が素数」

「……まあ、そんなところだ」

　愛華の説明を2から10までの自然数で表わすと、こういうことだ（1は素数ではないので最初から除いている）。

　２　3　4　5　6　7　8　9　10　

　まず2の倍数を消す（2は素数なので残す）。

　2　3　5　7　9　

　3の倍数を消す（素数の3は残す）。

　２　3　5　7　

　5以外に5の倍数はないので、残った4つは素数。

「労力あんまり変わんなくない？」

　確かにアナログ的な感じは否めないが、毎度割って調べるよりは効率的な方法だ。

「大きい素数を見つける方法として有名なのはリュカ・テストかな」

「何それ」

「2（　n）－1の形をした数だけに使える判定法だ。愛華、メルセンヌ素数は知ってるか？」

　愛華はかぶりを振った。

「メルセンヌ素数は2（　n）－1の形をした素数のこと。3(2（　2）－1)、7(2（　3）－1)、31(2（　5）－1)がその例だ。よく見れば分かると思うが、メルセンヌ素数はnも素数でなければならない。ただし、逆は成り立たない」

「逆って？」

「nが素数だからと言って、2（　n）－1も素数だとは限らないってことだよ。例えば、nが11のとき2（　11）－1は2047だが、これは残念ながら合成数」

「へぇ、そのリュカ・テストは私にも理解できる？」

　俺は返答に迷った。リュカ・テストの内容はさほど難しくはないが、言葉だけで説明するのは難しい。実際に手を動かした方がいいな。

「理解できなくはない。少しだけやってみるか」

「OK！　どんとこい！」

　やる気入ってんな。

「今回は31で説明する。大きい数だと計算が面倒だからな」

「何？　計算量多いの？」

「少しな。とりあえず説明に入ろう」

　まずは4から始めて、剰余（余り）の2乗から2を引いた数を31で割る。これをひたすら繰り返す。

　a_1＝4

　a_2＝4（　2）－2＝14

　a_3＝14（　2）－2＝194

「194を31で割ると余りは8、これがa_3の値だ。a_4は8を2乗して2を引いた数を31で割った余りだ」

「8の2乗は64でしょ。引く2だから62……あ、割りきれる」

「そう。これで31が素数であることが分かった」

「なるほど。割り切れれば素数ってことね」

「そういうこと。補足すると、127(2（　7）－1)はa_6まで、2047(2（　11）－1)はa_10まで計算して割りきれるかどうかを調べるんだ」

「手間かかるなぁ。電卓使っても大変そう」

　電卓で計算できるのはよくて2（　17）－1までかな。やったことないけど。

　窓から外を見ると日が暮れかけていた。今日はここまでにしよう。

　参考文献

　芹沢正三『素数入門―計算しながら理解できる（ブルーバックス）』講談社　2002年

　リュカ・テストの概要は本書を参考にしました。