ユークリッドの定理

ユークリッドの証明にはいくつかのバリエーションが存在し、以下のようなものがある。

正の整数 n の階乗n !は、2 からnまでのすべての整数の積であるため、それらの整数で割り切れます。したがって、n ! + 1は、2 からnまでのどの整数でも割り切れません (それぞれの整数で割ると余りが 1 になります)。したがって、n ! + 1は素数であるか、 nより大きい素数で割り切れるかのどちらかです。いずれの場合も、すべての正の整数nに対して、 nより大きい素数が少なくとも 1 つ存在します。結論として、素数の数は無限です。^{[ 9 ]}  

フアン・パブロ・ピナスコは次のような証明を書いた。^{[ 14 ]}

p ₁ ,  ..., p _{N を}最小のN個の素数とする。このとき、包含排除原理により、 x以下の正の整数のうち、これらの素数のいずれかで割り切れる数は、 

$${\displaystyle {\begin{aligned}1+\sum _{i}\left\lfloor {\frac {x}{p_{i}}}\right\rfloor -\sum _{i<j}\left\lfloor {\frac {x}{p_{i}p_{j}}}\right\rfloor &+\sum _{i<j<k}\left\lfloor {\frac {x}{p_{i}p_{j}p_{k}}}\right\rfloor -\cdots \\&\cdots \pm (-1)^{N+1}\left\lfloor {\frac {x}{p_{1}\cdots p_{N}}}\right\rfloor .\qquad (1)\end{aligned}}}$$

xで割ってx  →  ∞にすると

$$\displaystyle \sum _{i}{\frac {1}{p_{i}}}-\sum _{i<j}{\frac {1}{p_{i}p_{j}}}+\sum _{i<j<k}{\frac {1}{p_{i}p_{j}p_{k}}}-\cdots \pm (-1)^{N+1}{\frac {1}{p_{1}\cdots p_{N}}}.\qquad (2)}$$

これは次のように書くことができます

$${\displaystyle 1-\prod _{i=1}^{N}\left(1-{\frac {1}{p_{i}}}\right).\qquad (3)}$$

p ₁ ,  ..., p _N以外の素数が存在しない場合、(1) の式は以下と等しくなります。  ${\displaystyle \lfloor x\rfloor }$(2)の式は 1に等しいが、明らかに(3)の式は1に等しくない。したがって、p ₁ , ..., p _Nよりも多くの素数が存在する必要がある。   

2010年、ジュンホ・ピーター・ワングは背理法による以下の証明を発表した。^{[ 15 ]} kを任意の正の整数とする。すると、ルジャンドルの公式（時にはド・ポリニャックに帰せられる） に よれば、$${\displaystyle k!=\prod _{p{\text{ prime}}}p^{f(p,k)}}$$ どこ $${\displaystyle f(p,k)=\left\lfloor {\frac {k}{p}}\right\rfloor +\left\lfloor {\frac {k}{p^{2}}}\right\rfloor +\cdots .}$$$${\displaystyle f(p,k)<{\frac {k}{p}}+{\frac {k}{p^{2}}}+\cdots ={\frac {k}{p-1}}\leq k.}$$

しかし、素数が有限個しか存在しない場合、 $${\displaystyle \lim _{k\to \infty }{\frac {\left(\prod _{p}p\right)^{k}}{k!}}=0,}$$ （分数の分子は単指数関数的に増加するが、スターリングの近似によれば分母は単指数関数よりも速く増加する）ため、各kに対して分子が分母以上であるという事実と矛盾する。

フィリップ・サイダックは、背理法^{[ 16 ]}やユークリッドの補題（素数pがabを割り切るならば、 aまたはbを割り切る）を用いない構成による以下の証明を与えた。 

1より大きい自然数には少なくとも1つの素因数があり、連続する2つの数nと( n  +  1)には共通の素因数がないため、積n ( n  + 1)は数n 自体よりも多くの異なる素因数を持つ。したがって、プロニック数の連鎖1×2=2{2}、2×3=6{2,3}、6×7=42{2,3,7}、42×43=1806{2,3,7,43}、1806×1807=3263442{2,3,7,43,13,139}、...は、無限に増加する素数の集合の列を提供する。        

