素数が無限に存在することの証明 (1)

素数とは、1より大きい自然数で、1と自分自身以外に約数を持たないもののこと。具体的には、2, 3, 5, 7, 11, 13, 17, 19, 23, $\ldots$ が素数である。素数が無限に多く存在することはよく知られていて、たくさんの証明がなされている。それらのいくつかについて書いていきたい。まずは最もよく引用される、ユークリッドの証明から。

ユークリッドは「原論」の中で素数が無限に存在することを証明しているのだが、それは以下のような背理法を使ったものとして紹介されることが多い。

証明1
素数が有限の $n$ 個しか存在しないと仮定し、それらを $p_1, p_2, \ldots, p_n$ とする。

$\displaystyle N = p_1 \times p_2 \times \cdots \times p_n + 1$

とおくと、 $N$ は存在するすべての素数 $p_1, p_2, \ldots, p_n$ のいずれでも割り切れない(1余る)から素数である。一方で $N$ はどの素数よりも大きいから合成数である。これは矛盾。

したがって、素数が有限個しか存在しないという仮定が誤りであり、素数は無限に存在する。(証明終)

ところが、実際にはユークリッドは背理法を使っていないようである。「原論」に書かれている方法(→ 英訳)を上記の書き方に合わせて、かつできるだけシンプルに書いてみると以下のようになる。

証明2
任意の $n$ 個の素数をとり、それらを $p_1, p_2, \ldots, p_n$ とおく。さらに

$\displaystyle N = p_1 \times p_2 \times \cdots \times p_n + 1$

とおく。 $N$ は1より大きいので何らかの素数 $p$ で割り切れるが、一方で $p_1, p_2, \ldots, p_n$ のいずれでも割り切れない(1余る)から、 $p$ はそれら以外の素数である。したがって $p_1, p_2, \ldots, p_n$ 以外に素数が存在することになる。

以上より、どんな自然数 $n$ に対しても $n$ 個より多い素数を得ることができるので、素数は無限に存在する。(証明終)
(※ユークリッドは $N$ が素数の場合とそうでない場合に分けているが、特に分ける必要はないと思う)

私は昔、証明1の方を先に知ってその巧みさに感心したのだが、今になって考えてみると、背理法というのは(論理的には正しくても)直接ズバッと証明したという感触に乏しい。だから今は概して背理法を使わない証明の方が好きである。無限に存在することイコール「どんな数に対してもそれより多くをとることができる」なのであるから、それを直接示したい。それに証明2の方が「無限の広がり」を感じられていい。

…ということを考えながらいろいろ検索していたら、「脱背理法教育」を掲げた安部研究室のページ(東京大学)を見つけた。確かに、背理法という手法は教えるにしても、実際の定理の証明はできるだけ背理法を使わないものを教えた方がいいと思う。

安部研究室のページでは、素数が無限に存在することの証明について「素数の無限性」のエントリで触れられている。高校数学で背理法を導入する時の定番である「 $\sqrt{2}$ が無理数であること」の背理法を使わない証明も書いてあって興味深い。