A prime number has exactly two factors, itself and one: 2, 3, 5, 7, 11, 13 and so on. Every other whole number above one is built by multiplying primes together, which is why they are called the building blocks of arithmetic.
They thin out. Between 1 and 100 there are 25 primes; between 1,000,000 and 1,000,100 there are only six. It is natural to wonder whether they stop altogether.
Euclid, around 300 BC, showed they do not. Suppose you had a complete list of every prime. Multiply them all together and add one. The new number is not divisible by any prime on your list, because dividing by any of them leaves a remainder of one. So either it is a new prime, or it has a prime factor that was missing from the list. Either way, the list was not complete.
1. Why It Still Matters
Large primes are the basis of the encryption that protects a card payment. Multiplying two big primes is easy; recovering them from the product is, as far as anyone knows, extremely hard. Euclid’s guarantee that primes never run out is what keeps that supply going.
2. Try It
Take the primes 2, 3 and 5. Multiply them and add one: 31, which is prime. Now try 2, 3, 5, 7, 11 and 13: the result is 30,031, which is 59 times 509. Both outcomes are allowed by the proof, and both give a prime that was not on the list.