素数がk個 ( p ₁ , ..., p _k )しかないと仮定します。算術の基本定理により、任意の正の整数n は次のように表すことができます。 $${\displaystyle n={p_{1}}^{e_{1}}{p_{2}}^{e_{2}}\cdots {p_{k}}^{e_{k}},}$$ ここで、非負の整数指数e _iと有限サイズの素数のリストがあれば、数を再構成するのに十分です。${\displaystyle p_{i}\geq 2}$すべてのiに対して、次のことが成り立つ。${\displaystyle e_{i}\leq \lg n}$すべてのiに対して(${\displaystyle \lg }$は底が2の対数を表します。これにより、 nのエンコーディングは次のサイズになります (ビッグオー記法を使用)。 $${\displaystyle O({\text{prime list size}}+k\lg \lg n)=O(\lg \lg n)}$$ビット。これは、 n を直接バイナリで表現するよりもはるかに効率的なエンコーディングです。${\displaystyle N=O(\lg n)}$ビット。ロスレスデータ圧縮における確立された結果によれば、一般的にNビットの情報をNビット未満に圧縮することはできません。上記の表現は、 nが十分に大きい場合、この原則に大きく違反します。なぜなら、${\displaystyle \lg \lg n=o(\lg n)}$したがって、素数の数は有限であってはならない。 ^{[ 17 ]}

ロメオ・メシュトロヴィッチは偶奇の議論を用いて、素数の数が無限でない場合、3が最大の素数となり、矛盾が生じることを示した。^{[ 18 ]}

仮に${\displaystyle p_{1}=2<p_{2}=3<p_{3}<\cdots <p_{k}}$これらはすべて素数です。${\displaystyle P=3p_{3}p_{4}\cdots p_{k}}$また、仮定により、それと互いに素なすべての正の整数は集合に含まれることに注意してください。${\displaystyle S=\{1,2,2^{2},2^{3},\dots \}}$特に、${\displaystyle 2}$比較的${\displaystyle P}$そして、それは${\displaystyle P-2}$しかし、これはつまり${\displaystyle P-2}$セット内の奇数です${\displaystyle S}$⁠、だから⁠${\displaystyle P-2=1}$⁠、または⁠${\displaystyle P=3}$つまり、${\displaystyle 3}$最大の素数でなければならないが、これは矛盾である。

上記の証明は、以下の場合にも引き続き有効です。${\displaystyle 2}$任意の素数に置き換えられる${\displaystyle p_{j}}$と共に​${\displaystyle j\in \{1,2,\dots ,k-1\}}$⁠、製品${\displaystyle P}$になる${\displaystyle p_{1}p_{2}\cdots p_{j-1}\cdot p_{j+1}\cdots p_{k}}$偶数か奇数かの議論は、割り切れるか割り切れないかの議論に置き換えられる。${\displaystyle p_{j}}$議論。結果として生じる矛盾は、${\displaystyle P-p_{j}}$同時に、等しい${\displaystyle 1}$そして、より大きくなる${\displaystyle 1}$⁠、 ^{[ a ]}これは不可能です。

ディリクレの定理は、互いに素な任意の2つの正の整数aとdに対して、 a + ndの形をとる素数が無限に存在することを述べている。ここでnも正の整数である。言い換えれば、 dを法として aと合同な素数は無限に存在する。   

π ( x )を、任意の実数xに対して、x以下の素数の個数を表す素数計数関数とする。素数定理によれば、x / log xはπ ( x )の良い近似値であり、xが無限に増加する ときのπ ( x )とx / log xの商の極限は1 である。 $${\displaystyle \lim _{x\rightarrow \infty }{\frac {\pi (x)}{x/\log(x)}}=1.}$$

漸近記法を用いると、この結果は次のように言い換えることができる。 $${\displaystyle \pi (x)\sim {\frac {x}{\log x}}.}$$

これによりユークリッドの定理が得られる。${\displaystyle \lim _{x\rightarrow \infty }{\frac {x}{\log x}}=\infty .}$

数論において、ベルトランの公準は、任意の整数に対して が成り立つことを述べる定理である。${\displaystyle n>1}$⁠、常に少なくとも１つの素数が存在し、 $${\displaystyle n<p<2n.}$$ 同様に、${\displaystyle \pi (x)}$素数計数関数（1以下の素数の数）${\displaystyle x}$）定理は、${\textstyle \pi (x)-\pi ({\tfrac {x}{2}})\geq 1}$すべての人にとって${\displaystyle x\geq 2}$⁠ .

この主張は、1845年にジョセフ・ベルトラン^{[ 19 ]}（1822-1900）によって初めて予想されました。ベルトラン自身は、区間[2, 3 × 10 ⁶ ]のすべての数についてこの主張を検証しました。彼の予想は、1852年にチェビシェフ（1821-1894）によって 完全に証明され^{[ 20 ]}、そのためこの公準はベルトラン・チェビシェフの定理またはチェビシェフの定理とも呼ばれています。