A prime number is an integer $p>1$ whose only positive divisors are $1$ and $p$ itself; every integer $n>1$ that is not prime is composite, meaning it splits as $n=a\cdot b$ with $1<a,b<n$. The goal of Book IX, Proposition 20 of Euclid's Elements (c. 300 BCE) — in Heath's translation, 'Prime numbers are more than any assigned multitude of prime numbers' — is to show the set $\mathbb{P}=\{2,3,5,7,11,\dots\}$ cannot be exhausted by any finite list.

Note the logical shape of Euclid's own statement: it is not phrased as 'there are infinitely many primes' but as a construction — give me any assigned collection of primes, and I will exhibit a prime not among them. Infinity enters only as the impossibility of completeness for finite lists, which is exactly how ancient Greek mathematics treated the infinite.

The proof rests on two pillars already established earlier in the Elements: that every integer greater than $1$ has a prime divisor (Book VII, Proposition 31), and the elementary fact that a divisor of two numbers also divides their difference — the engine behind the '+1' trick of Step 3.