【新人エンジニア向け】素数が無限に続く不思議！ユークリッドの証明をサクッと理解しよう

2025年12月20日 2025年12月20日山崎講師

山崎講師

こんにちは。ゆうせいです。

エンジニアとして働き始めると、セキュリティや暗号技術の話の中で「素数」という言葉を耳にする機会が増えますよね。でも、改めて「素数ってなんで無限にあるの？」と聞かれたら、パッと答えられますか。

実は、素数が無限に存在することは、古代ギリシャの時代から知られている事実なんです。しかも、その証明方法は驚くほどシンプルで美しいロジックに基づいています。

きょうは、この「素数が無限に続くこと」を、数学が苦手な方でも直感的にわかるように解説していきます。論理的思考力を鍛えるトレーニングだと思って、一緒に頭を働かせてみましょう！

素数とは何か？数の「原子」を知ろう

証明に入る前に、まずは素数についておさらいしておきましょう。

素数とは、1と自分自身以外では割り切れない、1より大きい整数のことです。

例えば、2、3、5、7、11などがそうです。逆に、4は2で割り切れますし、9は3で割り切れるので素数ではありません。

これを化学の世界に例えるなら、素数は「原子」のようなものです。すべての物質が原子の組み合わせでできているように、すべての整数は素数のかけ算（素因数分解）で表すことができます。

たとえば、12という数字は以下のように分解できます。

12 $=$ 2 $\times$ 2 $\times$ 3

このように、数を構成する最小単位が素数なのです。では、この「数の原子」はどこかで尽きてしまうのでしょうか。それとも無限に存在するのでしょうか。

背理法という強力な武器

素数が無限にあることを証明するために、今回は「背理法」というテクニックを使います。

背理法とは、証明したい事柄の「逆」を仮定して、そこから矛盾を導き出すことで、元の命題が正しいことを示す方法です。

少し難しそうに聞こえるかもしれませんが、日常会話でもよく使っています。

たとえば、「彼は今、家にいない」ことを証明したいとします。「もし彼が家にいるなら、部屋の電気がついているはずだ。でも電気は消えている。だから彼は家にいない」という理屈です。

逆を仮定する（家にいるはず）
矛盾を見つける（でも電気は消えている）
結論（やっぱり家にいない）

この流れを、素数の証明にも当てはめてみましょう。

素数が無限にあることの証明

それでは、いよいよ本題です。古代ギリシャの数学者ユークリッドが考えた、エレガントな証明をご紹介します。

まず、背理法を使うので、あえて間違った仮定をします。

「素数は有限個しかない（数に限りがある）」と仮定しましょう。

もし素数が有限個しかないなら、世界中のすべての素数をリストアップできるはずです。そのリストにある最大の素数までを、すべて並べたと想像してください。

ここでは、そのすべての素数を掛け合わせた数に、1を足した新しい数を作ってみます。この数を $Q$ と呼びましょう。

$Q =$ (すべての素数を掛けたもの) $+$ 1

言葉だけだとわかりにくいので、具体例を出しますね。仮に、この世に素数が「2、3、5」の3つしか存在しないと仮定してみましょう。

すると、数 $Q$ はこうなります。

$Q =$ ( 2 $\times$ 3 $\times$ 5 ) $+$ 1 $=$ 31

さて、ここでできた「31」という数に注目してください。

この31を、もともとの素数リストにある2、3、5のどれかで割ってみましょう。

31 $\div$ 2 $=$ 15 余り 1

31 $\div$ 3 $=$ 10 余り 1

31 $\div$ 5 $=$ 6 余り 1

なんと、どれで割っても「1」余ってしまいます。割り切れませんね。

これは何を意味するのでしょうか。

もし $Q$ がリストにある素数で割り切れないなら、 $Q$ 自体が新しい素数であるか、あるいはリストに含まれていない別の素数でできていることになります。

しかし、私たちは最初に「素数はこれですべて（有限である）」と仮定しました。それなのに、リストにない新しい素数が出てきてしまいました。

これは矛盾ですよね！

つまり、「素数が有限個しかない」という最初の仮定が間違っていたことになります。

結論として、素数は有限ではなく、無限に存在することが証明されました。

素数が無限にあることのメリットとデメリット

エンジニアの視点から見ると、素数が無限にあるという事実は、現代のIT社会において非常に重要な意味を持っています。メリットとデメリットという観点で整理してみましょう。

メリット：セキュリティの強度を保てる

最大のメリットは、暗号技術（特にRSA暗号）の安全性が担保されることです。

インターネット上の通信は、巨大な素数同士を掛け合わせる計算に基づいた暗号で守られています。もし素数が有限個しかなかったら、いつかはすべてのパターンが解読されてしまい、パスワードやクレジットカード情報が筒抜けになってしまうでしょう。

素数が無限にあるからこそ、私たちはより大きく、より複雑な素数を使って、解読困難な暗号を作り続けることができるのです。

デメリット：計算コストの増大

一方で、素数が無限にあるがゆえの難点もあります。それは、巨大な素数を見つけるために膨大な計算リソースが必要になることです。

数が大きくなればなるほど、その数が素数かどうかを判定する処理は重くなります。暗号化や復号の処理に時間がかかるようになると、システムのパフォーマンスに影響を与える可能性があります。

無限に広がる数の海から、実用的な素数を見つけ出す作業は、まるで砂漠で特定の砂粒を探すような途方もない作業なのです。

まとめ

いかがでしたか。

今回は、素数が無限に続く理由を、背理法を使って解説しました。

素数が有限だと仮定する。
すべての素数を掛けて1を足した数を作る。
その数はどの素数でも割り切れない。
新しい素数が必要になり、矛盾する。

このロジックの流れは、プログラミングにおけるデバッグや、アルゴリズムを考える際の論理的思考と非常に似ています。「もしこうだと仮定したら、どこでエラーが出るか？」という考え方は、エンジニアにとって必須のスキルです。

今後は、この素数が実際にどのように暗号技術に使われているのか、「RSA暗号」の仕組みについて学習を進めてみてください。数学とプログラムが密接に関わっていることに、きっと感動するはずですよ！

セイ・コンサルティング・グループの新人エンジニア研修のメニューへのリンク

投稿者プロフィール

山崎講師代表取締役

セイ・コンサルティング・グループ株式会社代表取締役。
岐阜県出身。
2000年創業、2004年会社設立。
IT企業向け人材育成研修歴業界歴20年以上。
すべての無駄を省いた費用対効果の高い「筋肉質」な研修を提供します！
この記事に間違い等ありましたらぜひお知らせください。