『素数』を数えて落ちつくんだ……。“素数の無限性”の証明する「エラトステネスの篩」「ユークリッドの証明」「エルンスト・クンマーの証明」をやさしく解説してみた
ニコニコニュース / 2021年4月5日 19時0分
今回紹介するのは、Gaudaro440さんが投稿した『【ゆっくり数学】素数の無限性と3つの証明』という動画です。音声読み上げソフトを使用して、素数が無限に存在することの証明についての解説を行いました。
エラトステネスの篩の素数判定法
霊夢:
まず、エラトステネスの篩という素数判定法の紹介をする。この方法自体はかなり有名だから、知っている人も多いかもしれない。おまけにエラトステネスは紀元前200年に活躍したエジプト数学者、つまりかなり古い時代に考案されたやり方なんだ。たとえば2~20までの数字があったとする。この中から素数となるものを見つけ出す。やり方は単純、まず2以外の偶数をすべて消す。次に3以外の3の倍数を全部消す。はい、終わり。
これで残ったやつが素数です。エラトステネスの篩の最強なところは、この圧倒的計算量の少なさである。このためアルゴリズムに使われたりする。さて、このエラトステネスの篩から、こんな疑問が生じる。先程は1から20までで考えていたが、これを無限個の自然数で操作するとき、そして操作が有限回で終わるかどうかというのは、素数が有限個か無限個か? という問いと同じになる。
実は、素数は無限に存在する。篩は限られた自然数の中で素数を見つけ出すには最強だが、残念ながらこれで素数が無限個あることは証明できない。しかし、かわりにいろんな数学者が素数が無限にあることを証明してくれた。
ユークリッド(エウクレイデス)の証明
霊夢:
古代エジプトの最強数学者、エウクレイデス。またの名をユークリッドである。「幾何学の父」とか言われたりして、非常に有名で多大な貢献をした数学者である。では彼の証明を見ていこう。
まず、素数が有限個であると仮定する。それをp_1、p_2……p_Nとおいていく。こんどはその有限個の素数の全部の積に1を足したQという数字を考える。こいつはおのおののpで割れない。
しかし2以上の自然数はなにかしらの素数を約数にもっているはずなので、ここで矛盾が発生する。これはつまり、「新たな素数が必要だ」ということを意味している。
エルンスト・クンマーの証明
霊夢:
次に紹介するのは、エルンスト・クンマーの証明。クンマーは19世紀に活躍したドイツの数学者。それでは証明を見ていこう。クンマーの証明も、ユークリッドと同様、素数が有限個であるという仮定からはじまる。次にNを有限個の素数全部の積としてN-1という数を考える。N-1はN個ある素数のどれかで割り切れるはずである。
ここで有限個ある素数のうち、p.jという素数がN-1を割り切るとする。p.jは当然Nも割り切るはずである。したがって、NとN-1の差である1も割り切るはずであるが、これは素数が2以上であることに矛盾する。したがって素数は無限に存在する。
ジョージ・ポリアの証明
霊夢:
最後にポリアの証明である。ジョージ・ポリアはハンガリー生まれのアメリカの数学者で、20世紀半ばにはスタンドフォード大学で教授を務めていたときもあった。フェルマーは当初、「フェルマー数はすべて素数」と考えていた。しかし残念ながらn=5のときは合成数であることをオイラーが証明した。ちなみにnが5以上のときにフェルマー数が素数でないかどうかは未解決である。しかしこのフェルマー数を用いれば、素数が無限にあることを証明することができる。
まず、フェルマー数を割り切る素数pをもってくる。ここで後で示す補題「素数pがフェルマー数の約数」ならば、「pはそれより前の項のフェルマー数の約数ではない」ということから、それぞれの項のフェルマー数を割り切る素数と異なることを意味する。フェルマー数は無限に作ることができるから、異なる素数も無限に作れる。
したがって素数が無限に存在することを示すことができた。このように同じ命題に対して複数の証明が考えられることも、数学の醍醐味だったりする。ここで取り上げた証明以外にも、たとえばオイラーも素数の無限性の証明をしているので、興味がある方は調べてみてほしい。
なんとも奥が深い数学の世界。詳しい解説は動画をご覧ください。
・35年間未解明だった「ABC予想」をやさしく解説してみた。証明されるメリットとは? 謎に満ちた数学の宇宙を覗いてみませんか
外部リンク
この記事に関連するニュース
-
「数に強い人」「弱い人」を一瞬で見抜く算数クイズ 面倒くさい計算は「発想の転換」でスキップする
東洋経済オンライン / 2024年7月6日 11時0分
-
「素数」はランダムではない 出現周期に現れる“偏り”とは? 2016年発表の論文を紹介
ITmedia NEWS / 2024年7月4日 8時5分
-
『NHKテキスト 3か月でマスターする 数学』放送反響受け、売上好調につき大増刷決定!
PR TIMES / 2024年7月3日 13時15分
-
「面倒くさがりな子」ほど数学ができる驚きの理由 「どこかで楽ができないか」と考える子が伸びる
東洋経済オンライン / 2024年6月12日 9時0分
-
アルゴリズムとプログラミングの理解・技術力向上を目指すならこの一冊! 『計算論的思考を育むPythonプログラミング実践問題集』発行
PR TIMES / 2024年6月7日 13時15分
ランキング
-
1Google検索も不要に? 検索AI「Perplexity」がスゴすぎてちょっと怖い
ITmedia NEWS / 2024年7月5日 19時16分
-
2プリングルズ価格改定 ショート缶は容量そのままサイズ変更して空間率減少へ
ねとらぼ / 2024年7月5日 16時20分
-
3「コレのせいやったんか」 最近スマホが重い → “とんでもない理由”が判明……!? 「自分もやってた」「4年以上経ちました」と猛者たち集結
ねとらぼ / 2024年7月5日 16時0分
-
4VTuber・犬山たまき所属事務所、誹謗中傷した人物との間で和解成立―当初「示談金の支払などは行わない」と回答するも訴訟提起で一転
インサイド / 2024年7月5日 16時55分
-
5ランサムウェア被害、報告続出 イセトーサイバー攻撃で今わかっていること(7月5日時点)
ASCII.jp / 2024年7月5日 15時45分
記事ミッション中・・・
記事にリアクションする
記事ミッション中・・・
記事にリアクションする
エラーが発生しました
ページを再読み込みして
ください