全脳科学帳

これを好む者はこれを楽しむ者に如かず

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

3つ目の証明として、スティルチェスによるものを。 スティルチェスは19世紀のオランダの数学者で、解析学で業績を残した人。

この動画で3つ目の証明として紹介されている。


素数が無限個あることの意外に知られていない3つの証明

証明は短い。背理法を使う(※動画では変数  n が重複して使われているので、以下ではそこを修正)。

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

 \displaystyle N = p_1 \times p_2 \times \cdots \times p_n

とおき、 N = lm ( l,  m は自然数)という積に分解したとする。 N p_1, p_2, \ldots, p_n を1つずつ因数として持っているから、どの素数  p_i (1 \le i \le n) についても  l,  m のうち一方のみが  p_i で割り切れ、他方は  p_i で割り切れない。 そこで  l + m という数を考えると、この数はどの  p_i でも割り切れない。つまり存在する素数のいずれでも割り切れないから、素数を約数に持たない。よって  l + m = 1 となる。しかし  l \ge 1,  m \ge 1 であるから矛盾。

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

ユークリッドの証明の時と同様に、同じ考え方で背理法を使わずに証明する方法を考えてみた。以下のようになるか。

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

 \displaystyle N = p_1 \times p_2 \times \cdots \times p_n

とおく。  N = lm ( l,  m は自然数)という積に分解する。 N p_1, p_2, \ldots, p_n を1つずつ因数として持っているから、どの素数  p_i (1 \le i \le n) についても  l,  m のうち一方のみが  p_i で割り切れ、他方は  p_i で割り切れない。 そこで  l + m という数を考えると、この数は1より大きいので何らかの素数  p で割り切れるが、一方で上記より  l + m p_1, p_2, \ldots, p_n のいずれでも割り切れないから、 p はそれら以外の素数である。したがって  p_1, p_2, \ldots, p_n 以外に素数が存在する。

以上より、どんな自然数  n に対しても  n 個より多い素数を得ることができるので、素数は無限に存在する。(証明終)

コツが少しわかってきた。「 n 個と仮定すると矛盾」を「 n 個に対して必ず他のものが存在する」に変えればよいのである。やはり背理法を使わない方が気持ちがいい。