ユークリッドの定理

ユークリッドの定理は、素数が無限に存在することを主張する数論における基本的な命題です。この定理は、ユークリッドの著書『原論』で初めて証明されました。この定理にはいくつかの証明があります。

ユークリッドは著書『原論』（第9巻、命題20）^[1]に掲載された証明を提示しており、ここではそれを要約する。^[2]

素数の有限リストp ₁、  p ₂、...、  p _nを考えてみましょう。このリストに含まれていない素数が少なくとも 1 つ追加で存在することがわかります。リスト内のすべての素数の積をPとします: P  =  p ₁ p ₂ ... p _n。q  =  P  + 1とします。qは素数かそうでないかのどちらかです:

• qが素数である場合、リストに含まれていない素数が少なくとももう 1 つ、つまりq自体が存在します。
• qが素数でない場合は、何らかの素因数 p がq を割り切れます 。この因数p がリスト内にあれば、P を割り切れます( P はリスト内の各数の積であるため)。しかし、先ほど述べたように、 p はP  + 1 =  qも割り切れます。 p がPとq を割り切れる場合、p は2 つの数の差^{[3]も割り切れなければなりません。差は (} P  + 1) −  Pまたは 1 です。 1 を割り切れる素数はないため、p はリスト内にあり得ません。これは、リスト内の素数以外に少なくとももう 1 つ素数が存在することを意味します。

これは、素数の有限リストごとに、リストに含まれない素数が存在することを証明しています。^[4]元の著作では、ユークリッドは任意の素数リストを書く方法がなかったため、頻繁に適用した方法、つまり一般化可能な例の方法を使用しました。つまり、彼は3つの素数だけを選択し、上記の一般的な方法を使用して、常に追加の素数を見つけることができることを証明します。ユークリッドは、最初にいくつの素数が選択されたかに関係なく、同様の証明が機能することを読者が確信していると想定していると思われます。^[5]

ユークリッドは、最初に検討した有限集合にはすべての素数が含まれているという仮定から始まる背理法によってこの結果を証明したと誤って報告されることが多いが^[6]、実際には事例による証明、つまり直接的な証明方法である。哲学者トルケル・フランツェンは、論理学の本の中で、「素数が無限に存在するというユークリッドの証明は間接的な証明ではない [...] この議論は、時々「q ₁、... q _{n が}すべて素数であると仮定する」という仮定に置き換えることで間接的な証明として定式化される。しかし、この仮定は証明で使用されていないため、再定式化は無意味である」と述べている^{[7] 。}

ユークリッドの証明には、次のようないくつかのバリエーションが存在します。

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

スイスの数学者レオンハルト・オイラーによるもう一つの証明は、算術の基本定理、すなわちすべての整数は一意に素因数分解できるという定理に基づいています。オイラーが書いたもの（現代の表記法ではなく、現代の標準とは異なり、和と積の引数を整数の有限集合に制限していません）は、次の命題と同等です^。[9]

$${\displaystyle \prod _{p\in P_{k}}{\frac {1}{1-{\frac {1}{p}}}}=\sum _{n\in N_{k}}{\frac {1}{n}},}$$

ここで、はk個の最初の素数の集合を表し、は素因数が全て${\displaystyle P_{k}}$${\displaystyle N_{k}}$${\displaystyle P_{k}.}$

これを示すには、積の各因子を等比級数として展開し、積を和に分配します（これは、リーマンゼータ関数のオイラー積公式の特殊なケースです）。

$${\displaystyle {\begin{aligned}\prod _{p\in P_{k}}{\frac {1}{1-{\frac {1}{p}}}}&=\prod _{p\in P_{k}}\sum _{i\geq 0}{\frac {1}{p^{i}}}\\&=\left(\sum _{i\geq 0}{\frac {1}{2^{i}}}\right)\cdot \left(\sum _{i\geq 0}{\frac {1}{3^{i}}}\right)\cdot \left(\sum _{i\geq 0}{\frac {1}{5^{i}}}\right)\cdot \left(\sum _{i\geq 0}{\frac {1}{7^{i}}}\right)\cdots \\&=\sum _{\ell ,m,n,p,\ldots \geq 0}{\frac {1}{2^{\ell }3^{m}5^{n}7^{p}\cdots }}\\&=\sum _{n\in N_{k}}{\frac {1}{n}}.\end{aligned}}}$$

最後から2番目の和では、素数の積はどれも1回だけ現れるので、算術の基本定理により最後の等式は真である。この結果に対する最初の系で、オイラーは「絶対無限大」に似た記号で を表し、文中の無限和は「値」 に等しく 、したがって無限積もそれに等しいと書いている（現代の用語では、これは調和級数のまでの部分和が のように漸近的に発散すると言うことと同等である）。次に、2番目の系で、オイラーは積が ${\displaystyle \infty}$${\displaystyle \log \infty}$${\displaystyle x}$${\displaystyle \log x}$

$${\displaystyle \prod _{n\geq 2}{\frac {1}{1-{\frac {1}{n^{2}}}}}}$$

は有限値2に収束し、その結果素数のほうが平方数より多くなります。これはユークリッドの定理を証明しています。^[10]

同じ論文（定理19）で、オイラーは実際に上記の等式を使って、それまで知られていなかったより強力な定理、すなわち級数

$${\displaystyle \sum _{p\in P}{\frac {1}{p}}}$$

は発散します。ここで、P はすべての素数の集合を表します (オイラーは、無限和は に等しいと書いています。これは、現代の用語で、この級数の までの部分和が のように漸近的に振る舞うと言うことと同等です)。 ${\displaystyle \log \log \infty }$${\displaystyle x}$${\displaystyle \log \log x}$

