素数は無限にあるか？わかりやすく｜ユークリッドの証明（背理法）・だれが証明・最大の素数

素数は無限にあるか（ユークリッドの証明）とは？（ひとことで）

「素数は無限にあるか」という問題の答えは、「ある。素数はどこまでも続く」です。これを最初に証明したのが、古代ギリシャの数学者ユークリッドの業績と生涯で、紀元前300年ごろに書かれた『原論』の第9巻に載っています。2300年以上たった今も、世界でもっとも美しい証明の一つと言われます。

証明の中身は、とてもかんたんです。「素数が全部で何個かしかないとする。その全部をかけ合わせて1を足した数を考えると、どの素数でもわり切れない。これは、リストにない新しい素数が必要だということだから、矛盾する」。使うのはかけ算・足し算・割り算の余りだけで、中学生でも理解できます。そして、背理法とは何かという証明の型をはじめて学ぶのに、いちばんよい例の一つです。

この問題は、ゴールドバッハ予想（偶数は素数2つの和？）や双子素数予想（差が2の素数は無限にある？）のように今も解けていない問題とはちがい、すでに解決ずみです。ただし、「素数が無限にある」とわかったあとにも、「ではどのくらいの割合で出てくるのか」「差が2の組はどうか」と、つぎつぎに新しい問いが生まれました。その入口にあたる、数論でもっとも大事な定理です。素数について知りたい人は、唯一の偶数の素数「2」の話や2027は素数？双子素数と西暦の入試問題もあわせて読んでみてください。

素数が無限にあるとは？問題の意味をやさしく解説

素数とは

素数とは、1とその数自身でしかわり切れない、2以上の整数です。2、3、5、7、11、13、…と続きます。1は素数に入れません。また、偶数の素数は2だけです。素数の定義と見分け方をまず確かめましょう。素数でない2以上の整数（合成数）は、素数のかけ算に分けられます。これが素因数分解と約数の個数です。素数は、あらゆる整数をつくる「原子」のようなものです。

「無限にある」とはどういうこと？

「素数は無限にある」とは、「どんなに大きな数を考えても、それより大きな素数がかならず見つかる」ということです。言いかえると、「最後の素数」は存在しない、ということです。これを数学では「素数の集合は無限集合である」と言います。

注意したいのは、「たくさんある」と「無限にある」はちがうことです。「100までに25個」「1000までに168個」とふえていても、それだけでは「無限」とは言えません。どこかで止まるかもしれないからです。止まらないことを、すべての場合をおおって示す必要があります。ここに証明の出番があります。

証明の手順を、例でたどる

ユークリッドの考え方を、小さな数で試してみます。まず「素数はこの何個かだけ」というリストを作ります。リストの素数を全部かけて、1を足すのです。

• リストが {2} だけなら、2＋1＝3。3は素数で、リストにない新しい素数。
• リストが {2, 3} なら、2×3＋1＝7。7も新しい素数。
• リストが {2, 3, 5} なら、2×3×5＋1＝31。31も新しい素数。
• リストが {2, 3, 5, 7} なら、210＋1＝211。211も素数です。
• リストが {2, 3, 5, 7, 11, 13} なら、30030＋1＝30031。これは素数ではなく、59×509です。

最後の例が大事です。30031は素数ではありません。でも、59も509も、リスト {2, 3, 5, 7, 11, 13} には入っていません。新しい素数が因数として出てきたのです。これがユークリッドの証明の核心です。「かけて1を足した数が素数だ」とは言っていません。「リストにない素数をかならず1つ生み出す」と言っているのです。

よくある誤解：「かけて1を足すと素数になる」？

この証明を読んで、「素数を全部かけて1を足した数は素数になる」と思いこむ人がいます。これはまちがいです。上の30031が反例です。ほかにも、2×3×5×7×11×13×17＋1＝510511＝19×97×277 のように、素数でない例が続きます。ユークリッドが言っているのは、「その数は、リストのどの素数でもわり切れない。だから、素因数分解したとき、リストにない素数が出てくる」ということだけです。

また、「ユークリッドの証明は、素数をつぎつぎに作る方法だ」という言い方も、実は少し正確ではありません。小さい順に素数を作る方法ではなく、「有限のリストでは足りない」ということを示す証明だからです。

素数が無限にあることの歴史と年表

