Euclid's theorem
Euclid's theorem is a fundamental statement in number theory that asserts that there are infinitely many prime numbers. There are several well-known proofs of the theorem.
Euclid offered a proof published in his work Elements (Book IX, Proposition 20), which is paraphrased here.
Consider any finite list of prime numbers p1, p2, ..., pn. It will be shown that at least one additional prime number not in this list exists. Let P be the product of all the prime numbers in the list: P = p1p2...pn. Let q = P + 1. Then q is either prime or not:
This proves that for every finite list of prime numbers there is a prime number not on the list, and therefore there must be infinitely many prime numbers.
Euclid is often erroneously reported to have proved this result by contradiction, beginning with the assumption that the finite set initially considered contains all prime numbers, or that it contains precisely the n smallest primes, rather than any arbitrary finite set of primes. Instead of a proof by contradiction, Euclid's proof shows that no item on a finite list has a particular property. A contradiction is not inferred, but none of the items on the list can have the property of being a divisor of 1.
Several variations on Euclid's proof exist, including the following:
The factorial n! of a positive integer n is divisible by every integer from 2 to n, as it is the product of all of them. Hence, n! + 1 is not divisible by any of the integers from 2 to n, inclusive (it gives a remainder of 1 when divided by each). Hence n! + 1 is either prime or divisible by a prime larger than n. In either case, for every positive integer n, there is at least one prime bigger than n. The conclusion is that the number of primes is infinite.
Another proof, by the Swiss mathematician Leonhard Euler, relies on the fundamental theorem of arithmetic: that every integer has a unique prime factorization. If P is the set of all prime numbers, Euler wrote that:
...
Wikipedia