ポール・エルデシュは算術の基本定理に基づいた証明^{[11]を示した。すべての正の整数は、}平方数rと平方数 s2に一意に因数分解できる。例えば、75,600 = 2 ⁴ 3 ³ 5 ^{2 7} 1 = 21 ^⋅ 60 ²である。

N を正の整数とし、 k をN以下の素数の個数とする。これらの素数をp ₁ , ... , p _kとする。N以下の任意の正の整数a は、次の形式で表すことができる 。

$${\displaystyle a=\left(p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}\right)s^{2},}$$

ここで、各e _{i は}0または1です。aの平方自由部分を形成する方法は2 ^k通りあります。また、s ^{2 は}最大でNなので、s ≤ √ Nです。したがって、最大で2 ^k √ Nの数がこの形式で表されます。言い換えると、

$${\displaystyle N\leq 2^{k}{\sqrt {N}}.}$$

または、整理すると、N以下の素数の個数kは、以上である。1/2⁠ log ₂ N。Nは任意なので、 N を適切に選択することでk を必要なだけ大きくすることができます。

1950年代にヒレル・ファーステンベルグは点集合位相を用いた背理法による証明を導入した。^[12]

整数 上の位相を等間隔整数位相と呼び、部分集合が空集合、、または等差数列の和集合( の場合)である場合に限り、部分集合を開集合であると宣言することによって定義する。ここで、 ${\textstyle \mathbb {Z} }$${\textstyle U\subseteq \mathbb {Z} }$ ${\textstyle \emptyset }$${\textstyle S(a,b)}$${\textstyle a\neq 0}$

$${\displaystyle S(a,b)=\{an+b\mid n\in \mathbb {Z} \}=a\mathbb {Z} +b.}$$

すると、整数の有限集合は開集合にはなり得ないという性質と、基底集合が開集合かつ閉集合であるという性質から矛盾が生じる。 ${\textstyle S(a,b)}$

$${\displaystyle \mathbb {Z} \setminus \{-1,+1\}=\bigcup _{p\mathrm {\,prime} }S(p,0)}$$

補集合が有限であるため閉じることはできませんが、閉集合の有限和であるため閉じています。

フアン・パブロ・ピナスコは次のような証明を書いている。^[13]

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)の式は に等しく 、(2)の式は1に等しくなりますが、明らかに(3)の式は1に等しくありません。したがって、   p ₁、...、  p _Nよりも多くの素数が存在する必要があります。 ${\displaystyle \lfloor x\rfloor }$

2010年に、ジュンホ・ピーター・ワンは背理法による次の証明を発表しました。^[14] 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について分子が分母以上であるという事実と矛盾します。

フィリップ・サイダックは、背理法^[15]やユークリッドの補題（素数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と有限サイズの素数リストを合わせると、数を再構成するのに十分である。すべてのiに対して となるので、すべてのiに対してとなる（ここで は底 2 の対数を表す）。これにより、次のサイズのnのエンコードが得られる（ビッグオー記法を使用）：ビット。これは、ビットを要するバイナリでn を直接表すよりもはるかに効率的なエンコードである。ロスレスデータ圧縮の確立された結果によれば、一般にNビットの情報をNビット未満に圧縮することはできない。上記の表現は、nが十分に大きい場合 となるため、これに完全に違反する。したがって、素数の数は有限であってはならない。^[16]${\displaystyle p_{i}\geq 2}$${\displaystyle e_{i}\leq \lg n}$${\displaystyle \lg }$${\displaystyle O({\text{prime list size}}+k\lg \lg n)=O(\lg \lg n)}$${\displaystyle N=O(\lg n)}$${\displaystyle \lg \lg n=o(\lg n)}$

ロメオ・メシュトロヴィッチは偶奇論を用いて、素数の数が無限でなければ3が最大の素数であるという矛盾を示した。^[17]

がすべて素数であると仮定します。仮定により、 と互いに素であるすべての正の整数は集合 に含まれることに留意してください。特に、は と互いに素であり、したがって も同様です。しかし、これは が集合 内の奇数であることを意味するため、、または になります。これはが最大の素数でなければならないこと を意味し、これは矛盾です。${\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}$

上記の証明は、 を任意の素数で置き換えて とした場合にも有効であり、積は となり、偶数対奇数の議論は、 で割り切れる対 で割り切れない議論に置き換えられます。結果として生じる矛盾は、 が と同時に に等しく、 より大きい必要があることですが、^[a]は不可能です。 ${\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}$

このセクションの定理は、ユークリッドの定理と他の結果を同時に意味します。

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

π ( x ) を、任意の実数 x に対して 、 x以下の素数の個数を与える素数計算関数とします。素数定理によれば、x / log x はπ ( x )の良い近似値であり、 xが無制限に増加するときの2つの関数π ( 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 .}$

数論において、ベルトランの公理は、任意の整数 に対して、少なくとも1つの素数が必ず存在し、 ${\displaystyle n>1}$

$${\displaystyle n<p<2n.}$$

ベルトラン・チェビシェフの定理は、 との関係としても表すことができます。ここで、は素数計算関数です（ 未満の素数の個数）。 ${\displaystyle \pi (x)}$${\displaystyle \pi (x)}$${\displaystyle x\,}$

$${\displaystyle \forall x\geq 2.\pi (x)-\pi ({\tfrac {x}{2}})\geq 1}$$

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

• Weisstein, Eric W.「ユークリッドの定理」。MathWorld。
• ユークリッドの『原論』第 9 巻、命題 20 (ユークリッドの証明、クラーク大学のデイビッド ジョイスの Web サイトに掲載)