紀元前300年ごろ：ユークリッドの『原論』

ユークリッドは古代ギリシャのアレクサンドリアで活躍した数学者とされ、その著書『原論』は、2000年以上にわたって数学の教科書でした。第9巻の命題20は、現代の言葉で書くと「素数は、どんな有限個の素数の集まりよりも多い」という内容です。ユークリッドは「素数は無限にある」とは書かず、「どんな素数の個数より多い」と言いました。ギリシャ人は「無限」という言葉を慎重に扱ったからだと説明されることがあります。

なお、『原論』の証明は、よく言われる背理法ではなく、場合分けの形で書かれているという指摘があります。「Nが素数なら新しい素数、Nが素数でないなら新しい素因数」の2つに分ける形です。一方、現代の教科書では、背理法の形で書かれることが多いです。

1737年：オイラーの証明（素数の逆数の和）

オイラーの業績と生涯は、まったく別の方法で証明しました。素数の逆数をすべて足した$\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\cdots$という和が、どこまでも大きくなる（発散する）ことを示したのです。もし素数が有限個なら、この和は有限の値で終わるはずなので、素数は無限にあることになります。オイラーのこの結果は1737年に見つけられ、論文として出たのは1744年です（といわれます）。

この方法は、ユークリッドの証明より「強い」結果をもたらします。素数が無限にあるだけでなく、素数がじゅうぶん多い（逆数の和が発散するほど）ことまで分かるからです。たとえば、平方数（1、4、9、16、…）の逆数の和は有限の値 $\frac{\pi^2}{6}$ になりますから、素数は平方数よりも「多い」ことになります。この考え方は、リーマン予想（素数の分布のかぎ）や、素数がどのくらい出てくるかを調べる素数定理（素数の散らばり方の法則）へつながっていきます。

18〜19世紀：さまざまな証明

ゴールドバッハは、フェルマー数 $F_n=2^{2^n}+1$ のどの2つも「互いに素」（共通の約数が1だけ）であることを使って、素数が無限にあることを示したと伝えられます。1878年には、ドイツの数学者クンマーがユークリッドの証明を少し形を変えて書き直しました（積に1を足す代わりに、小さい素数の積から1を引く形です）。

20世紀：位相空間から数え上げまで

1938年ごろには、エルデシュの業績と生涯が「平方数を使う数え上げ」の証明を示したことが知られています（平方因子のない数と平方数の積で、すべての整数を書く方法です）。1955年には、ヒレル・フルステンバーグが位相空間という大学数学の道具を使った、たった1ページの証明を発表しました。数論の問題が、まったく別の分野の言葉で証明できてしまう――その鮮やかさで有名です。

素数が無限にあることは、いつ・だれが証明した？

この問題は、紀元前300年ごろに、ユークリッドが解決しました。すでに解決ずみの問題なので、「今どこまで分かっているか」ではなく、証明の中身をていねいに見てみましょう。

ユークリッドの証明（現代風）

1. 仮定：素数が有限個だとして、その全部を $p_1, p_2, \dots, p_n$ とする。
2. 数をつくる：$N = p_1 \times p_2 \times \cdots \times p_n + 1$ という数を考える。
3. 調べる：$N$ を $p_1$ でわると、$p_1 \times (\text{ほかの全部})$ の部分はわり切れるので、余りは1。$p_2, \dots, p_n$ でわっても、どれも余りは1。つまり、$N$ はどの $p_i$ でもわり切れない。
4. 矛盾：$N$ は2以上の整数なので、素数であるか、素数のかけ算に分けられるかのどちらか。素数なら、それはどの $p_i$ とも別の素数。素数でなければ、$N$ の素因数がある。その素因数もどの $p_i$ でもない。どちらにしても、「リストにない素数」がある。これは「$p_1, \dots, p_n$ が素数の全部」という仮定に反する。
5. 結論：素数が有限個という仮定がまちがい。だから、素数は無限にある。

このなかで、「余りが1になる」というところが、合同式（mod の計算）の使い方の考え方です。合同式で書くと、$N \equiv 1 \pmod{p_i}$ です。

オイラーの証明（概略）

オイラーは、「素数だけで作れる数」の足し算を、すべての整数の足し算とくらべました。素数だけを材料にして、整数 $1, 2, 3, \dots$ の逆数 $\frac{1}{n}$ をすべて足したもの（調和級数）は、つぎのように素数の積の形に書けます：

