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

今回は素数が無限に存在することの証明についてまとめていきます。これまでに証明した命題が登場しますが、その部分はすでに証明済みなので、省略していきます。

素数が無限にある

これまでの記事に書いた命題をまとめておきます。今回の本題となる命題を証明する際に使うものを主に書いています。(証明では、表立って使われていないが、使う命題の証明をするのに使うものも含めて書いています)

ここから、本題となる素数が無限に存在することの証明をする準備をしていきます。

証明

仮定より、$m = na$となる$a \in \mathbb{Z}$が存在する。

もし、$n \mid m+1$なら、$m+1 = nb$となる$b \in \mathbb{Z}$が存在する。

$nb - na = (m+1) - m = 1 \Leftrightarrow 1 = n(b - a)$

系1より、1の約数は$\pm1$なので、$n$の約数は$\pm1$となり、$n \ne \pm1$であることに矛盾する。

したがって、$n \nmid m+1$

これより、$m,m+1$が互いに素であることも分かる。□
(なぜなら、もし$m,m+1$が互いに素でないとすると共通因数を持つことになり、これはここまでの議論の中で矛盾が生じてしまっているため)

証明

もし、素数が有限個しかなかったとする。
つまり、すべての素数が$p_1,\cdots,p_N$で表せたとする。

$q = p_1\cdots p_N + 1$とおくと、命題3より$q$は素数を約数に持つ。その一つを$p$とする。

もし、$p = p_i$となる$(1\leqq i \leqq N)$があれば、

$$ p \mid p_1\cdots p_N$$

である。

命題4より、$p_1\cdots p_N \hspace{2mm},\hspace{2mm} p_1\cdots p_N + 1$は互いに素であるので矛盾する。

これより、$p \ne p_i$.

しかし、$p$は素数だが、$p_1,\cdots,p_N$のいずれでもないということは、すべての素数が$ p_1,\cdots,p_N$で表せるということに矛盾する。

したがって、素数は無限にある。□

今回やりたかったことはここまでなのですが、残り二つ命題として扱いたいものがあるので、それを紹介したいと思います。命題としては自明のようなものなのですが、自分が本を読んでいたときに少し引っかかってしまった部分があったので、まとめておきたいと思いました。

証明

$d = gcd(a,b) \hspace{2mm},\hspace{2mm}l = lcm(a,b) $とおく。

$d = gcd(a,b)$より、$d \mid a \hspace{2mm},\hspace{2mm} d \mid b$である。
したがって、$\dfrac{a}{d} , \dfrac{b}{d} \in \mathbb{Z}$.

すると、$\dfrac{ab}{d} = a\dfrac{b}{d} = b\dfrac{a}{d}$となり、$\dfrac{ab}{d}$は$a,b$の公倍数であることが分かる。

$a,b$の最小公倍数は$l$であるので、$ \dfrac{ab}{d} \geqq l \Leftrightarrow ab \geqq dl$.

続いて、$ l = lcm(a,b)$より、$a \mid l \hspace{2mm},\hspace{2mm}b \mid l$である。
したがって、$\dfrac{l}{a} , \dfrac{l}{b} \in \mathbb{Z}$.

すると、$\dfrac{ab}{l} = \dfrac{a}{l/b} = \dfrac{b}{l/a}$となる。
$\dfrac{l}{b} , \dfrac{l}{a}$はそれぞれ次のように表すこともできる。

$$ \dfrac{l}{b} = \dfrac{a}{ab/l} \hspace{2mm},\hspace{2mm} \dfrac{l}{a} = \dfrac{b}{ab/l}$$

これより、$\dfrac{l}{b}$は$a$の約数で、$\dfrac{l}{a}$は$b$の約数である。

よって、$\dfrac{ab}{l}$は$a,b$の公約数である。$a,b$の最大公約数は$d$であるので、

$\dfrac{ab}{l} \leqq d \Leftrightarrow ab \leqq dl$.

以上より、$ab = dl \Leftrightarrow gcd(a,b)lcm(a,b) = ab$□

これは命題6に$gcd(a,b) = 1$を代入すればよい。

今回は以上です。