素数が無限に多く存在することの証明

0 はじめに

素数が無限に多く存在することは有名である。

ここでは、この事実のいくつかの証明を紹介したい。これらの証明の多くは、良くはないが与えられた数以下の素数の個数に関する評価を与えている。 π(x) を x 以下の素数の個数とする。このとき、多くの証明は π(x) > c log log x とか π(x) > c log x とかいった形の評価を与える。ここで c は正の定数である。

ここに挙げられた証明に関する論文などは MathSciNet で “infinitude of prime∗” で検索することにより見つけることができる。

もちろん、素数が無限に多く存在することの証明は他にもある。

1 ユークリッドの証明

2 = p_{1} < p_{2} < ⋯ < p_{r} をすべての素数と仮定する。 P = p_{1}p_{2} ⋯ p_{r} + 1 とし、 p を P の素因数とする。 p_{1}, p_{2}, …, p_{r} はいずれも P = p_{1}p_{2} ⋯ p_{r} + 1 の素因数ではないから、 p はこれらの素数とは異なる素数である。これは p_{1}, p_{2}, …, p_{r} をすべての素数と仮定したことに矛盾する。

ユークリッドの証明は、素数が無限に多く存在することの証明としては最も有名なものだろう。この証明は非常に単純である。また、この証明を修正することで、素数の分布に関する情報を得ることができる。 R ≥ 2 に対し、 R < p ≤ R^{R} + 1 となる素数が存在する。

2 = p_{1} < p_{2} < ⋯ < p_{r} を R 以下のすべての素数とする。 P = p_{1}p_{2} ⋯ p_{r} + 1 とし、 p を P の素因数とする。 p_{1}, p_{2}, …, p_{r} はいずれも P = p_{1}p_{2} ⋯ p_{r} + 1 の素因数ではないから、 p はこれらの素数とは異なる素数である。明らかに p ≤ R^{r} + 1 ≤ R^{R} + 1 である。 p_{1}, p_{2}, …, p_{r} は R 以下の素数すべてであるから、 p > R である。

ここで、 R^{R} + 1 は R^{R/2+1} + 1 で置き換えられることがわかる。 1 および 2 以外の偶数は素数ではありえないから、 R 以下の素数の個数は R/2+1 個を超えないからである。

もちろん、これは非常に弱い結果である。

ここで注意しなければならないのは、上に出てきた p_{1}p_{2} ⋯ p_{r} + 1 という形の数自体は、必ずしも素数ではないということである。実際、 2 × 3 × 11 × 13 + 1 = 59 × 509 である。 p_{1}p_{2} ⋯ p_{r} + 1 の形の素数が無限に多く存在するか否かは未だに解決されていない問題である。 p_{1}p_{2} ⋯ p_{r} + 1 の形の合成数が無限に多く存在するか否かも知られていない。

ユークリッドの証明には、いくつもの変形がある。

参考

P. Ribenboim, The New Book of Prime Number Records, Springer-Verlag, New York, 1996, p. 3.

L. E. Dickson, History of the Theory of Numbers, Vol. I: Divisibility and Primality, Carnegie Institution of Washington, 1919 (reprint: Dover Publication, New York, 2005), p. 413.

2 クンマーの証明

2 = p_{1} < p_{2} < ⋯ < p_{r} をすべての素数と仮定する。 N = p_{1}p_{2} ⋯ p_{r} > 2 とおく、少なくとも素数は2つ以上はあり、 N は素数すべての積なので N−1 > p_{r} であるから、 N − 1 は素因数 p_{i} を持つ。 p_{i} は N − (N − 1) = 1 を割りきらなければならないが、これは不可能である。

クンマーの証明は、ユークリッドの証明と本質的に同一のものである。ユークリッドが p_{1}p_{2} ⋯ p_{r} + 1 の形の数を用いているのに対し、クンマーは p_{1}p_{2} ⋯ p_{r} − 1 の形の数を用いている。ユークリッドの証明と同様に、クンマーの証明を修正し、任意の R ≥ 2 に対し、 R < p ≤ R^{R/2+1} − 1 となる素数 p が存在することを証明することができる。

参考 P. Ribenboim, 上掲書, p. 4 および L. E. Dickson, 上掲書, p. 413。

3 スティルチェスの証明