$$\sum_{n=1}^{\infty}\frac{1}{n}=\prod_{p}\frac{1}{1-\frac{1}{p}}$$

左側は、収束と発散でいう発散（どこまでも大きくなる）です。もし素数が有限個なら、右側は有限の値になるはずなので、等号が成り立ちません。だから、素数は無限にある。これが、素因数分解が1通りだけであること（素因数分解の一意性）を使った、オイラーの証明です。

エルデシュの証明（数え上げ）

エルデシュの証明は、「数の個数を数える」だけで終わります。素数がもし $k$ 個しかないとします。1以上 $N$ 以下の整数は、$a \times b^2$（$a$ は平方因子をもたない数）の形に1通りに書けます。$a$ の選び方は、素数が $k$ 個なら高々 $2^k$ 通り、$b$ の選び方は高々 $\sqrt{N}$ 通りです。だから $N$ 以下の整数の個数 $N$ は、$2^k\sqrt{N}$ 以下でなければなりません。でも、$N$ をじゅうぶん大きくすると $N > 2^k\sqrt{N}$ になって矛盾します。この証明は、「素数が少なすぎると、数を作り切れない」という考え方です。さらに、$N$ 以下の素数が少なくとも $\frac{1}{2}\log_2 N$ 個はあることまで読み取れます。

フルステンバーグの証明（位相）

整数を等差数列で「区切る」特別な位相を定めると、素数の倍数の集まりが「開かつ閉」になります。もし素数が有限個なら、$\{-1, 1\}$ 以外のすべての整数が、有限個の閉集合の和になってしまい、$\{-1, 1\}$ が開集合になる、という矛盾が出ます。位相空間の言葉を知らないと分かりにくいですが、「数論の問題を、別の分野の道具で解く」例として有名です。

では、最大の素数は？

素数が無限にあるので、「最大の素数」は存在しません。ただし、「人間が見つけた中で最大の素数」はあります。2024年10月に、アメリカのルーク・デュラント氏が、GIMPS（ギンプス：世界中のコンピューターを使ってメルセンヌ素数を探すプロジェクト）で、$2^{136279841}-1$ という数が素数であることを見つけました。これは41,024,320桁の数で、52番目のメルセンヌ素数です（順位は暫定）。2024年10月12日の発見で、2026年11月時点でもGIMPS公式ページで最大のままです。ユークリッドの証明によって、この数よりも大きな素数がまだ必ずあると分かっています。

素数の問題は、なぜ奥が深い？

「素数が無限にある」こと自体の証明は、2300年前にすでに終わっています。それでも素数が数学者を引きつけ続けているのは、「無限にある」の先にある問いが、どれもとても難しいからです。ここでは、その理由を3つに分けて見てみます。

1. 素数は「かけ算」でできていて、「足し算」と合わない

素数は、かけ算で分けられない数として決まります。ところが、素数がどこに並んでいるかは、足し算の世界（1、2、3、…と順に数える世界）で見ると、ふしぎなほど不規則です。2、3、5、7 のあと、11、13、17、19、23、…。次の素数がどこに現れるかを決める簡単な式は、見つかっていません。「素数をすべて並べて出す式」は、今も見つかっていないのです。

2. 「無限にある」だけでは、散らばり方は分からない

ユークリッドの証明は、「かならずある」ことしか教えてくれません。たとえば「1000以下に素数は何個あるか」は、証明からは出てきません。この疑問に答えたのが素数定理（x以下の素数はおよそ x÷log x 個）で、証明は1896年まで待たなければなりませんでした。さらに、リーマン予想が解ければ、誤差まで正確に分かると考えられています。

3. 「差が小さい素数」「和で書ける素数」は、今も未解決

素数が無限にあるのなら、差が2の素数の組（3と5、11と13、…）は無限にあるのか――これが双子素数予想で、今も未解決です。また、ゴールドバッハ予想（偶数は素数2つの和）も未解決です。「素数が無限にある」と分かっても、「どんな形の素数が無限にあるか」は、一つひとつ調べなければなりません。

そのなかで、等差数列の中に素数が無限にある、という結果（1837年、ディリクレの業績と生涯）や、「素数の中にいくらでも長い等差数列がある」という結果（2004年、グリーンとタオ）は、解決ずみです。

