Euclid's Theorem

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  be the product of all the prime numbers in the list:

Let . Then is either prime or not:

• 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.