**Euclid’s Theorem** is a fundamental, that asserts that there are infinitely many prime numbers.

## Proof by Euclid

Consider any finite list of prime numbers:

It will be shown that at least one additional prime number not in this list exists. Let

Let

- if
is prime, then there is at least one more prime that is not in the list, namely, itself; - if
is not a prime, then some prime factor divides . If this factor were in our list, then it would divide (since is the product of every number in the list); but also divides , as just stated. If divides and also , then must also divide the difference of the two numbers, which is or just . Since no prime number divides , cannot be in the list. This means that at least one more prime number exists beyond those in the list.