素数は無限に存在するのか?それとも有限個なのか?
これは素数を習ったことがある多くの人が思うことではないでしょうか?
結論から言うと素数は無限に存在します!
この素数の無限性の証明は様々な証明方法があります。
その中でも今回は背理法を用いて証明をしていきます。
1.証明
今回は背理法を用いるので今回はまず設定を
「素数を有限個だと仮定する」
という設定からスタートします。
では証明していきましょう!
素数の個数を有限個と設定したので、素数の個数を\(m\)個として
\(p_1, p_2, p_3, …… p_k, ……, p_m\)
になる。ここで\(p_1 = 2, p_2 = 3, p_3 = 5\)とする。
有限和の席を\(Q_m\)と考えると,
\( Q_m = (\displaystyle\frac{1}{2^0} + \displaystyle\frac{1}{2^1} + \displaystyle\frac{1}{2^2} + …… )・(\displaystyle\frac{1}{3^0} + \displaystyle\frac{1}{3^1} + \displaystyle\frac{1}{3^2} + ……) \)
\( …… (\displaystyle\frac{1}{p_{m}^0} +\displaystyle\frac{1}{p_{m}^1} + \displaystyle\frac{1}{p_{m}^2} + ……) \)
\(=\displaystyle \prod_{ k=1 }^m (\frac{1}{p_{k}^0} +\frac{1}{p_{k}^1} + \frac{1}{p_{k}^2} + ……)\)
\(=\displaystyle \prod_{ k=1 }^m \frac{1}{1- \frac{1}{p_k}}\)
これで積の形が求まった。
今度は
\( Q_m = (\displaystyle\frac{1}{2^0} + \displaystyle\frac{1}{2^1} + \displaystyle\frac{1}{2^2} + …… ) \)
\( ・(\displaystyle\frac{1}{3^0} + \displaystyle\frac{1}{3^1} + \displaystyle\frac{1}{3^2} + ……) \)
\( …… (\displaystyle\frac{1}{p_{m}^0} +\displaystyle\frac{1}{p_{m}^1} + \displaystyle\frac{1}{p_{m}^2} + ……) \)
\(=(\displaystyle\frac{1}{2^0 3^0 5^0 … p_{m}^0})\)
\( + (\displaystyle\frac{1}{2^1 3^0 5^0 … p_{m}^0} + …… +\displaystyle\frac{1}{2^0 3^0 5^0 … p_{m}^1} ) + ……\)
\(=\displaystyle \sum_{ n = 0 }^{ ∞ } \displaystyle\sum \frac{1}{2^{r_1} 3^{r_2} 5^{r_3} … p_{m}^{r_m}}\)
これで和の形になった。
ここで、和の括り方は分母の指数に注目して指数の総和が0を第1項に、総和が1を第2項にした。
そしてシグマを取っているところは一般形を持ってくるので、指数の総和がnになるように設定した。
つまり、\(r_1〜r_m\)に関しては総和が\(m\)の範囲で任意の数字を取っている。
したがって、分母に注目してみると
「全ての整数が一度だけ現れる」
ことがわかるので
\(Q_m = \displaystyle\frac{1}{1} + \displaystyle\frac{1}{2} +\displaystyle\frac{1}{3} + \displaystyle\frac{1}{4} + …… \)
これは調和級数と呼ばれる形で
\( Q_m = \displaystyle\sum_{k=1}^{∞} \frac{1}{k} \)
したがって、次の等式が導かれることになる。
\(\displaystyle \prod_{ k=1 }^m \frac{1}{1- \frac{1}{p_k}} =\displaystyle\sum_{k=1}^{∞} \frac{1}{k} \)
左辺は素数が有限個という仮定から<有限の値>を取るが、右辺は調和級数だから<正の無限大に発散>する。
これは題意と矛盾している。
したがって、素数は有限個ではなく無限に存在する。
以上で素数が無限に存在することを証明できました。
2.最後に
今回は背理法と調和級数を用いて素数が無限に存在することを証明しました。
他にも様々な証明方法があるのでぜひぜひ様々な証明方法を考えてみてください!!
このブログは僕が普段学習したことのアウトプット用に使っています。
大学での専攻は物理学、独学でPythonを学習しているためこの2つが主な内容を占めています。
時間がある時に読んでいただけると嬉しいです。
気に入っていただけたらブックマーク、twitter(@tsureblo_nobu)のフォローよろしくお願いします。
twitterではタイムリーな学問に対する思いなどをつぶやいています。
3.参考文献
今回の記事を書くにあたって参考にした本を紹介します。