Prime numbers: the atoms of arithmetic
Every whole number is built from primes, in exactly one way.
A prime number is a whole number greater than 1 whose only divisors are 1 and itself. 7 is prime. 8 is not, because 2 x 4 = 8.
That definition sounds like a piece of trivia. It describes the closest thing arithmetic has to atoms.
The fundamental theorem of arithmetic
Every whole number greater than 1 is either prime, or can be written as a product of primes in exactly one way, ignoring order.
- 12 = 2 x 2 x 3
- 30 = 2 x 3 x 5
- 100 = 2 x 2 x 5 x 5
- 97 = 97, because 97 is prime
The word doing the work is exactly. There is no second, different set of primes that multiplies to 12. That uniqueness is why primes are called the building blocks: every number has one prime recipe and no other.
Why 1 is not prime
This looks like an arbitrary rule and it is not. If 1 counted as prime, the uniqueness above would collapse: 12 would be 2 x 2 x 3, and also 1 x 2 x 2 x 3, and also 1 x 1 x 2 x 2 x 3, endlessly.
So 1 is excluded to protect the theorem that makes primes useful. Definitions in mathematics are often chosen this way - not discovered, but selected because they make the important statements come out clean.
There are infinitely many, and we have known for 2,300 years
Euclid proved it around 300 BC, and the proof is short enough to follow completely.
- Suppose there were only finitely many primes. Call them p1, p2, ... up to pn.
- Multiply them all together and add 1. Call that number N.
- N cannot be divisible by any prime on the list - dividing by any of them leaves remainder 1.
- So either N is itself prime, or it has a prime factor not on the list.
- Either way there is a prime we missed, so the list was not complete.
This is proof by contradiction: assume the opposite of what you want, follow it honestly, arrive at something impossible. It is one of the most powerful moves in mathematics and this is the cleanest example of it.
Try it with any finite list and the same thing happens. The argument does not find the next prime - it proves the list can never be finished, which is a stronger and stranger kind of knowledge.
Finding them: the sieve
Eratosthenes gave the method around 200 BC and it is still how you would do it by hand.
- Write the numbers from 2 upward.
- Circle 2, then cross out every multiple of 2.
- Circle the next uncrossed number, 3, and cross out every multiple of 3.
- Repeat. Everything circled is prime.
One shortcut worth knowing: to test whether n is prime you only need to try divisors up to the square root of n. If n = a x b then one of a or b must be at or below the square root, so if nothing below it divides n, nothing above it will either. Testing 97 means checking only up to 9.
Where they get strange
- They thin out, but never stop. There are 25 primes below 100 and only 8 between 9,900 and 10,000.
- Twin primes - pairs two apart like 11 and 13, or 41 and 43. Whether there are infinitely many is an open problem.
- Goldbach's conjecture - every even number above 2 seems to be the sum of two primes. Checked to enormous values, never proved.
That such simple statements remain unproved after centuries is worth sitting with. Mathematics is not a finished subject, and the unfinished parts are not always exotic.
Why this is not just pretty
Modern encryption depends on a specific asymmetry: multiplying two large primes is fast, and factoring the result back into those primes is - as far as anyone knows - extremely slow.
So a website can publish a number that is the product of two 300-digit primes, use it to let anyone encrypt a message, and stay confident that nobody can reverse it without the factors. Every secure connection you make runs on that gap.
Which means one of the oldest and most abstract topics in mathematics turned out, 2,000 years later, to be the thing protecting online banking. Nobody planned that.