Katana VentraIP

Euclid's theorem

Euclid's theorem is a fundamental statement in number theory that asserts that there are infinitely many prime numbers. It was first proven by Euclid in his work Elements. There are several proofs of the theorem.

This article is about the theorem on the infinitude of prime numbers. For the theorem on perfect numbers and Mersenne primes, see Euclid–Euler theorem. For the theorem on the divisibility of products by primes, see Euclid's lemma.

If q is prime, then there is at least one more prime that is not in the list, namely, q itself.

If q is not prime, then some p divides q. If this factor p were in our list, then it would divide P (since P is the product of every number in the list); but p also divides P + 1 = q, as just stated. If p divides P and also q, then p must also divide the difference[3] of the two numbers, which is (P + 1) − P or just 1. Since no prime number divides 1, p cannot be in the list. This means that at least one more prime number exists beyond those in the list.

prime factor

Recent proofs[edit]

Proof using the inclusion-exclusion principle[edit]

Juan Pablo Pinasco has written the following proof.[13]


Let p1, ..., pN be the smallest N primes. Then by the inclusion–exclusion principle, the number of positive integers less than or equal to x that are divisible by one of those primes is

"Euclid's Theorem". MathWorld.

Weisstein, Eric W.

(Euclid's proof, on David Joyce's website at Clark University)

Euclid's Elements, Book IX, Prop. 20