What Is a Prime Number? The Atoms of Arithmetic
By the BrainSnail editorial team. How these articles are written and checked, and how to tell us when one is wrong.
Two, three, five, seven, eleven, thirteen: the primes are the numbers that cannot be broken into smaller factors, and every other whole number is made by multiplying them together. Euclid proved there were infinitely many of them around 300 BC, and the largest one currently known has more than forty million digits. They are the simplest objects in mathematics to define and among the hardest to understand, and the difficulty of telling large ones apart is what keeps a credit card number secret on its way across the internet.
The definition, and why one is left out
A prime is a whole number greater than one whose only divisors are one and itself. Six is not prime, because two times three makes it; seven is, because nothing does. Two is the only even prime, since every other even number is divisible by two. One is excluded by convention, and the convention has a reason: the point of primes is that every number factorises into them in exactly one way, and if one counted as prime, six could be written as two times three, or one times two times three, or one times one times two times three, and the uniqueness would be lost.
That uniqueness is the fundamental theorem of arithmetic, and it is what makes primes the atoms of number. Twelve is two times two times three and nothing else; 360 is two cubed times three squared times five. Every whole number has a prime factorisation and only one, which is why primes rather than any other kind of number are the ones worth studying.
There is no last one
Euclid's proof that the primes never run out is two thousand years old and still the standard one. Suppose there were a finite list of all the primes. Multiply them all together and add one. The result is not divisible by any prime on the list, since dividing by any of them leaves a remainder of one, so either it is a new prime itself or it has a prime factor that was not on the list. Either way the list was incomplete, and since this works for any list, no finite list can be complete.
They do thin out. Among the first hundred numbers, twenty-five are prime; among the first million, about 78,000; and in general the proportion of primes near a number n is roughly one in the natural logarithm of n, a pattern guessed by Gauss as a teenager from tables and proved a century later. The thinning is gradual and never stops, and yet primes keep turning up in pairs two apart, such as 41 and 43 or 101 and 103, and whether that ever stops is unknown.
Finding them
For small numbers the oldest method is still good. The sieve of Eratosthenes writes out the numbers, crosses off every multiple of two, then of three, then of the next number not yet crossed off, and what survives is prime. It finds every prime up to a million in a fraction of a second on a laptop. For a single large number the question is different: is this particular thousand-digit number prime or not? The methods for that:
- •Trial division: try every prime up to the square root, which is hopeless beyond a few dozen digits
- •Fermat's test: a prime p divides a to the power p minus a for any a, so a number that fails this for some a is certainly composite
- •Miller-Rabin: a refinement that, repeated a few dozen times with random values, declares a number prime with an error probability smaller than a hardware fault, and is what real software uses
- •AKS: a 2002 algorithm that decides primality with certainty in a time that grows only polynomially with the number of digits, a theoretical landmark that is too slow to use in practice
Why they guard secrets
Multiplying two 300-digit primes together takes a computer a moment. Taking the 600-digit result and recovering the two primes takes every computer on Earth longer than the age of the universe, as far as anyone knows. That asymmetry is the basis of RSA encryption, the system introduced in 1977 and still behind most secure web connections: a user publishes the product and keeps the two primes secret, anyone can use the product to scramble a message, and only the holder of the primes can unscramble it. Every online purchase leans on the fact that factoring is hard, and nobody has proved that it is; a fast factoring method would be the most consequential discovery in mathematics, and a large enough quantum computer would provide one, which is why replacement systems are being rolled out now.
What is not known
For all the attention, the primes keep their main secrets. Goldbach's conjecture, that every even number above two is the sum of two primes, has been checked to four million million million and not proved. The twin prime conjecture, that there are infinitely many pairs two apart, was not even known to be approachable until 2013, when Yitang Zhang proved there are infinitely many pairs less than 70 million apart, a gap since cut to 246. The Riemann hypothesis, which would describe exactly how the primes are spread, has stood since 1859 with a million-dollar prize attached. The largest known prime, found in 2024, is two to the power 136,279,841 minus one, and the search for the next one runs on volunteers' computers around the world.
The takeaway
A prime number is a whole number above one with no divisors except one and itself, and every whole number is a product of primes in exactly one way, which makes them the building blocks of arithmetic. Euclid proved they are infinite, they thin out at a known rate, they can be found by sieving or tested by probabilistic methods, and the difficulty of splitting a product of two large primes back into its factors is the foundation of internet encryption.