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 =

j=i

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

integers

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 +

1≤ji

nj.

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 =

22i−1

+ 1,

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,

22n−1

+ 1; this translates into a lower bound of the shape

π(x) log log x (x → ∞).