素数が p_{1}, p_{2}, …, p_{r} しかないと仮定する。 N = p_{1}p_{2} ⋯ p_{r} とし、 N = mn(m, n ≥ 1) を N の分解の一つとする。各 p_{i} は、 m と n のうちのちょうど片方のみを割り切るから、 p_{i} はいずれも m + n を割りきらない。つまり、 m + n はどのような素数でも割り切れない。しかし m + n > 1 だから、このようなことは不可能である。

参考 P. Ribenboim, 上掲書, p. 4 および L. E. Dickson, 上掲書, p. 414。

4 ゴールドバッハの証明

ゴールドバッハの予想（4 以上のすべての偶数は 2 つの素数の和で表される）で有名なゴールドバッハも素数が無限に多く存在することの証明を残している（ゴールドバッハが証明を書き残している例は他には確認されていない）。

まず、フェルマー数 F_{n} = 2^{2^{n}} + 1(n ≥ 0) は、どの 2 つも互いに素であることを示す。 F_{m} − 2 = 2^{2^{n}} − 1 = (2^{2^{n}−1} + 1)(2^{2^{n}−1} − 1) = F_{0}F_{1} ⋯ F_{m−1} であるから、 F_{m} と F_{n}(m > n) を共に割り切る素数は 2 = F_{m} − (F_{m} − 2) を割りきらなければならないが、 F_{n} は常に奇数だから、そのような素数はありえない。

よって q_{1} を F_{1} を割り切る素数とし、 q_{2} を F_{2} を割り切る素数とし、以下同様にすると、 q_{1}, q_{2}, … は素数の無限列となる。

1730 年にゴールドバッハがオイラーに宛てた手紙の中でフェルマー数を用いた証明を与えたことが記されている。

フェルマー数の最初の 5 つ F_{0} = 3, F_{1} = 5, F_{2} = 17, F_{3} = 257, F_{4} = 65537 はいずれも素数である。しかし、 F_{5} = 4294967297 = 641 は合成数であり、その他のフェルマー数も、合成数であるものは多く知られているが、素数であるものは発見されていない。

参考 P. Ribenboim, 上掲書, p.p. 4–5 および L. E. Dickson, 上掲書, p.

5 ショルンの証明

素数が m 個しか存在しないと仮定し、 n = m + 1 とおく。 n 個の整数 (n!)i + 1(i = 1, 2, …, n) はどの 2 つも互いに素である。というのは、 1 ≤ i < j ≤ n とし j = i+d とおくと ((n!)i+1, (n!)j+1) = ((n!)i+1, (n!)d) = 1 となるからである。各 i = 1, 2, …, n に対し、 p_{i} を (n!)i + 1 を割り切る素数とする。このとき p_{1}, p_{2}, …, p_{n} は相異なる素数である。よって少なくとも n 個の素数が存在することになり、当初の仮定に反する。

ショルンの証明は、任意の整数 n に対し、 (n!)n + 1 以下の素数は少なくとも n 個存在することを示している。

参考 P. Ribenboim, 上掲書, p.p. 5。

6 オイラーの証明

素数が無限に多く存在することの証明の多くは初等的であるのに対し、オイラーの証明はどちらかといえば解析的な考えを用いている。しかし、この方法は、素数の分布に関する大きな発展に結びついている。

p_{1}, p_{2}, …, p_{n} をすべての素数とする。いずれの素数も 1 より大きいから、等比級数 ∑_{k=0}^{∞} 1/p_{i}^{k} は 1/(1 − 1/p_{i}) に収束する。

したがって ∏_{i=1}^{n} 1/(1 − 1/p_{i}) = ∏_{i=1}^{n} ∑_{k=0}^{∞} 1/p_{i}^{k} = ∑_{k_{i}} 1/(∏_{i=1}^{n} p_{i}^{k_{i}}) である。 p_{1}, p_{2}, …, p_{n} がすべての素数であるから、右辺に現れる積 ∏_{i=1}^{n} p_{i}^{k_{i}} は正の整数をいずれも、少なくとも 1 回はとる。よってすべての整数の逆数の和は ∑_{n=1}^{∞} 1/n ≤ ∏_{i=1}^{n} 1/(1 − 1/p_{i}) となって、収束しなければならない。しかし、これは ∑_{n=1}^{∞} 1/n は発散するという有名な事実（これは ∑_{n=1}^{∞} 1/n ≥ 1 + 1/2 + (1/4 + 1/4) + (1/8 + 1/8 + 1/8 + 1/8) + ⋯ により確かめられる）に反する。

