3. Coprime integer sequences 3
Proof of Braun (1897), M´ etrod (1917). Let p1,...,pk be a list of k ≥
2 distinct primes and let P = p1p2 · · · pk. Consider the integer
N := P/p1 + P/p2 + · · · + P/pk.
For each 1 ≤ i ≤ k, we have
N ≡ P/pi =
pj ≡ 0 (mod pi),
so that N is divisible by none of the pi. But N ≥ 2, and so it must possess
a prime factor not on our list.
3. Coprime integer sequences
Suppose we know an infinite sequence of pairwise relatively prime positive
2 ≤ n1 n2 · · · .
Then we may define a sequence of primes pi by selecting arbitrarily a prime
divisor of the corresponding ni; the terms of this sequence are pairwise
distinct because the ni are pairwise coprime.
If we can exhibit such a sequence of ni without invoking the infinitude
of the primes, then we have a further proof of Theorem 1.1. An argument
of this nature was given by Goldbach:
Proof (Goldbach). Let n1 = 3, and for i 1 inductively define
ni = 2 +
The following assertions are all easily verified in succession:
(i) Each ni is odd.
(ii) When j i, we have nj ≡ 2 mod ni.
(iii) We have gcd(ni,nj) = 1 for i = j.
Theorem 1.1 now follows from the above remarks.
A straightforward induction shows that
(1.1) ni =
and this is how Goldbach presented the proof.
Before proceeding, we pause to note that the above proof implies more
than simply the infinitude of the primes. First, it gives us an upper bound
for the nth prime,
+ 1; this translates into a lower bound of the shape
π(x) log log x (x → ∞).