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

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

この動画で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 は自然数)という積に分解したとする。Np_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 は自然数)という積に分解する。Np_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 + mp_1, p_2, \ldots, p_n のいずれでも割り切れないから、p はそれら以外の素数である。したがって p_1, p_2, \ldots, p_n 以外に素数が存在する。

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

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

はてなブックマーク - 素数が無限に存在することの証明 (3)
[`evernote` not found]

コメントを残す

メールアドレスが公開されることはありません。