実際、素因数分解の一意性から、オイラーは有名な式 ∑_{n=1}^{∞} 1/n^{s} = ∏_{i=1}^{n} 1/(1 − 1/p_{i}^{s}) を導いている。

オイラーの方法の興味深い点は、 ζ 関数 ζ(s) = ∑_{n=1}^{∞} 1/n^{s} と素数のつながりを示唆していることにある。これは解析的整数論の最も重要な基礎の一つである。

さらにオイラーは素数の逆数の和が発散することも示している。

N 以下の整数は、 N 以下の素数の積で表されるから、上と同様にして、 ∑_{n=1}^{N} 1/n ≤ ∏_{p≤N} 1/(1 − 1/p) となることがわかる。

よって log ∏_{p≤N} 1/(1 − 1/p) = − ∑_{p≤N} log(1 − 1/p) となるが、 log(1 − 1/p) = ∑_{m=1}^{∞} 1/(mp^{m}) ≤ ∑_{m=1}^{∞} 1/(p^{m}) = 1/p+1/p(p−1) < 1/p+1/(p−1)^{2} より、 log ∑_{n=1}^{N} 1/n ≤ ∑_{p≤N} 1/p + 1/(p − 1)^{2} ≤ ∑_{p≤N} 1/p + ∑_{n} 1/n^{2} となる。

したがって ∑_{p≤N} 1/p ≥ log ∑_{n=1}^{N} 1/n − c ≥ log log N − C となる定数 c, C が存在する。

参考 P. Ribenboim, 上掲書, p.p. 6–7 および L. E. Dickson, 上掲書, p. 413。

7 エルデシュの証明

p_{1} = 2, p_{2} = 3, …, p_{j} を x 以下のすべての素数とする。 n = n_{1}^{2}m （m は平方因子をもたない）とおく。このとき m = 2^{b_{1}}3^{b_{2}} ⋯ p_{j}^{b_{j}} （b_{i} は 0 または 1）とかける。このような整数は多くても 2^{j} 個しかない。 n_{1}^{2} ≤ n ≤ x だから、各 m に対し、 n_{1} の可能性は多くても x^{1/2} 通りである。よって x ≤ 2^{j}x^{1/2} つまり j ≥ (log x)/(2 log 2) となる。したがって、 x 以下の素数は少なくとも (log x)/(2 log 2) 個存在する。

エルデシュの方法を用いて、素数の逆数の和が発散することを示すこともできる。

素数の逆数の和が収束すると仮定すると、 ∑_{p>M} 1/p < 1/2 となる M が存在する。このとき、任意の整数 N に対し、 ∑_{p>M} N/p < N/2 となる。

N 以下の整数を 2 つの集合に分割する。 N_{1} を N 以下の整数のうち、 M より大きい何らかの素数で割り切れるものの個数とし、 N_{2} をそれ以外の N 以下の整数の個数とする。

このとき、 N_{1} ≤ ∑_{p>M} N/p < N/2 であるが、一方で上と同様に N_{2} < 2^{M}N^{1/2} となる。よって N が十分大きいとき N = N_{1} + N_{2} < N/2 + 2^{M}N^{1/2} < N となり、矛盾が生じる。

実際任意の正の整数 M に対して N = 2^{2M+2} ととれば N_{1} ≤ ∑_{M<p≤N} N/p かつ N_{1} = N − N_{2} ≥ N − 2^{M}N^{1/2} = 2^{2M+1} = N/2 より ∑_{M<p≤2^{2M+2}} 1/p > 1/2 となることがわかる。

参考 G. H. Hardy and E. M. Wright, D. R. Heath-Brown, J. Silverman, A. Wiles, An Introduction to the Theory of Numbers, the 6th edition, Oxford University Press, 2008, Section 2.6.

8 チェビシェフの証明

チェビシェフは階乗の整数論的な性質を用いて、 x > 1 のとき x < p < 2x となる素数が存在するという有名な定理を証明した。エルデシュはこれに簡単な証明を与えている。

チェビシェフの方法は、素数が無限に多く存在することの証明に用いることができる。

a(p, N) を素数 p が階乗 N! を割り切る回数とする。

このとき、どの素数 p ≤ N に対しても、 a(p, N) = ⌊N/p⌋ + ⌊N/p^{2}⌋ + ⋯ < N/(p − 1) となり、 p が N より大きい素数のとき、 a(p, N) = 0 となる。