受験・勉強と「素数は無限にある」のつながり

中学受験：素数を使いこなす

中学受験の算数では、素数に関する問題が毎年のように出ます。基本は100までの素数25個を覚えることです。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。そして「ある数が素数か調べる」には、その数の平方根以下の素数でわってみれば十分です。たとえば 97 が素数か調べるなら、$\sqrt{97}$ は10に近い数なので、2、3、5、7 でわって、どれもわり切れなければ素数と分かります。整数の性質（約数の個数・倍数の判定）と素因数分解と約数の個数をセットで練習しておきましょう。

「エラトステネスのふるい」（2の倍数、3の倍数、…を消していって、残った数が素数）は、小学校高学年の自由研究にぴったりです。エラトステネスの業績と生涯は、ユークリッドとほぼ同じ時代の人です。

高校受験・大学受験：背理法と整数の証明

ユークリッドの証明は、高校数学で習う背理法の最初の見本です。「$\sqrt{2}$ は無理数である」の証明と並んで、入試の定番です。型は同じで、①結論を否定して仮定する、②そこから矛盾を導く、③だから仮定がまちがい、の3ステップです。背理法の考え方と命題と証明の考え方を確かめておきましょう。

大学入試では、ユークリッドの証明をまねる問題がよく出ます。つぎのような問題です。

例題：4で割って3余る素数は、無限にあることを示せ

有限個だとして、全部を $p_1=3, p_2=7, \dots, p_n$ とします。$P=p_1p_2\cdots p_n$ として、$N=4P-1$ を考えます。

• $N$ は奇数で、$N\equiv 3\pmod 4$ です（4で割ると3余る）。
• もし $N$ のすべての素因数が「4で割って1余る」なら、それらの積である $N$ も4で割ると1余ります。これは矛盾。だから、$N$ には「4で割って3余る」素因数 $q$ がある。
• この $q$ は、どの $p_i$ とも等しくありません。もし $q=p_i$ なら、$q$ は $N$ と $4P$ の両方をわり切るので、$1=4P-N$ をわり切ることになり、不可能です。
• これは「$p_1,\dots,p_n$ が全部」という仮定に反するので、4で割って3余る素数は無限にあります。

同じ方法は、「6で割って5余る素数」「3で割って2余る素数」でも使えます。ただし、「4で割って1余る素数」では、この方法は少し形を変える必要があります。ここで合同式（合同式の使い方）に慣れていると、とても楽です。この一般の場合が、ディリクレの算術級数定理（1837年）です。大学入試の範囲ではありませんが、数学オリンピックなどでは使われます。

「連続した合成数」の問題

入試でよく出るもう一つの定番が、「連続する $n$ 個の合成数（素数でない数）を作れ」という問題です。答えは $(n+1)!+2, (n+1)!+3, \dots, (n+1)!+(n+1)$ です。たとえば $n=5$ なら $6!+2=722$ から $6!+6=726$ までの5個が、それぞれ 2、3、4、5、6 でわり切れます。ここから、素数と素数の間はいくらでも広がることが分かります。素数が無限にある一方、すき間も限りなく大きくなる。この2つの事実は、同時に成り立つのです。

勉強法として：「ありえない」を見つける力

ユークリッドの証明から学べるのは、「つくった数が、どの素数でもわり切れない」ことに気づく力です。入試の整数問題では、「1を足す」「1を引く」「階乗を使う」といった工夫で、わり切れない数をつくる場面がよく出ます。自分で手を動かして、小さな数で実験することが大切です。数学の勉強の進め方は、数学の勉強法（解法の暗記→演習→過去問）も参考にしてください。

「素数が無限にある」が数学・社会にあたえた影響

• 背理法という証明のお手本：2000年以上、「証明とはこういうもの」というお手本として読まれてきました。ハーディは『ある数学者の弁明』のなかで、ユークリッドの素数の証明を「第一級の数学」の例として取り上げています。
• 解析的整数論のはじまり：オイラーの証明は、素数と無限級数をむすびつけました。そこから、ディリクレの算術級数定理、素数定理、リーマン予想へと、素数を解析学で調べる道が開けました。
• 暗号の安全性：インターネットで使われるRSA暗号は、「大きな素数を2つ見つけるのは簡単だが、その積を素因数分解するのは難しい」ことに頼っています。素数が無限にあるから、毎回「新しい大きな素数」を選べるのです。
• コンピューターによる素数探し：メルセンヌ素数（$2^p-1$ の形の素数）を探すプロジェクトは、世界中の人々がパソコンの空き時間を提供して続けています。見つかった素数は、完全数（約数の和が自分の2倍になる数）ともつながっています。
• 「無限」を扱う数学の基礎：「有限個では足りない」という論法は、集合論やヒルベルトの業績と生涯の「無限ホテル」の話など、無限を扱う数学全体の考え方につながっています。

