素数に関する式と定理
素数は1とその数自身しか約数を持たない数。英語の「prime number」からpと表されることが多い。
素数が無限個存在することは紀元前から知られており、ユークリッド原論にその証明が記されている。
「『原論』に載っている証明は、ピタゴラスが発見したという説が有力らしい」
「ピタゴラスってピタゴラスの定理でしか知らないけど、素数の証明してるんだ」
「あくまでも説だけどな。現代風に書くとこんな感じだ」
素数のリスト2、a、bをすべて掛けて1を加えた数をcとする。つまり、2ab+1=c。
cは2、a、bどれでも割り切れないので、cは素数、もしくはcを割り切る2以上の奇素数を約数に持つ合成数である。
この操作によって出力される数は、その数自身が素数であるか、リストにはない素数を約数に持つ合成数である。
出力される数が素数、合成数どちらであっても、リストにはない新しい素数をいくらでも得ることができる。したがって、素数は無限に存在する。
「……文字だけだとわかりづらい」
「だったら試しに2で始めて見るか」
2+1=3 3は素数
2・3+1=7 7は素数
2・3・7+1=43 43は素数
2・3・7・43+1=1807 1807=13・139
2・3・7・43・13+1=23479 23479=53・443
出力された数の最小の素因数をリストに加わった順に並べた数列
2、3、7、43、13、53、…
はEuclid–Mullin sequenceと呼ばれる。
「やっぱり数字の方がわかりやすい」
「数学の証明は抽象的だからな。ピンと来ないときは具体的な数で試すと理解の助けになる」
「でも、素数かどうか確かめるの面倒だよね。この1807とか」
「まあな。素数判定ができる式というか、定理は一応あるけど」
「え、そうなの? どんな定理?」
「ウィルソンの定理と呼ばれるものだ」
ウィルソンの定理はpが素数のとき、(p-1)!+1はpで割り切れる。合同式で書くと、
(p-1)!+1≡0(mod p)
一般的な数学書では1を右辺に移項させて、
(p-1)!≡-1(mod p)
とすることが多い。
p=5のとき
(5-1)!=24
24≡-1(mod 5)
「ただ、ウィルソンの定理はpの値が大きくなると、算出される値が爆発的に増えるから実用的ではない」
現時点で実用的なのはメルセンヌ素数のような
「なんだ。つまんないの」
「その代わりと言ってはなんだけど、面白い式はいくつか発見されている」
特筆すべきはオイラーが発見した
41、43、47、53、61、71、83、97、113、131、151、173、197、223、251、281、313、347、383、421、461、503、547、593、641、691、743、797、853、911、971、1033、1097、1163、1231、1301、1373、1447、1523、1601
「この40個が全部素数なんだ。オイラーすごすぎない?」
「オイラーの業績は数多いが素数に関しても残している」
特に素数の逆数の和が無限大に発散する性質を利用して、素数が無限に存在することを証明したことは数学界では有名な話だ。
「ほかには、ベン・グリーンとテレンス・タオの論文に23連続で素数を生成する式が載っている」
56211383760397 + 44546738095860k
実際にkに0から22まで代入して計算するとすべて素数になっている。
56211383760397、100758121856257 、145304859952117 、189851598047977、234398336143837 、278945074239697 、323491812335557 、368038550431417、412585288527277 、457132026623137 、501678764718997 、546225502814857、590772240910717 、635318979006577 、679865717102437 、724412455198297、768959193294157 、813505931390017 、858052669485877 、902599407581737、947146145677597 、991692883773457 、1036239621869327
「この式の面白いところはkの係数、44546738095860を素因数分解すると、2から23までの素数がすべて表れるところだ」
44546738095860=
「しかも、項数がいくらでも長い素数の等差数列は無限に存在することがグリーンとタオによって2004年に証明された。今では『グリーン=タオの定理』と呼ばれている」
「証明したのは充分すごいけど、どうやったらこんな式発見できるんだろ……」
「さあな」
コンピューターを使ったのは間違いないけど具体的な方法は知らない。
「さっき挙げた二つの式は1変数だけど、マチャセビッチという数学者は19変数37次の多項式を発見している。ただ、変数が多すぎて実用的ではないのが現状だ」
「19変数ってことは19個の文字が使われてるってことだよね。めちゃくちゃ複雑そう」
素数は本当に謎だらけの数だ。だからこそ多くの数学者を惹きつけ、RSA暗号のようなセキュリティー技術にも応用されている。オイラーが知ったらどう思うだろう。
参考文献
小島寛之 『素数ほどステキな数はない 素数定理からゼータ関数まで』 技術評論社 2021年
Green and Terence Tao 『The primes contain arbitrarily long arithmetic progressions』 Annals of Mathematics, 167 (2008), 481–547
新規登録で充実の読書を
- マイページ
- 読書の状況から作品を自動で分類して簡単に管理できる
- 小説の未読話数がひと目でわかり前回の続きから読める
- フォローしたユーザーの活動を追える
- 通知
- 小説の更新や作者の新作の情報を受け取れる
- 閲覧履歴
- 以前読んだ小説が一覧で見つけやすい
アカウントをお持ちの方はログイン
ビューワー設定
文字サイズ
背景色
フォント
組み方向
機能をオンにすると、画面の下部をタップする度に自動的にスクロールして読み進められます。
応援すると応援コメントも書けます