Euclid's Infinite-Primes Tree — Assume Finite, Multiply, Add One, Watch a New Prime Fall Out

Euclid's proof that there are infinitely many prime numbers is more than two thousand years old, and it is still the cleanest worked example of proof by contradiction in all of mathematics. The entire argument is three lines long and it can be run in your head. But the three lines pack a remarkable amount of structure, and you understand the argument more deeply once you see it as a tree — a little mechanical process that takes any finite list of primes and produces one that is not on the list.

The claim

Theorem (Euclid). There are infinitely many prime numbers.

The contradiction setup

Suppose — for contradiction — that there are only finitely many primes. Then you could write them all down in a complete list:

p_1, p_2, p_3, \ldots, p_k

(every prime appears somewhere in this list; no primes are missing.)

Now build the number N by multiplying them all together and adding 1:

N = p_1 \cdot p_2 \cdot p_3 \cdots p_k + 1

This N is a positive integer greater than 1, so by the fundamental theorem of arithmetic, it has at least one prime factor. Call that prime factor p.

Claim: p is not on the list \{p_1, p_2, \ldots, p_k\}.

Why? Suppose p were on the list, say p = p_i for some i. Then p_i \mid N (because p \mid N). But p_i also divides p_1 p_2 \cdots p_k (it is one of the factors). So p_i divides the difference:

N - p_1 p_2 \cdots p_k = 1

But no prime divides 1 — every prime is at least 2, and 2 \nmid 1. Contradiction.

So p is a prime not on the list. But the list was supposed to contain every prime. Contradiction. Therefore no finite list of primes contains all of them — there are infinitely many. \square

Why the +1 is the magic: the +1 ensures that N is one more than a multiple of every prime in the list. So no prime from the list can divide N evenly — there is always a remainder of 1. Yet N > 1 must have some prime factor, and that factor cannot come from the list. The extra +1 is what forces a fresh prime to appear.

The tree picture

The proof has the structure of a finite tree: pick any finite collection of primes; multiply them; add 1; watch a new prime fall out. You can keep running this process, and each run grows the list by at least one.

Drag the slider below to run the process on successively larger starting lists. Each time, N and its smallest prime factor (which is necessarily new) appear.

Start from the empty list. Each "Add a prime" click extends the tree: the current list multiplies up to a product $P$; $N = P + 1$ sprouts below; $N$'s smallest prime factor hangs off as a fresh leaf and is added to the list. The tree grows one layer per click, and a new prime falls out every single time.

Why this is the perfect contradiction proof

Three things make Euclid's proof a gem:

The construction is explicit. You do not just argue "something must exist." You build the counterexample to the "finite list" assumption using an elementary operation — multiply and add 1.
The contradiction is algebraic and unavoidable. Dividing N by any prime on the list always leaves a remainder of 1. This is not a subtle maneuver; it follows from the identity N = p_1 p_2 \cdots p_k + 1 by inspection.
The proof is finite and short. Three lines. No case analysis, no induction, no limits. It is a contradiction proof where the contradiction is produced by a single constructive step.

A common misconception: N is not always prime

Students sometimes read Euclid's proof too quickly and come away believing "if you multiply the first k primes and add 1, you always get a prime." This is false. For example:

2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509

N = 30031 is composite. But its prime factors 59 and 509 are not in the input list — that is all Euclid's proof needs. The proof does not claim N is prime. It claims N has a prime factor not on the list. Whether that prime factor is N itself or a smaller factor is irrelevant to the argument.

Why this distinction matters: "N is prime" is a stronger statement than "N has a new prime factor." Euclid's argument only needs the weaker one. Conflating the two is a common student error, and once you see it, the proof becomes more transparent — it is not a recipe for producing primes, it is a recipe for producing fresh prime factors, which is all the proof requires.

The variant: p! + 1 and primorial primes

You can run the same argument starting from "every integer from 1 to n" instead of "every prime": take N = n! + 1. No integer from 2 to n divides N (remainder 1). So every prime factor of N exceeds n. This gives a slightly different infinite-primes proof, also due essentially to Euclid's idea but using factorial instead of primorial.

Primorial primes are primes of the form p_1 p_2 \cdots p_k + 1 — sometimes Euclid's N is itself prime, and when it is, the prime is called a primorial prime. The sequence starts 3, 7, 31, 211, 2311, \ldots (OEIS A018239). It is an open problem whether there are infinitely many primorial primes.

Why contradiction, not a direct construction?

Could you prove there are infinitely many primes directly — i.e., without contradiction? Yes, and Euclid's argument is secretly constructive. Starting from any finite set of primes, it produces a new prime. Iterating: start with \{2\}, get 3; now \{2, 3\}, get 7; now \{2, 3, 7\}, multiply and add 1 to get 43; and so on. This Euclid-Mullin sequence generates an infinite sequence of distinct primes constructively.

So the contradiction wrapper is optional — the same math also serves as a direct existence proof. But historically and pedagogically, the contradiction form is crisper: it focuses attention on the single impossibility (p_i \mid 1) rather than on the generation dynamics of the Euclid-Mullin sequence.

The Indian thread

Indian mathematicians from Aryabhata and Brahmagupta onward were centrally concerned with primes and divisibility. Brahmagupta's methods for solving Pell's equation (x^2 - Ny^2 = 1) required a deep understanding of prime factorisations, and the kuttaka algorithm for linear Diophantine equations rests on the fact that primes cannot be avoided when dividing. Ramanujan later made spectacular conjectures about the distribution of primes, many proven decades after his death.

Euclid's little proof — that primes do not run out — is the scaffolding on which every prime-related result in every tradition stands. Without infinitely many primes, much of number theory would collapse.

The takeaway

Euclid's proof is the perfect small example of proof by contradiction: a finite setup, a single algebraic manoeuvre, an unavoidable contradiction, a sweeping conclusion. If you are new to contradiction proofs, run through this one three or four times. The mechanical "multiply, add 1, spot the new prime" loop is a mental model you will reuse in other contradiction proofs throughout mathematics — any time an argument says "assume a finite list suffices," ask yourself "what is the +1 move that forces something new?"