それで ∑_{p≤N}(log p)/(p − 1) > ∑_{p} a(p, N)(log p)/N = (1/N) log(N!) > (log N) − 1 となるから、 ∑_{p≤N}(log p)/(p − 1) は N とともに正の無限大に発散する。これより、素数は無限に多く存在する。

参考 G. H. Hardy and E. M. Wright, D. R. Heath-Brown, J. Silverman, A. Wiles, An Introduction to the Theory of Numbers, the 6th edition, Oxford University Press, 2008, Section 22.7.

9 シュリニヴァサンの証明

上に述べた通り、どの 2 つも互いに素な整数からなる無限列が存在するならば、素数は無限に多く存在する。 As mentioned above, any infinite sequence of pairwise coprime integers shows the infinite of primes.

数列 x_{i}(i = 0, 1, …) が x_{i} | x_{i+1} かつ gcd(x_{i}, x_{i+1}/x_{i}) = 1 を満足するならば、数列 a_{i} = x_{i+1}/x_{i}(i = 0, 1, …) は、どの 2 つも互いに素な整数からなる。

f(x) = x^{2} + x + 1 とする。このとき f(n^{2}) = n^{4} + n^{2} + 1 = (n^{2} + n + 1)(n^{2} − n + 1) = f(n)f(−n) であるが n^{2} + n + 1 は常に奇数なので gcd(n^{2} + n + 1, n^{2} − n + 1) = gcd(n^{2} + n + 1, 2n) = 1 である。

よって x_{i} = f(2^{2^{m}}) によって定まる数列 x_{m}(m = 0, 1, …) は上記の条件を満たす。

数列 x_{m} = 2^{p^{m}} − 1(m = 0, 1, …) も上記の条件を満たす。 q | x_{m} ならば x_{m+1}/x_{m} = ((x_{m}+1)^{p}−1)/((x_{m}+1)−1) = 1+(x_{m}+1)+⋯+(x_{m}+1)^{p−1} ≡ p (mod q) となる。よって q が x_{m}, x_{m+1}/x_{m} を共に割り切るのは q = p の場合のみである。しかしフェルマーの小定理より x_{m} = (2^{m})^{p} − 1 ≡ 1 (mod p) より p が x_{m} を割り切ることはできない。したがって gcd(x_{m}, x_{m+1}/x_{m}) = 1 である。

2^{p^{m}} − 1 の素因数は p^{m} を法として 1 と合同である。したがって、上のことから p^{m} を法として 1 と合同な素数は無限に多く存在することがわかる。

より一般に、シュリニヴァサンはすべての正の整数 k に対して、 k を法として 1 と合同な素数が無限に多く存在することを示している。これは本質的には k を法として 1 と合同な素数が無限に多く存在することのルーカスによる証明の変形である。

参考 S. Srinivasan, On infinitude of primes, Hardy Ramanujan J. 7 (1984), 21–26.

10 トゥエの証明

n, k を (1+n)^{k} < 2^{n} となる正の整数とし、 p_{1} = 2, p_{2} = 3, …, p_{r} を2^{n} 以下のすべての素数とする。 1 ≤ m ≤ 2^{n} となるすべての整数は m = 2^{e_{1}}3^{e_{2}} ⋯ p_{r}^{e_{r}} の形に書くことができる。 m ≤ 2^{n} なので e_{i} ≤ n である。このような e_{1}, e_{2}, …, e_{r} の選び方は多くても (n + 1)^{r} 通りであるから (1 + n)^{k} < 2^{n} ≤ (1 + n)^{r} つまり r > k である。任意の正の整数 k に対し、 1 + 2k^{2} < 2^{2k} より (1 + 2k^{2})^{k} < 2^{2k^{2}} である。よって任意の正の整数 k に対し、 n = 2k^{2} ととれば n, k は冒頭の条件を満たす。したがって 2^{n} = 4^{k^{2}} より小さい素数の個数は少なくとも k + 1 個ある。

参考 P. Ribenboim, 上掲書, p. 7 および L. E. Dickson, 上掲書, p. 414。

11 ペロットの証明

まず、 ∑_{n=1}^{∞}(1/n^{2}) は 2 より小さな値に収束する。実際、この和は π^{2}/6 に収束することはオイラーの有名な結果である。

∑_{n=1}^{∞}(1/n^{2}) = 1+1/4+∑_{n=3}^{∞}(1/n^{2}) < 5/4+∑_{n=3}^{∞}(1/n(n−1)) = 5/4+∑_{n=3}^{∞}(\frac{1}{n − 1}−\frac{1}{n}) = 5/4+1/2 = 7/4.

