What Is a Prime Number? The Atoms of Arithmetic

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.

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.

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

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.

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.

For decades every largest known prime has been a Mersenne prime, one less than a power of two, named after the French friar Marin Mersenne, who studied them in the seventeenth century. The reason is not that such primes are unusually common but that there is an unusually fast test for them. The Lucas-Lehmer test checks whether two to the power p minus one is prime by running a simple sequence of squarings about p times and looking at the final remainder, far quicker than any general method for a number of the same size.

There is a catch. Two to the power n minus one can only be prime if n itself is prime, because otherwise it splits neatly into factors, but a prime exponent is no guarantee. Two to the power 11 minus one is 2,047, which is 23 times 89. So searchers test prime exponents one by one, and nearly all of them fail. The Great Internet Mersenne Prime Search, a volunteer project running since 1996, has found every record prime since then this way, and a single test at today's sizes can occupy a home computer for days.

Some periodical cicadas in North America spend thirteen or seventeen years underground before emerging together in enormous numbers, and both figures are prime. One leading explanation is that prime cycles help them avoid predators or parasites with shorter regular cycles. A cicada with a twelve-year cycle would meet a predator on a two, three, four or six-year cycle every time it emerged, while a seventeen-year cicada meets a three-year predator only once every fifty-one years. Biologists still debate whether predators were the main pressure, but the arithmetic of rarely coinciding cycles is sound.

Engineers use the same arithmetic on purpose. In a pair of meshing gears, if the tooth counts share no common factor, such as 17 and 30, each tooth on one gear meets every tooth on the other before any pairing repeats. That spreads wear evenly, so a small defect on one tooth is not ground into the same spot over and over; the extra tooth that achieves this is traditionally called a hunting tooth. Computer programs that store data in tables often size those tables with a prime number for a similar reason, to keep patterns in the data from piling onto the same slots.

A frequent misreading of Euclid's argument is that multiplying the first few primes and adding one always gives a new prime. Try it: 2 plus 1 is 3, 2 times 3 plus 1 is 7, and the next three give 31, 211 and 2,311, all prime. Then the pattern breaks. Two times three times five times seven times eleven times thirteen is 30,030, and adding one gives 30,031, which is 59 times 509. The proof never claimed otherwise; it only says the new number has a prime factor missing from the list, and 59 and 509 are exactly such factors.

Checking 30,031 by hand is easier than it sounds, because you only need to try primes up to its square root. If a number splits into two factors, they cannot both be bigger than the square root, or their product would be too large. The square root of 30,031 is a little over 173, so testing primes up to 173 settles it. Shortcuts help with the smallest: a number is divisible by 3 if its digits add up to a multiple of 3, and by 11 if the alternating sum of its digits is. Many numbers look prime and are not, such as 91, which is 7 times 13.

Fermat's test, in the list above, catches most composite numbers, but not all. Take 341. Two to the power 341, divided by 341, leaves a remainder of 2, exactly as it would for a prime, yet 341 is 11 times 31. Such impostors are called pseudoprimes, and 341 is the smallest one for the base 2. Usually a different base exposes them: testing 341 with 3 instead of 2 shows at once that it is composite. So a natural strategy is to try several bases and declare a number prime only if it passes every one.

That strategy fails for a rare kind of number named after Robert Carmichael, who described the smallest of them in 1910. It is 561, which is 3 times 11 times 17, and it passes Fermat's test for every base that shares no factor with it. The trick is that 560 is divisible by 2, 10 and 16, each one less than a prime factor, which forces the remainders to come out as a prime's would. In 1994 three mathematicians proved there are infinitely many such numbers. That is why practical software uses Miller-Rabin, which no composite can pass for more than a quarter of possible bases.

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.