目次
素数とは
素数とは、1より大きい自然数で、1とその数以外で割り切れない数のことをいいます。（1は1だけでしか割り切れないので、素数ではありません。）
例えば、100までの素数は以下となります。
2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97
素数の見分け方
与えられた数nが素数かどうかを見分けるには、その数の約数を調べればわかります。（約数：その数を割り切ることができる数）
例えば、23が素数かどうかを見分けるには、23を2, 3, 4, 5,...22までの数で割っていって、割り切れるかどうかを調べます。
2から22の数のなかに23を割り切れる数が1つでもあれば、23は素数ではありません。
しかし2から22の数のなかに23を割り切れる数はないので、23は素数だとわかります。
このように2からn-1までの数で割り切れるかどうかを試すことで、素数かどうかを見分けることができます。
合成数
合成数とは、1より大きい自然数で、素数ではない数のことをいいます。2つ以上の素数の積で表すことができます。
例えば、6や30はそれぞれ2×3、2×3×5と素数の積で表される合成数です。
87はどうでしょう。87も3×29と素数の積で表されるので合成数です。
1729はどうでしょうか。少し時間をかければ、1729＝7×13×19ということがわかり、1729は合成数であることが判明します。
このように素数自体は約数がわかれば難しくありませんが、与えられた数が大きくなると、素数か合成数かの見分けが困難になります。
ここで数学が必要になります。その意味で素数は難しいといえます。
連載「超入門 リーマン予想」でも紹介したリーマンによるリーマン予想（1859年）の発見は、素数を探究した末にたどり着いた深い闇です。
素数判定
与えられた数nが素数であるか合成数であるかを判定する問題のことを素数判定といいます。
素数判定を行うアルゴリズムのことを素数判定法といい、以下の種類があります。
- 決定的素数判定法 例：エラトステネスの篩（ふるい）
- 確率的素数判定法 例：フェルマーテスト、ミラーラビン法
エラストテネスの篩（ふるい）
エラストテネスの篩は、素数かどうかを見分ける基本的かつ簡単な方法として知られています。
大まかな手順は以下のとおりです。
- 与えられた数の範囲の中で最も小さい素数を探す
- その素数の倍数を消す
- 1と2の手順が終わったら、次に最も小さい素数を探し、その倍数を消す
- 上記を繰り返した結果、残った数が素数となる
それではエラストテネスの篩を使って素数を判定してみましょう。
- 与えられた数の範囲を1～100とします。1は素数ではないので、この範囲の中で最も小さい素数は2となります。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 - 2の倍数を消します。（1は素数ではないので1も消しておきます。）
2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 - 次にこの範囲の中で最も小さい数は3なので、今度は3の倍数を消します。
2 3 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97 - 次に5の倍数を消す、その次に7の倍数を消す...と繰り返し、消せる倍数がなくなったところで終了です。
結果として100までのうち残った以下の数が素数は以下となります。
2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97
Pythonで素数判定
こちらのコラムでPythonを使った素数判定プログラミングを紹介していますので、ぜひご覧になってみてください。
フェルマーの小定理を確かめる
フェルマーの小定理といわれる定理があります。
「pが素数ならば、任意の整数nのp乗をpで割った余りはnである」というものです。
ちなみに同じフェルマーによるフェルマーの大定理は、「3以上の自然数nに対してxn+yn=znは自然数の解をもたない」というもので、1994年にワイルズによって証明されました。
ではフェルマーの小定理を具体的に計算して確かめてみましょう。
素数p=3の場合
n=2 23=8 → 3で割ると商が2、余りは2
n=3 33=27 → 3で割ると商が8、余りは3
n=4 43=64 → 3で割ると商が20、余りは4
n=5 53=125 → 3で割ると商が40、余りは5
素数p=5の場合
n=2 25=32 → 5で割ると商が6、余りは2
n=3 35=243 → 5で割ると商が48、余りは3
n=4 45=1024 → 5で割ると商が204、余りは4
n=5 55=3125 → 5で割ると商が624、余りは5
このように余りはnと等しいことがわかります。
もっと大きな数で確かめてみましょう。
素数p=17の場合
n=2 217=131072 → 17で割ると商が7710、余りは2
n=3 317=129140163 → 17で割ると商が7596480、余りは3
n=4 417=17179869184 → 17で割ると商が1010580540、余りは4
n=5 517=762939453125 → 17で割ると商が44878791360、余りは5
やはり最後の余りはnと等しくなります。「任意の整数nのp乗」の指数部分pが素数でないと、こうはなりません。
例えば、指数部分を6とすれば、
素数でないp=6の場合
n=2 26=64 → 6で割ると商が10、余りは4
n=3 36=729 → 6で割ると商が121、余りは3
n=4 46=4096 → 6で割ると商が682、余りは4
n=5 56=15625 → 6で割ると商が2604、余りは1
となり、余りがnと等しくない場合が出てきます。
さてフェルマーの小定理は次のように言い換えることができます。
「pとnは互いに素（公約数が1だけ）のとき、pが素数ならば、任意の整数nのp-1乗をpで割った余りは1である」
先の計算例で再びこのことが成り立つかを確かめてみましょう。
素数p=3の場合
n=2 22=4 → 3で割ると商が1、余りは1
n=3 pとnは互いに素でない。公約数が1以外の3がある。
n=4 42=16 → 3で割ると商が5、余りは1
n=5 52=25 → 3で割ると商が8、余りは1
フェルマーの小定理は合成数の判定法には使える
フェルマーの小定理を次のように言い換えることができます（対偶をとる）。
「pとnは互いに素（公約数が1だけ）のとき、任意の整数nのp-1乗をpで割った余りが1でないならば、pは素数ではない」
すなわち、
「pとnは互いに素（公約数が1だけ）のとき、任意の整数nのp-1乗をpで割った余りが1でないならば、pは合成数である」
ということです。
フェルマーの小定理は合成数の判定法となり得ることがわかります。
例えば、p=8として
pと互いに素であるn=5 57=78125 → 8で割ると商が9765、余りは5 → 余りは1でない → p=8は合成数
これに対して、「余りが1」となる場合はpは素数、合成数どちらにもなります。
p=23として
pと互いに素であるn=5 522=2384185791015625 → 23で割ると商が2384185791015624、余りは1 → p=23は素数！
p=25として
pと互いに素であるn=7 724=191581231380566414401 → 25で割ると商が7663249255222656576、余りは1 → p=25=5×5 は合成数！
フェルマーの小定理は素数の判定法にはなり得ない
残念ながら、フェルマーの小定理は素数判定法にはなり得ません。
しかし、興味深いことに「余りが1」となる場合、pは素数である確率が大きいことがわかっています。
そこで、フェルマーの小定理の計算で最後の「余りが1」となる場合、pはprobable primeと呼ばれています。
probable primeはおおむね素数という意味で、日本語では概素数（がいそすう）と呼ばれます。
概素数
概素数とは、素因数を2つしかもたない合成数のことを指します。
フェルマーの小定理を用いることで、probably（おそらく）素数であることが判定できます。それゆえ、このような素数判定法を確率的素数判定法と呼びます。
フェルマーの小定理を用いた確率的素数判定法は「フェルマーテスト」と呼ばれます。
さて、正確な表現として、pとnは互いに素（公約数が1だけ）のとき、整数nのp-1乗をpで割った余りが1である場合のpのことをnを底とした概素数と呼び、n-PRPと書きます。
そして、素数でない（合成数である）概素数のことを擬素数（ぎそすう、pseudoprimes）と呼びます。素数もどき、という意味です。
工業レベルの素数
25,000,000,000（250億）以下には、素数は1,091,987,405（約10億）個存在します。
同じ範囲に2を底とする擬素数（合成数の概素数）は21,853個（0.0000874％）しかありません。
事実、擬素数は素数に比べて珍しいことがエルデシュによって1950年に証明されています。
このことからHenri Cohen（コーエン）は2-RPRを「工業レベルの素数」と呼んでいます。
確率的素数判定法によって見つかる素数のように、実用上問題ない精度で判定できる素数をこう呼びます。
インターネット上で用いられるRSA暗号には2つの巨大な素数が必要ですが、確率的素数判定法であるミラーラビン法によって見つかる工業レベルの素数が用いられています。
驚異のカーマイケル数
高速な素数判定のために、フェルマーの小定理を用いた確率的素数判定法「フェルマーテスト」を様々な底nについて（底2を試し、次に底3、次に底5、…）行うことで、厳しい素数判定ができるようになります。
ところが、すべての底nに対してフェルマーテストで「余りが1」になる擬素数が存在するという衝撃的な事実が明らかになりました。
1910年、Carmichael（カーマイケル）によって発見されました。
このカーマイケル数は、自身と互いに素である任意の底でフェルマーテストをすり抜ける合成数で、絶対擬素数（absolute pseudoprimes）とも呼ばれます。
561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361
100,000以下のカーマイケル数
素数は面白い
素数は難しい。
私自身、28番目メルセンヌ素数286243-1（25962桁）の素数判定を行ってみてそのことを実感しました。
しかし同時に「チャレンジするに値する数が素数である」ことを強く感じました。
概素数、擬素数、工業レベルの素数、カーマイケル数、絶対擬素数。
これらの言葉たちが、私たちが素数にチャレンジしてきた軌跡を物語ります。