より、 ∑_{n=1}^{∞}(1/n^{2}) < 7/4 となることはすぐにわかる。 δ = 2 − ∑_{n=1}^{∞}(1/n^{2}) とおくと、上の評価より δ > 1/4 となる。

さて X を任意の正の実数とし p_{1}, p_{2}, …, p_{r} を X 以下のすべての素数とする。 X 以下の整数 m で、平方数で割り切れないものの個数は多くても 2^{r} である。 X 以下の整数 m で、 d^{2} で割り切れるものの個数は多くても X/d^{2} であるから、 X 以下の整数 m で、何らかの平方数で割り切れるものの個数は多くても ∑_{d=2}^{∞}(X/d^{2}) = X(∑_{d=1}^{∞}(X/d^{2}) − 1) = X(1 − δ) である。よって X ≤ 2^{r} + X(1 − δ) つまり 2^{r} ≥ δX ≥ N/4 である。したがって r > (log X/ log 2) − 2 となる。

ペロットの証明は X 以下の整数のうち各平方数 d^{2} で割り切れないものを取り除くことにより X 以下の、平方数で割り切れない整数の個数を数えている。この議論は本質的には、ある条件を満たす整数の個数を評価するために発展した篩の理論の基本的な考えである。

参考 P. Ribenboim, 上掲書, p. 8 および L. E. Dickson, 上掲書, p. 413。

12 オーリックの証明

p_{1} < p_{2} < ⋯ < p_{r} がすべての素数であると仮定する。 t を任意の正の整数とし N = p_{r}^{t} とおく。

任意の N 以下の正の整数 m は r 個の非負の整数 (f_{1}, f_{2}, …, f_{r}) により m = p_{1}^{f_{1}}p_{2}^{f_{2}} ⋯ p_{r}^{f_{r}} の形に書くことができる。 E = (log p_{r})/(log p_{1}) とおく。 p_{1}^{f_{i}} ≤ p_{i}^{f_{i}} ≤ m ≤ N = p_{r}^{t} よりすべての i に対して f_{i} ≤ tE である。よって N は 1 ≤ f_{i} ≤ tE となる r 個の整数の組 (f_{1}, f_{2}, …, f_{r}) の選び方の個数を超えないので p_{r}^{t} = N ≤ (tE + 1)^{r} ≤ t^{r}(E + 1)^{r} である。これは t が大きいときには成り立たない。

参考 P. Ribenboim, 上掲書, p. 9 および L. E. Dickson, 上掲書, p. 414。

13 Boije af Gennäs の証明

X を任意の正の実数とし、 2, 3, …, p_{n} を X 以下のすべての素数とする。 e_{i}(i = 1, 2, …, n) を任意の正の整数とし P = 2^{e_{1}}3^{e_{2}} ⋯ p_{n}^{e_{n}} とおく。 δ と P/δ が互いに素で、かつ Q = P/δ − δ > 1 となるような δ をとる。 Q は X 以下の素数では割り切れないから Q は X より大きな素数の積である。特に X より大きな素数が存在する。

参考 L. E. Dickson, 上掲書, p. 414。

14 バーネスの証明

1976 年にバーネスは連分数とペル方程式の理論を用いた、新しい素数の無限性の証明を発表した。

p_{1} = 2, p_{2} = 3, …, p_{t} がすべての素数であると仮定し、 P = ∏_{i=1}^{t} p_{i}, Q = ∏_{i=2}^{t} p_{i} とおく。

このとき x = (P + \sqrt{P^{2} + 4})/2 = Q + \sqrt{Q^{2} + 1} は連分数 x = [p, p, …] により表される。

このとき Q^{2} + 1 は p_{1} = 2 以外の素数で割り切れないので 2 の累乗でなければならない。 Q^{2} + 1 は平方数でもありえないので Q^{2} + 1 = 2^{2l+1} つまり Q^{2} − 2(2^{l})^{2} = −1 でなければならない。よって Q/2^{l} は\sqrt{2} の連分数展開 [1, 2, 2, …] の偶数番目の近似分数なければならない。 [1, 2, 2, …] の m 番目の近似分数を B_{m} とおく。それで B_{0} = 1, B_{1} = 2, B_{m+1} = 2B_{m} + B_{m−1} となり m が偶数のとき、常に B_{m} は奇数でなければならない。したがって Q も奇数でなければならず、よって l = 0 つまり Q = 1 でなければならない。これは矛盾である。

