The infinitude of the primes

Theorem

The infinitude of the primes

T-005Home MU-101Threads logic · structure

Statement

Working in the ring \( \mathbb{Z} \) of integers, call an integer \( p \) prime if \( p \geq 2 \) and the only positive divisors of \( p \) are \( 1 \) and \( p \) (so units are excluded by definition). Then the set of primes is infinite: for every finite list of primes \( p_1, p_2, \ldots, p_k \) (any \( k \geq 0 \), the list need not be exhaustive, need not consist of the first \( k \) primes, and may be empty) there exists a prime \( q \) with \( q \neq p_i \) for all \( i \). Equivalently, there is no largest prime, and \( \#\{\,p \in \mathbb{N} : p \text{ prime}\,\} = \infty \).

Why it matters

This is the first genuinely non-obvious theorem of number theory and one of the oldest surviving proofs in mathematics (Euclid, Elements IX.20, c. 300 BC). It guarantees that the multiplicative building blocks of \( \mathbb{Z} \) never run out: unique factorisation would be a statement about a finite alphabet otherwise, and analytic number theory — the Euler product for \( \zeta(s) \), Dirichlet's theorem, the Prime Number Theorem — would be vacuous.

Methodologically it is the canonical example of producing an object outside any proposed finite list by constructing a witness from the list itself. The same template ("multiply everything in sight, perturb by a unit, extract a prime factor") reappears in Dirichlet-type results for special arithmetic progressions, in Goldbach's proof via Fermat numbers, and throughout algebra whenever one shows an ideal-theoretic object cannot be exhausted by a finite family.

Hypotheses

The ambient ring is \( \mathbb{Z} \) (equivalently, we work in \( \mathbb{N} \) with its usual multiplication and order).In the formal power series ring \( K[[x]] \) over a field, every element with nonzero constant term is a unit, so \( x \) is the only prime up to units: the conclusion fails even though the ring is infinite. In \( \mathbb{Z}/12\mathbb{Z} \) the whole ring is finite, so no infinitude of anything is possible.

"Prime" excludes units: \( p \geq 2 \), i.e. \( p \neq \pm 1 \).If \( 1 \) were admitted as a prime, the pivotal contradiction "\( q \mid 1 \) is absurd" evaporates — the extracted factor \( q \) could simply be \( 1 \), and the argument would produce nothing new. The exclusion of units is what gives step 7 its teeth.

Every integer \( n \geq 2 \) has at least one prime divisor (a consequence of the well-ordering of \( \mathbb{N} \)).This existence lemma is not free: it is where induction enters. In the multiplicative monoid \( \bigl((1,\infty), \cdot\bigr) \subseteq \mathbb{R} \), which is not well-ordered, no element is irreducible at all — every \( x \gt 1 \) factors as \( \sqrt{x}\cdot\sqrt{x} \) with \( \sqrt{x} \gt 1 \) — so there are no "primes" whose infinitude one could even discuss.

Proof

Fix an arbitrary finite list of primes \( p_1, p_2, \ldots, p_k \) (possibly empty, possibly with gaps). It suffices to exhibit a prime \( q \notin \{p_1,\ldots,p_k\} \).

A set is infinite iff it is contained in no finite set; so producing, for every finite list, a member outside the list proves infinitude. Note the proof is direct: we do not assume the list contains all primes. A

\[ N \;=\; \prod_{i=1}^{k} p_i \;+\; 1 . \]

Then \( N \geq 2 \): if \( k = 0 \) the empty product is \( 1 \) and \( N = 2 \); if \( k \geq 1 \) then each \( p_i \geq 2 \), so \( \prod p_i \geq 2 \) and \( N \geq 3 \).

Definition of \( N \) — the key construction. Multiplying the whole list and adding \( 1 \) manufactures an integer that, as step 6 will show, no listed prime can divide. B

Lemma (existence of a prime divisor). Every integer \( n \geq 2 \) has a prime divisor. Proof. Let \( S = \{\, d \in \mathbb{Z} : d \gt 1 \text{ and } d \mid n \,\} \). Then \( S \neq \emptyset \) since \( n \in S \). By the well-ordering principle \( S \) has a least element \( q \). If \( q \) were not prime, it would have a divisor \( d \) with \( 1 \lt d \lt q \); but \( d \mid q \) and \( q \mid n \) give \( d \mid n \) (transitivity of divisibility), so \( d \in S \), contradicting minimality of \( q \). Hence \( q \) is prime and \( q \mid n \). \( \square \)

Well-ordering principle for \( \mathbb{N} \) (equivalent to strong induction) plus transitivity of divisibility: \( a \mid b \) and \( b \mid c \) imply \( a \mid c \), since \( b = ar,\ c = bs \Rightarrow c = a(rs) \). This lemma is the only place induction is used, and it must be proved, not assumed. C

Since \( N \geq 2 \), the Lemma of step 3 yields a prime \( q \) with \( q \mid N \).

Direct application of the lemma to the integer \( N \) constructed in step 2. A

Suppose, for contradiction on this sub-claim only, that \( q = p_j \) for some \( j \in \{1,\ldots,k\} \). Then \( q \,\Big|\, \prod_{i=1}^{k} p_i \).

If \( q = p_j \) then \( \prod_i p_i = p_j \cdot \prod_{i \neq j} p_i = q \cdot m \) for the integer \( m = \prod_{i\neq j} p_i \); this is the definition of divisibility. A

\[ q \mid N \quad\text{and}\quad q \,\Big|\, \prod_{i=1}^{k} p_i \quad\Longrightarrow\quad q \,\Big|\, \Bigl( N - \prod_{i=1}^{k} p_i \Bigr) = 1 . \]

Linearity of divisibility: if \( q \mid a \) and \( q \mid b \), say \( a = qs \), \( b = qt \), then \( a - b = q(s-t) \), so \( q \mid a - b \). The difference here is exactly the "\( +1 \)" planted in step 2. B

But \( q \mid 1 \) forces \( q \in \{1, -1\} \), contradicting \( q \geq 2 \). Hence \( q \neq p_j \) for every \( j \): the prime \( q \) lies outside the list.

In \( \mathbb{Z} \), \( q \mid 1 \) means \( 1 = qm \) for some integer \( m \), so \( |q|\,|m| = 1 \) and \( |q| = 1 \). This is where the hypothesis "primes are not units" is consumed. A

The list \( p_1,\ldots,p_k \) was an arbitrary finite list of primes, and it omits the prime \( q \). Therefore no finite set contains all primes, i.e. the set of primes is infinite. \( \blacksquare \)

Universal generalisation over the arbitrary list of step 1, together with the characterisation of infinite sets quoted there. A

Result

\[ \#\{\, p \in \mathbb{N} : p \text{ prime} \,\} = \infty ; \qquad \forall\, \{p_1,\ldots,p_k\} \text{ finite primes},\ \exists\, q \text{ prime with } q \,\Big|\, \prod_{i=1}^{k}p_i + 1 \ \text{and}\ q \notin \{p_1,\ldots,p_k\}. \]

Reading. Hand me any finite collection of primes whatsoever and I will manufacture, by one multiplication and one addition, a number whose prime factors are all brand new. So the primes can never be exhausted: there is always a next one.

Scope. The theorem is a statement about \( \mathbb{Z} \) (equivalently \( \mathbb{N} \)) with the standard definition of prime excluding units. The argument generalises to any integral domain that is not a field, has only finitely many units, and in which every nonzero non-unit has an irreducible factor (e.g. any ring of integers of a number field, where infinitude of prime ideals holds); it does not apply verbatim to rings with infinitely many units such as \( K[[x]] \), where the conclusion is genuinely false.

Corollaries & converses

A recursive prime bound. Writing \( p_1 \lt p_2 \lt \cdots \) for the primes in increasing order, the proof gives \( p_{n+1} \leq p_1 p_2 \cdots p_n + 1 \), whence by induction \( p_n \lt 2^{2^n} \) and \( \pi(x) \geq \lfloor \log_2 \log_2 x \rfloor \) for \( x \geq 2 \) — the first, admittedly feeble, lower bound on the prime-counting function (Problem 5).
Arbitrarily large primes. For every \( M \) there is a prime \( p \gt M \): apply the theorem to the (finite) set of primes \( \leq M \).
A prime-generating recursion. Iterating the construction (always keeping the smallest new prime factor of \( N \)) generates the Euclid–Mullin sequence \( 2, 3, 7, 43, 13, 53, 5, \ldots \) — the proof is constructive, not merely existential.
No meaningful converse. The statement is not an implication, so "converse" can only mean the folklore claim "\( p_1 p_2 \cdots p_k + 1 \) is itself always prime" — and that is false: \( 2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13 + 1 = 30031 = 59 \cdot 509 \) (Worked Problem 2). The theorem only ever asserts that the prime factors of \( N \) are new.
Strengthenings (cited, not proved here). Euler (1737): \( \sum_{p \text{ prime}} \frac{1}{p} = \infty \), which quantifies density, not just infinitude. Dirichlet (1837): infinitely many primes in every progression \( a \bmod m \) with \( \gcd(a,m)=1 \). The Prime Number Theorem (1896): \( \pi(x) \sim x/\log x \).

Fails without

Drop "the ring is \( \mathbb{Z} \)": in \( K[[x]] \), formal power series over a field \( K \), the only prime up to units is \( x \). The Euclid move dies at step 2: for the one-element list \( \{x\} \), \( N = x + 1 \) has nonzero constant term, hence is a unit, and units have no prime factors — step 4 finds nothing. The same failure occurs in the localisation \( \mathbb{Z}_{(2)} \) (fractions with odd denominator): its only prime up to units is \( 2 \), and \( N = 2 + 1 = 3 \) is a unit there.
Drop "units are not primes": admit \( 1 \) as a prime and run the proof with the list \( \{1\} \). Then \( N = 2 \), its "prime" divisor could be taken to be \( 1 \), and step 7's contradiction \( q \mid 1 \Rightarrow \) absurd never fires: the argument can no longer certify that the extracted factor is new. (Historically this is one reason \( 1 \) was expelled from the primes.)
Drop the prime-divisor lemma (i.e. drop well-ordering): in the monoid \( \bigl((1,\infty),\cdot\bigr) \subseteq \mathbb{R} \) every element factors nontrivially forever (\( x = \sqrt{x}\cdot\sqrt{x} \)), so no irreducibles exist and step 4 has no lemma to invoke. Infinite descent of factorisations is exactly what well-ordering forbids in \( \mathbb{N} \).

Common errors

The "Euclid numbers are prime" error. Claiming \( N = p_1\cdots p_k + 1 \) is itself prime. False: \( 30031 = 59 \cdot 509 \). The proof only needs some prime factor of \( N \), and shows that factor is new.
The "proof by contradiction" misreading. Presenting the argument as "assume there are finitely many primes and let \( p_1,\ldots,p_k \) be all of them". Euclid's own proof, and the one above, is direct: take any finite list, produce a prime outside it. The global-contradiction wrapper is harmless but unnecessary, and it obscures the constructive content.
The "new prime is bigger" error. Concluding \( q \gt \max_i p_i \). If the list is \( \{5\} \), then \( N = 6 \) and the new primes are \( 2 \) and \( 3 \) — both smaller than \( 5 \). Newness means \( q \notin \{p_1,\ldots,p_k\} \), nothing more, unless the list happens to be the first \( k \) primes.
Skipping the lemma. Writing "\( N \gt 1 \), so \( N \) has a prime factor" with no justification. That existence claim is a theorem requiring well-ordering (step 3); at degree level it must be proved or cited, not assumed.
Sign/edge sloppiness. Forgetting the empty list (\( k=0 \), \( N=2 \)) when the theorem is stated as "every finite list omits a prime", or asserting \( q \mid 1 \Rightarrow q = 1 \) in \( \mathbb{Z} \) without noting \( q = -1 \) is excluded by \( q \geq 2 \).

Discussion

Euclid's Proposition IX.20 states, in the geometric idiom of the Elements, that "prime numbers are more than any assigned multitude of prime numbers" — infinitude phrased without the modern notion of an infinite set. His proof takes three primes \( A, B, C \), forms their least common multiple plus a unit, and case-splits on whether the result is prime. The modern streamlining above is faithful to its logic: it is a machine that converts any finite stock of primes into a strictly larger one. That the proof is over 2,300 years old and still the standard first proof taught is nearly unique in mathematics.

The theorem sits at the junction of the two pillars of \( \mathbb{N} \): order (well-ordering, used in the lemma) and arithmetic (divisibility, used in the linearity step). Notice what is not used: unique factorisation. The proof needs only existence of a prime factor, never uniqueness — a point worth internalising, since existence comes from well-ordering alone while uniqueness needs Euclid's lemma \( p \mid ab \Rightarrow p \mid a \text{ or } p \mid b \), a strictly deeper fact.

Many independent proofs are now known, each opening a different door: Goldbach's via the pairwise-coprime Fermat numbers \( F_n = 2^{2^n}+1 \) (Problem 4); Euler's analytic proof from the divergence of \( \sum 1/p \), which launched analytic number theory; Furstenberg's 1955 proof using a topology on \( \mathbb{Z} \) whose open sets are unions of arithmetic progressions; and Erdős's counting proof, which bounds how many integers up to \( x \) a finite set of primes could generate. Comparing them is a masterclass in how the same fact can be arithmetic, analytic, topological, or combinatorial.

Algebraically, the right generalisation is: an integral domain \( R \) that is not a field, in which every nonzero non-unit has an irreducible factor, and whose unit group \( R^\times \) is finite, has infinitely many pairwise non-associate irreducibles — run Euclid's argument with \( N = u \cdot a_1 \cdots a_k + 1 \) ranging over the finitely many units \( u \) and note that not every such \( N \) can be a unit when \( R^\times \) is finite. This covers \( \mathbb{Z} \) (units \( \pm 1 \)) and \( K[x] \) for finite fields \( K \); for infinite fields \( K[x] \) needs a separate (easy) argument, and for rings of integers \( \mathcal{O}_K \) with infinite unit group one passes to prime ideals, whose infinitude follows from the splitting of rational primes. The failure of the naive statement in \( K[[x]] \) and in \( \mathbb{Z}_{(p)} \) is precisely a failure of the finite-units hypothesis, not of the Euclid mechanism.

Common misconceptions. (i) "Euclid assumed finitely many primes and derived a contradiction" — his proof is direct. (ii) "\( p_1\cdots p_k+1 \) is prime" — false at \( k=6 \). (iii) "The proof shows primes appear with some regularity" — it gives only the doubly-exponential bound \( p_n \lt 2^{2^n} \), astronomically weaker than the truth \( p_n \sim n \log n \). (iv) "Infinitude is obvious because the integers are infinite" — the units in \( K[[x]] \) show an infinite ring can have essentially one prime.

Worked examples

Example 1 — running the construction on \( \{2,3,5,7\} \). Use the theorem's machine to produce a prime not among \( 2,3,5,7 \).

\[ N = 2 \cdot 3 \cdot 5 \cdot 7 + 1 = 210 + 1 = 211 . \]

Step 2 of the theorem: product of the list plus one. A

By the theorem, every prime factor of \( 211 \) avoids \( \{2,3,5,7\} \). To identify the factor, test primality: since \( 14^2 = 196 \lt 211 \lt 225 = 15^2 \), it suffices to trial-divide by the primes \( \leq 14 \), namely \( 2, 3, 5, 7, 11, 13 \).

If \( n \) is composite, \( n = ab \) with \( 1 \lt a \leq b \) forces \( a \leq \sqrt{n} \), and \( a \) has a prime factor \( \leq \sqrt{n} \) by the step-3 lemma. B

\( 211 \) is odd; digit sum \( 4 \), so \( 3 \nmid 211 \); last digit \( 1 \), so \( 5 \nmid 211 \); \( 211 = 7 \cdot 30 + 1 \); \( 211 = 11 \cdot 19 + 2 \); \( 211 = 13 \cdot 16 + 3 \). No prime \( \leq 14 \) divides \( 211 \).

Direct division with remainder; the divisibility tests for \( 3 \) and \( 5 \) are the standard congruence criteria mod \( 3 \) and mod \( 10 \). A

\[ 211 \text{ is prime, and } 211 \notin \{2,3,5,7\} \]

Reading. The construction not only promises a new prime — here it delivers one outright, since \( N \) itself turned out prime. (It need not: see Problem 2.)

Scope. One concrete instance of the theorem with \( k = 4 \).

Example 2 — Euclid's method with a twist: infinitely many primes \( \equiv 3 \pmod 4 \). The theorem's technique adapts to prove a refined infinitude.

Let \( q_1, \ldots, q_k \) be any finite list (possibly empty) of primes congruent to \( 3 \bmod 4 \). Define \[ N = 4\, q_1 q_2 \cdots q_k - 1 . \] Then \( N \geq 3 \) (empty list gives \( N = 3 \)) and \( N \equiv 3 \pmod 4 \).

Euclid's template, with the perturbation chosen so that \( N \) is forced into the residue class \( 3 \bmod 4 \): indeed \( N = 4m - 1 \equiv -1 \equiv 3 \pmod 4 \). B

\( N \) is odd, so by the step-3 lemma and induction \( N \) is a product of odd primes, each congruent to \( 1 \) or \( 3 \bmod 4 \). If all prime factors of \( N \) were \( \equiv 1 \pmod 4 \), then \( N \equiv 1 \pmod 4 \), since the class \( 1 \bmod 4 \) is closed under multiplication: \( (4a+1)(4b+1) = 4(4ab+a+b)+1 \). This contradicts \( N \equiv 3 \pmod 4 \).

Multiplicativity of congruence classes mod \( 4 \); the closure computation is displayed. Hence some prime \( r \mid N \) with \( r \equiv 3 \pmod 4 \). B

If \( r = q_j \) for some \( j \), then \( r \mid 4 q_1 \cdots q_k \) and \( r \mid N \), so \( r \mid \bigl(4q_1\cdots q_k - N\bigr) = 1 \), impossible for \( r \geq 2 \). Hence \( r \notin \{q_1,\ldots,q_k\} \).

Linearity of divisibility, exactly as in step 6 of the main proof. A

\[ \#\{\, p \text{ prime} : p \equiv 3 \!\!\pmod 4 \,\} = \infty \]

Reading. Not only are there infinitely many primes — infinitely many of them lie in the residue class \( 3 \bmod 4 \). Every finite list of such primes generates a new one.

Scope. The same elementary trick works for \( 5 \bmod 6 \), but not for \( 1 \bmod 4 \): products of primes \( \equiv 3 \) can land in class \( 1 \), so no single congruence forces a factor from class \( 1 \). That case needs quadratic residues, and the general progression \( a \bmod m \), \( \gcd(a,m)=1 \), is Dirichlet's theorem, which is analytic.

Problems

Let \( E_k = p_1 p_2 \cdots p_k + 1 \), where \( p_1 \lt p_2 \lt \cdots \) are the primes in order. Compute \( E_1, \ldots, E_5 \) and decide the primality of each.
Solution

\( E_1 = 2 + 1 = 3 \); \( E_2 = 2\cdot 3 + 1 = 7 \); \( E_3 = 2\cdot 3\cdot 5 + 1 = 31 \); \( E_4 = 2\cdot 3\cdot 5\cdot 7 + 1 = 211 \); \( E_5 = 2\cdot 3\cdot 5\cdot 7\cdot 11 + 1 = 2311 \).

\( 3, 7, 31 \) are prime by inspection. \( 211 \) is prime (Worked Example 1). For \( 2311 \): \( 48^2 = 2304 \lt 2311 \lt 2401 = 49^2 \), so it suffices to trial-divide by primes \( \leq 48 \): \( 2311 \) is odd; digit sum \( 7 \), so \( 3 \nmid 2311 \); last digit \( 1 \), so \( 5 \nmid 2311 \); \( 2311 = 7\cdot 330 + 1 = 11\cdot 210 + 1 = 13\cdot 177 + 10 = 17\cdot 135 + 16 = 19\cdot 121 + 12 = 23\cdot 100 + 11 = 29\cdot 79 + 20 = 31\cdot 74 + 17 = 37\cdot 62 + 17 = 41\cdot 56 + 15 = 43\cdot 53 + 32 = 47\cdot 49 + 8 \). No prime \( \leq 48 \) divides \( 2311 \), so \( E_5 = 2311 \) is prime. All five are prime — which tempts the false conjecture demolished in Problem 2.
Show that \( E_6 = 2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13 + 1 = 30031 \) is composite, factor it completely, and explain carefully why this does not damage Euclid's proof.
Solution

\( 2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13 = 30030 \), so \( E_6 = 30031 \). Trial division: \( 30031 = 59 \cdot 509 \), since \( 59 \cdot 509 = 59\cdot 500 + 59 \cdot 9 = 29500 + 531 = 30031 \). Both factors are prime: \( 59 \lt 64 = 8^2 \) and \( 59 \) is not divisible by \( 2, 3, 5, 7 \); for \( 509 \), note \( 22^2 = 484 \lt 509 \lt 529 = 23^2 \), and \( 509 \) is odd, has digit sum \( 14 \) (so \( 3 \nmid 509 \)), does not end in \( 0 \) or \( 5 \), and \( 509 = 7\cdot 72 + 5 = 11\cdot 46 + 3 = 13\cdot 39 + 2 = 17\cdot 29 + 16 = 19\cdot 26 + 15 \). So \( 30031 = 59 \cdot 509 \) is the complete factorisation.

No damage is done: the proof never claims \( N \) is prime. It claims only that any prime factor of \( N \) is absent from the list — and indeed \( 59 \notin \{2,3,5,7,11,13\} \) and \( 509 \notin \{2,3,5,7,11,13\} \), exactly as steps 5–7 guarantee (each \( p_i \) leaves remainder \( 1 \) when dividing \( N \)).
Prove the lemma of step 3 by strong induction instead of well-ordering: every integer \( n \geq 2 \) has a prime divisor.
Solution

Strong induction on \( n \geq 2 \). Base: \( n = 2 \) is prime and divides itself. Step: let \( n \gt 2 \) and suppose every integer \( m \) with \( 2 \leq m \lt n \) has a prime divisor. If \( n \) is prime, then \( n \mid n \) and we are done. Otherwise \( n \) is composite: \( n = ab \) with \( 1 \lt a \lt n \) and \( 1 \lt b \lt n \). Since \( 2 \leq a \lt n \), the induction hypothesis gives a prime \( q \) with \( q \mid a \). By transitivity of divisibility (\( q \mid a \) and \( a \mid n \)), \( q \mid n \). \( \square \)

Remark: strong induction and well-ordering are equivalent over the other Peano axioms, so this is the same proof in different clothing; either way, some induction principle is indispensable (see "Fails without").
(Goldbach, 1730.) Let \( F_n = 2^{2^n} + 1 \) for \( n \geq 0 \) (the Fermat numbers). (a) Prove \( F_0 F_1 \cdots F_{n-1} = F_n - 2 \) for all \( n \geq 1 \). (b) Deduce \( \gcd(F_m, F_n) = 1 \) for \( m \lt n \). (c) Deduce a second proof of the infinitude of the primes.
Solution

(a) Induction on \( n \). Base \( n = 1 \): \( F_0 = 3 = 5 - 2 = F_1 - 2 \). Step: assuming \( F_0\cdots F_{n-1} = F_n - 2 \), \[ F_0 \cdots F_{n-1} F_n = (F_n - 2)F_n = \bigl(2^{2^n} - 1\bigr)\bigl(2^{2^n} + 1\bigr) = 2^{2^{n+1}} - 1 = F_{n+1} - 2 . \]

(b) Let \( m \lt n \) and \( d \mid F_m \), \( d \mid F_n \) with \( d \gt 0 \). Since \( F_m \) is one of the factors in \( F_0\cdots F_{n-1} \), we get \( d \mid F_0\cdots F_{n-1} = F_n - 2 \), and with \( d \mid F_n \), linearity gives \( d \mid F_n - (F_n - 2) = 2 \). But every \( F_k \) is odd, so \( d \neq 2 \), forcing \( d = 1 \). Hence \( \gcd(F_m, F_n) = 1 \).

(c) Each \( F_n \geq 3 \) has a prime divisor \( q_n \) (step-3 lemma). If \( m \neq n \) then \( q_m \neq q_n \), since a common value would divide both \( F_m \) and \( F_n \), contradicting (b). So \( n \mapsto q_n \) is an injection from \( \mathbb{N} \) into the primes, and the primes are infinite. \( \square \)
(a) Using Euclid's construction, prove \( p_{n+1} \leq p_1 p_2 \cdots p_n + 1 \), where \( p_1 \lt p_2 \lt \cdots \) enumerates the primes. (b) Deduce by induction that \( p_n \lt 2^{2^n} \) for all \( n \geq 1 \). (c) Conclude that the prime-counting function satisfies \( \pi(x) \geq \lfloor \log_2 \log_2 x \rfloor \) for all \( x \geq 4 \).
Solution

(a) Apply the theorem to the list \( p_1, \ldots, p_n \): the number \( N = p_1\cdots p_n + 1 \) has a prime factor \( q \notin \{p_1,\ldots,p_n\} \). Since \( p_1,\ldots,p_n \) are the \( n \) smallest primes and \( q \) is a prime distinct from all of them, \( q \geq p_{n+1} \). Also \( q \mid N \) gives \( q \leq N \). Hence \( p_{n+1} \leq q \leq p_1\cdots p_n + 1 \).

(b) Induction. Base: \( p_1 = 2 \lt 4 = 2^{2^1} \). Step: assume \( p_i \lt 2^{2^i} \) for \( i = 1,\ldots,n \). Then by (a), \[ p_{n+1} \leq p_1 \cdots p_n + 1 \lt 2^{2^1}\, 2^{2^2} \cdots 2^{2^n} + 1 = 2^{\,2^1 + 2^2 + \cdots + 2^n} + 1 = 2^{\,2^{n+1} - 2} + 1 . \] Since \( 2^{\,2^{n+1}-2} + 1 \leq 2^{\,2^{n+1}-2} + 2^{\,2^{n+1}-2} = 2^{\,2^{n+1}-1} \lt 2^{\,2^{n+1}} \), the induction closes: \( p_{n+1} \lt 2^{2^{n+1}} \).

(c) Fix \( x \geq 4 \) and set \( n = \lfloor \log_2 \log_2 x \rfloor \geq 1 \). Then \( 2^n \leq \log_2 x \), so \( 2^{2^n} \leq x \). By (b), \( p_n \lt 2^{2^n} \leq x \), so at least the \( n \) primes \( p_1, \ldots, p_n \) are \( \leq x \), i.e. \( \pi(x) \geq n = \lfloor \log_2 \log_2 x \rfloor \). This bound grows without limit — a quantitative restatement of the theorem — though it is spectacularly weaker than the Prime Number Theorem's \( \pi(x) \sim x/\log x \). \( \square \)