Mathematics
Why There Are Infinitely Many Primes
Quick fact
The proof that there are infinitely many primes was given by Euclid around 300 BC and is still one of the most elegant arguments in mathematics.
Why this is interesting
Prime numbers are often small like 2, 3, 5, but can you ever run out of them? Let's find out why the list of primes never ends.
Read the full explanation
Understanding Why There Are Infinitely Many Primes
Prime numbers are the 'atoms' of multiplication—numbers greater than 1 that can only be divided by 1 and themselves. The first few are 2, 3, 5, 7, 11, and they seem to appear irregularly, but they never stop. Euclid's proof uses a clever trick. Imagine you have a list of every prime that exists. Multiply them all together and add 1. This new number is not divisible by any prime on your list—each prime would leave a remainder of 1. So either this number is prime itself (not on your list), or it has a prime factor that wasn't on your list. Either way, your list is missing a prime. So no list can ever be complete.
A deeper explanation
The proof relies on the fundamental theorem of arithmetic: every integer greater than 1 is either prime or a product of primes. Euclid's argument shows that given any finite set of primes, you can construct a number (the product plus 1) that is not divisible by any of them. By the theorem, this number must have some prime divisor, and that divisor cannot be in the set. Therefore, every finite set of primes is incomplete, meaning the set of all primes is infinite. This principle extends beyond primes: it demonstrates a method for proving infinity in mathematics. The result also underpins modern cryptography, where the difficulty of factoring large numbers (which are products of large primes) secures digital communication. The infinite nature of primes ensures there is always a new large prime to use. Euclid's proof is a cornerstone of number theory and a model of elegance and rigor.