もちろん、 Q^{2} + 1 > 2 であり Q^{2} + 1 は 4 では決して割り切れないから Q^{2} + 1 は 2 の累乗ではありえない。

参考 C. W. Barnes, The infinitude of primes; a proof using continued fractions, L’Enseignement Math. (2) 22 (1976), 313–316.

15 ブラウンの証明

t 個の素数 p_{1}, p_{2}, …, p_{t} しか存在しないと仮定し m/n = ∑_{i=1}^{t} 1/p_{i} とおく。さて 1/2 + 1/3 + 1/5 > 1 であるから m/n > 1 である。よって m > n ≥ 1 である。したがって m は素因数 p_{i} を持たなければならないが、このとき p_{i} | p_{1}p_{2} ⋯ p_{i−1}p_{i+1} ⋯ p_{t} となり、これは不可能である。

参考 L. E. Dickson, 上掲書, p. 414。

16 ハリスの証明

A_{0}, A_{1}, A_{2} を、どの 2 つも互いに素な正の整数とし n ≥ 3 に対して A_{n} = A_{0}A_{1} ⋯ A_{n−3}A_{n−1} + A_{n−2} とする。

このとき A_{0}, A_{1}, …, A_{n} はどの 2 つも互いに素であることが次のようにしてわかる。 p | gcd(A_{n}, A_{n−2}) のとき p | A_{n} − A_{n−2} = A_{0}A_{1} ⋯ A_{n−3}A_{n−1} より、ある i ≥ 1, i ≠ 2 に対し p | gcd(A_{n−i}, A_{n−2}) となる。同様に p | gcd(A_{n}, A_{n−j}) for some j ≥ 1, j ≠ 2 のとき p | A_{n} − A_{0}A_{1} ⋯ A_{n−3}A_{n−1} = A_{n−2} よりp | gcd(A_{n−j}, A_{n−2}) となる。以上より数学的帰納法より A_{0}, A_{1}, …, A_{n} はどの 2 つも互いに素である。 n ≥ 3 に対し A_{n} > 1 となるから A_{0}, A_{1}, … は 1 より大きく、かつどの 2 つも互いに素である整数の無限列を含んでいる。よって素数の個数は無限個である。

なお A_{0} = b_{0}, A_{1} = b_{0}b_{1} +1, A_{2} = b_{0}b_{1}b_{2} +b_{0} +b_{2} and b_{n} = A_{0}A_{1} ⋯ A_{n−3} により数列 b_{i}(i = 0, 1, …) を定めると A_{n} は連分数 [b_{0}, b_{1}, b_{2}, …] の近似分数の分子となる。

参考 V. C. Harris, Another proof of the infinitude of primes, Amer. Math. Monthly 63 (1956), 711.

17 チェルノフの証明

チェルノフの証明は単純な数え上げの議論のみを用いる。 k 個の素数 p_{1}, p_{2}, …, p_{k} しか存在しないと仮定する。 N が正の整数ならば k 個の正の整数の組 (e_{1}, e_{2}, …, e_{k}) で p_{1}^{e_{1}}p_{2}^{e_{2}} ⋯ p_{k}^{e_{k}} ≤ N すなわち e_{1} log p_{1} + e_{2} log p_{2} + ⋯ + e_{k} log p_{k} ≤ log N となるものは少なくとも N 個存在する（実際には素因数分解の一意性よりちょうど N 個となる）。そのような整数の組の個数は (log N)^{k}/(k! log p_{1} log p_{2} ⋯ log p_{k}) 以下であるから N ≤ c(log N)^{k} となる正の整数 c が（ N に無関係に）存在する。これは N が大きいとき成り立たない。よって素数は無限に多く存在する。

この証明では素因数分解の一意性は必要とされない。また、議論を少し変更することにより p_{1}, p_{2}, …, p_{k} を N 以下のすべての素数としてもよいことがわかる。このとき c = 1/(k! log 2) ととることができ、 N ≤ (log N)^{k}/(k! log 2) となる。したがって k > c′ log N となる正の絶対定数 c′ が存在する。つまり N 以下の素数の個数は少なくとも c′ log N であることがわかる。

参考 Paul R. Chernoff, A “Lattice Point” Proof of the Infinitude of Primes. Math. Mag. 38 (1965), 208.