素数の無限性

有限個の素数 $p_1,\dots,p_r$（$r\geq0$）を任意にとり、
$$ N:=p_1p_2\cdots p_r+1 $$
とおく。ただし $r=0$ のときは空の積を $1$ と約束して $N=2$ とする。$N\geq2$ なので、$N$ を割り切る素数 $q$ が存在する。$q=p_i$ となる $i$ があるとすると、$q$ は $N$ と $p_1\cdots p_r$ をともに割り切るので、その差 $N-p_1\cdots p_r=1$ を割り切る。しかし $q\geq2$ なので $q\nmid1$ であり、矛盾する。よって $q$ は $p_1,\dots,p_r$ のどれとも異なる素数である。
素数が有限個しかないと仮定すると、それらすべてを $p_1,\dots,p_r$ として上の議論を適用でき、どれとも異なる素数が得られて矛盾する。よって素数は無限に存在する。

$N=n!+1\geq2$ を割り切る素数 $q$ をとると $q\leq N$ である。$q\leq n$ なら $q$ は $n!$ の因子なので $q\mid n!$ であり、$q\mid N$ と合わせて $q\mid1$ となり矛盾する。よって $q>n$ である。

$q_1,\dots,q_r$（$r\geq1$）を $4$ で割って $3$ 余る有限個の素数とし（$3$ がその一つなので $r\geq1$ にとれる）、
$$ N:=4q_1q_2\cdots q_r-1 $$
とおく。$N\geq11$ は奇数なので、その素因数はすべて奇素数であり、$4$ で割って $1$ か $3$ 余る。$4$ で割って $1$ 余る数どうしの積は $(4a+1)(4b+1)=4(4ab+a+b)+1$ よりまた $4$ で割って $1$ 余るので、$N$ の素因数がすべて $4$ で割って $1$ 余るなら $N$ も $4$ で割って $1$ 余ることになる。ところが $N=4(q_1\cdots q_r-1)+3$ は $4$ で割って $3$ 余るので、$N$ は $4$ で割って $3$ 余る素因数 $q$ をもつ。$q=q_i$ なら $q$ は $4q_1\cdots q_r-N=1$ を割り切って矛盾する。よって $q$ は $q_1,\dots,q_r$ のどれとも異なる。

$m=\lfloor x\rfloor$ とおく。各 $n\geq1$ について、$n\leq t\leq n+1$ で $1/t\leq1/n$ なので $\frac1n\geq\int_n^{n+1}\frac{dt}{t}$ である。$n=1,\dots,m$ について足すと
$$ \sum_{n=1}^{m}\frac1n\geq\int_1^{m+1}\frac{dt}{t}=\log(m+1)>\log x $$
である（$m+1>x$）。

$x$ 以下の素数を $p_1,\dots,p_k$ とする。各 $p_i$ について等比級数の和の公式から $\bigl(1-\frac1{p_i}\bigr)^{-1}=\sum_{e=0}^{\infty}p_i^{-e}$ であり、これは正の項からなる収束級数である。有限個の正項収束級数の積は、各級数から 1 項ずつ選んで掛けたものすべての和に等しい（正項級数なので和の順序を変えてよい）。したがって
$$ \prod_{i=1}^{k}\Bigl(1-\frac1{p_i}\Bigr)^{-1}=\sum_{(e_1,\dots,e_k)}\frac{1}{p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}} $$
である。ここで和は非負整数の組 $(e_1,\dots,e_k)$ すべてにわたる。$1\leq n\leq x$ なる整数 $n$ は、素数の積に分解でき（素数 の記事の定理「算術の基本定理」の存在の部分）、その素因数は $n\leq x$ 以下なので $p_1,\dots,p_k$ のいずれかである。よって $n=p_1^{e_1}\cdots p_k^{e_k}$ となる組があり、$1/n$ は右辺の項として現れる。相異なる $n$ には相異なる組が対応する（組から積 $n$ が決まるので）。右辺の項はすべて正なので、右辺は $\sum_{n\leq x}1/n$ 以上である。後半の不等号は lem-infinitude-of-primes-harmonic である。

