Number of Primes is Infinite/Proof 1
Jump to navigation
Jump to search
Theorem
The number of primes is infinite.
Proof
Aiming for a contradiction, suppose there exists a greatest prime number $N$.
Hence, let $S$ denote the finite set of all prime numbers.
Euclid's Theorem states that:
- For any finite set of prime numbers, there exists a prime number not in that set.
Hence there exists $N'$ not in $S$.
If $N' < N$ then $N \in S$.
Hence:
- $N' > N$
which contradicts the assumption the $N$ is the greatest prime number.
The result follows by Proof by Contradiction.
$\blacksquare$
Sources
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): indirect proof
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): indirect proof