The Infinitude of Primes

Picture a box of LEGO bricks. You can snap many bricks together to build a huge castle or a car, but the bricks themselves can't be split into anything smaller.

In math, the numbers that play the role of these basic bricks are prime numbers (numbers whose only divisors are 1 and themselves). Think of 2, 3, 5, and 7. You can make 6 by multiplying 2 and 3, and you can make 12 by multiplying 2, 2, and 3. Every natural number greater than 1 can be broken down into a product of primes.

So as numbers grow past a hundred million, past a trillion, and on forever, do new basic bricks keep showing up? The bigger a number gets, the more likely it is to be divisible by something else, so it looks as if primes might vanish completely one day. But even at the edge of the universe, primes never run out.

About 2,300 years ago, the ancient Greek mathematician Euclid gave a beautifully simple answer to this question. His original proof showed that, no matter which primes you are given, there is always another prime outside that list. Today it is often retold as a proof by contradiction (a method that assumes something false and shows it leads to a contradiction), starting from the assumption that there are only finitely many primes.

Let's suppose the only primes in the world are 2, 3, and 5. Multiply them all together and add 1. (2 × 3 × 5) + 1 gives you 31.

Divide this new number, 31, by 2, and you get a remainder of 1. Divide by 3, and the remainder is 1. Divide by 5, and it's 1 again. So none of the primes we know divides it evenly. That means 31 is either a new prime itself, or it is divisible by some other prime we didn't know about. Either way, we end up with the conclusion that a new prime that wasn't on the list must exist.

Multiplying all the known primes and adding 1 doesn't always give you a prime. To be more precise, even when the result is composite (not prime), it must still have a prime divisor that is new.

For example, multiply the first six primes and add 1: (2 × 3 × 5 × 7 × 11 × 13) + 1 = 30031. This number is not prime. It splits into 59 and 509, which are two new primes. What matters is this: whether the result is prime or not, a prime outside the original list is always needed.

Primes get rarer as numbers grow, but they never disappear completely. Modern encryption such as RSA, used in online banking and more, relies on two facts: there are plenty of very large primes, and it is extremely hard to split the product of two large primes back into its factors.