$0< t\leq\frac12$ について
$$ -\log(1-t)=t+\frac{t^2}{2}+\frac{t^3}{3}+\cdots\leq t+\frac{t^2}{2}\bigl(1+t+t^2+\cdots\bigr)=t+\frac{t^2}{2(1-t)}\leq t+t^2 $$
である。prop-infinitude-of-primes-euler-product の両辺の対数をとり、各素数 $p$ に $t=1/p\leq\frac12$ として適用すると
$$ \log\log x<\sum_{p\leq x}-\log\Bigl(1-\frac1p\Bigr)\leq\sum_{p\leq x}\frac1p+\sum_{p\leq x}\frac1{p^2} $$
である。最後の和は
$$ \sum_{p\leq x}\frac1{p^2}\leq\sum_{n=2}^{\infty}\frac1{n^2}<\sum_{n=2}^{\infty}\frac1{n(n-1)}=\sum_{n=2}^{\infty}\Bigl(\frac1{n-1}-\frac1n\Bigr)=1 $$
で押さえられるので、$\sum_{p\leq x}1/p>\log\log x-1$ を得る。$\log\log x\to\infty$（$x\to\infty$）なので和は発散する。素数が有限個なら和は有限個の項の和で有界だから、素数は無限に存在する。

1：空集合は条件を自明に満たし、$\mathbb{Z}$ は $b=1$ で満たす。開集合の族の和集合 $\bigcup_\lambda U_\lambda$ の点 $a$ はある $U_\lambda$ に属するので、$S(a,b)\subset U_\lambda\subset\bigcup_\lambda U_\lambda$ となる $b$ がある。2 つの開集合 $U,V$ の共通部分の点 $a$ について、$S(a,b)\subset U$、$S(a,b')\subset V$ となる $b,b'$ をとると、$S(a,bb')$ は $S(a,b)$ と $S(a,b')$ の両方に含まれるので $S(a,bb')\subset U\cap V$ である。有限個の共通部分も帰納的に開である。
2：空でない開集合 $U$ は点 $a$ とともに無限集合 $S(a,b)$ を含む。
3：$c\in S(a,b)$ なら $S(c,b)=S(a,b)$ なので $S(a,b)$ は開である。また $\mathbb{Z}\setminus S(a,b)=\bigcup_{i=1}^{b-1}S(a+i,b)$ は開集合の和集合なので開であり、$S(a,b)$ は閉集合である。

$-1,1$ 以外の整数 $m$ は、ある素数 $p$ で割り切れる（$m=0$ はすべての素数で、$|m|\geq2$ は $|m|$ の素因数で割り切れる）。したがって
$$ \mathbb{Z}\setminus\{-1,1\}=\bigcup_{p\text{ は素数}}S(0,p) $$
である。素数が有限個しかないと仮定すると、右辺は有限個の閉集合の和集合なので閉集合であり（prop-infinitude-of-primes-furstenberg-topology の 3）、その補集合 $\{-1,1\}$ は開集合になる。しかし $\{-1,1\}$ は空でない有限集合であり、prop-infinitude-of-primes-furstenberg-topology の 2 に反する。よって素数は無限に存在する。

$n=1$ では $p_1=2=2^{2^0}$ である。$n\geq1$ とし、$k\leq n$ で $p_k\leq2^{2^{k-1}}$ が成り立つとする。prf-infinitude-of-primes を $p_1,\dots,p_n$ に適用すると、$N=p_1\cdots p_n+1$ の素因数で $p_1,\dots,p_n$ と異なるものがあり、それは $p_n$ より大きい素数なので $p_{n+1}$ 以上である。よって
$$ p_{n+1}\leq N\leq2^{2^0}\cdot2^{2^1}\cdots2^{2^{n-1}}+1=2^{2^n-1}+1\leq2^{2^n} $$
である（$2^0+2^1+\cdots+2^{n-1}=2^n-1$）。
後半：$x\geq2$ に対し $2^{2^{n-1}}\leq x<2^{2^n}$ となる整数 $n\geq1$ をとる。前半により $p_1,\dots,p_n\leq2^{2^{n-1}}\leq x$ なので $\pi(x)\geq n$ である。一方 $x<2^{2^n}$ から $\log_2\log_2x< n$ であり、$\pi(x)>\log_2\log_2x$ を得る。