ガウスの業績と生涯は15〜16歳のころに、素数の表をながめて「x以下の素数の個数は、およそ $x/\log x$」という予想を立てたと伝えられます。「素数が無限にある」とわかった次に、「どのくらいあるか」を問うたのです。それは、ユークリッドの証明から2000年以上たってからの、新しい一歩でした。

素数の無限に挑戦！練習問題

「素数は無限にある」と関係する数学者・難問

• ユークリッド（原論の著者）：紀元前300年ごろ、素数が無限にあることを最初に証明しました。
• オイラー：素数の逆数の和が発散することを示し、解析的整数論の道を開きました。
• エルデシュ：数え上げによる、短くて美しい別証明で知られます。
• ディリクレ：1837年、等差数列の中に素数が無限にあることを証明しました。
• 素数定理・ゴールドバッハ予想・双子素数予想・リーマン予想：素数の「無限」の先にある、散らばり方と並び方の難問です。

ほかの解かれた難問・決着した問題

• 三大作図問題とは（不可能・決められないと証明）
  定規とコンパスだけで、円と同じ面積の正方形・体積2倍の立方体・角の三等分を作図できるか。どれも不可能と証明された
• 平行線公準の問題とは（不可能・決められないと証明）
  ほかの公理から平行線の公理を証明できるか。証明できず、成り立たない幾何学（非ユークリッド幾何学）もあると分かった
• 5次方程式の解の公式とは（不可能・決められないと証明）
  2次・3次・4次方程式のような、四則と累乗根だけの解の公式が5次方程式にもあるか。一般にはないと証明された
• ケプラー予想とは（解決）
  同じ大きさの球をいちばん密に詰める方法は、八百屋のみかんの積み方か。コンピューターで証明
• フェルマーの最終定理とは（解決）
  n≧3 のとき xⁿ＋yⁿ＝zⁿ をみたす自然数はない。360年近く解けなかった
• バーゼル問題とは（解決）
  1＋1/4＋1/9＋1/16＋… はいくつか。答えは π²/6
• ケーニヒスベルクの橋の問題とは（解決）
  7つの橋を1回ずつ渡って元にもどれるか。できないと示し、グラフ理論が生まれた
• 円周率の超越性とは（解決）
  π はどんな整数係数の方程式の解にもならない。これで円積問題が不可能と決まった
• ウェアリングの問題とは（解決）
  どの自然数も、決まった個数の k 乗数の和で書けるか（3乗なら9個）
• 素数定理とは（解決）
  x 以下の素数はおよそ x/log x 個ある、という素数の散らばり方の法則

← 前の時代：平行線公準の問題とは（不可能・決められないと証明）　｜　次の時代：5次方程式の解の公式とは（不可能・決められないと証明） →

数学の難問・未解決問題の一覧（いつ・だれが解いたか）　｜　有名な数学者一覧

読みもの（合格大作戦の数学の記事）

• 唯一の偶数の素数「2」の話
  素数から学ぶ逆転合格の考え方
• 2027は素数？双子素数と西暦の入試問題
  2027＝45²＋2
• 算数・数学の公式一覧（公式辞典）
  公式・証明・例題を1つずつ
• 数学用語辞典（用語の意味を1語1ページ）
  素数・漸近線など200語
• 数学の勉強法（解法の暗記→演習→過去問）
  青・黄・赤チャートの使い分け
• 数学オリンピックの問題（長方形に詰めた正方形）
  中学生でも解ける本番の問題
• 京大の素数ものさしとは？使い方と答え
  素数の目盛りだけで長さを測る

よくある質問

あわせて読みたい

• 数学の難問・未解決問題の一覧
• 有名な数学者一覧
• 算数・数学の公式一覧（公式辞典）