What is a prime number? And why primes matter

A prime number is a whole number greater than 1 that can be divided evenly only by 1 and by itself. The first few are 2, 3, 5, 7, 11 and 13. Other whole numbers above 1, such as 12 = 2 × 2 × 3, are called composite. Primes matter because every whole number above 1 is built by multiplying primes together in exactly one way, which makes them the atoms of arithmetic, and because undoing that multiplication for huge numbers is hard enough to protect some internet encryption.

In short

• A prime has exactly two divisors, 1 and itself; 1 is not prime, and 2 is the only even prime.
• Every whole number above 1 factors into primes in just one way, which is why primes are called the building blocks of numbers.
• There are infinitely many primes, as Euclid proved more than 2,000 years ago, yet they thin out the higher you go.

How do you tell whether a number is prime?

To test a number, try dividing it by every prime up to its square root. If none divides evenly, it is prime. You only need to go as far as the square root because divisors come in pairs: if 91 = 7 × 13, one of the pair, 7, must be at most √91 ≈ 9.5. So to test 97, try 2, 3, 5 and 7 (√97 ≈ 9.8). None divides it, so 97 is prime. To test 91, 7 does, so 91 is not, though it looks as if it might be.

To find all the primes up to some limit at once, the oldest method is still one of the best: the sieve of Eratosthenes, named after the Greek scholar who ran the library at Alexandria in the third century BCE. Wolfram MathWorld describes it as crossing out multiples. Here it is up to 50.

1. Write out 2 to 50.
2. 2 is prime. Cross out every multiple of 2 after it: 4, 6, 8, … 50. That removes 24 numbers.
3. The next number not crossed out, 3, is prime. Cross out its multiples: 9, 15, 21, 27, 33, 39, 45 (6, 12 and the rest are already gone).
4. Next is 5. Cross out 25 and 35; the other multiples of 5 are already crossed.
5. Next is 7. Cross out 49. 7 × 7 = 49 is the last one that matters, because the next prime, 11, has 11 × 11 = 121, past 50.
6. Everything left is prime.

The 15 primes up to 50 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 and 47. The sieve never divides anything; it only counts in steps, which is why it is fast.

Why is every number made of primes?

Any composite number can be split into smaller factors, and those into smaller ones, until only primes are left. Take 360.

1. 360 is even: 360 = 2 × 180.
2. 180 = 2 × 90, and 90 = 2 × 45.
3. 45 isn't even; it divides by 3: 45 = 3 × 15, and 15 = 3 × 5.
4. 5 is prime, so stop.

So 360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5. Start the split another way, say 360 = 8 × 45 or 10 × 36, and you always end with the same three 2s, two 3s and one 5. That every whole number above 1 has exactly one prime factorization, apart from the order of the factors, is called the fundamental theorem of arithmetic. It is what makes primes the atoms of the numbers: knowing a number's prime factors tells you everything about what divides it. The factorization of 360 explains why it has so many divisors, 24 of them, which is one reason 360 degrees in a circle splits so neatly into halves, thirds, quarters, fifths, sixths and more.

Why isn't 1 a prime number?

The definition says "greater than 1", and the reason is the fundamental theorem. If 1 were prime, factorizations would stop being unique: 6 = 2 × 3 = 1 × 2 × 3 = 1 × 1 × 2 × 3, and so on forever. Excluding 1 keeps the rule clean. Mathematicians did sometimes count 1 as prime in earlier centuries; the modern convention settled because so many theorems would otherwise need "except 1" attached.

How do we know primes never run out?

The proof is in Euclid's Elements, Book IX, Proposition 20, written around 300 BCE. As translated by David Joyce at Clark University, Euclid states that prime numbers are more than any assigned multitude of prime numbers: any finite list of primes is missing some.

1. Take any finite list of primes, say 2, 3 and 5.
2. Multiply them all together and add 1: 2 × 3 × 5 + 1 = 31.
3. This new number leaves a remainder of 1 when divided by each prime on the list, so none of them divides it.
4. Either the new number is itself prime, or it has a prime factor. Either way, that prime is not on the list.
5. So no finite list contains every prime. There are infinitely many.

A common misreading is that the product-plus-one is always prime. It isn't. With the primes up to 13, 2 × 3 × 5 × 7 × 11 × 13 + 1 = 30,031, which is 59 × 509. The proof doesn't need it to be prime: 59 and 509 are both missing from the list, which is all the argument requires. The method, assume a finite list is complete and show that it isn't, is a model of mathematical proof, and it is one route into the idea of infinity.

How are primes spread out?

Primes get rarer as numbers grow, but irregularly. There are 25 primes below 100 and 168 below 1,000. The prime number theorem, proved in 1896, says the number of primes up to a large number N is close to N divided by the natural logarithm of N. For N = 1,000 that estimate gives about 145, against the true 168; the percentage error shrinks as N grows. Put another way, near a number N, about one number in every ln N is prime: near a million, roughly one in 14.

Within that trend, primes are wildly uneven. Gaps between consecutive primes can be as long as you like, yet pairs only 2 apart, such as 11 and 13 or 41 and 43, keep turning up. Whether there are infinitely many of these twin primes is unknown. So is Goldbach's conjecture, that every even number above 2 is the sum of two primes (10 = 3 + 7, 100 = 47 + 53), which has been checked by computer far beyond anything a person could test, but never proved. The deepest open question, the Riemann hypothesis, is about exactly how regular the spread of primes is.

The largest known prime is a Mersenne prime, one less than a power of 2. The Great Internet Mersenne Prime Search, a volunteer computing project, announced on 21 October 2024 that Luke Durant had found 2^136,279,841 − 1 on 12 October 2024. It has 41,024,320 digits. It was still the largest on the project's list of known Mersenne primes in November 2026; records fall, so the figure has a date.

Why do primes matter outside mathematics?

The main practical use is cryptography. Multiplying two large primes is quick for a computer; taking the product apart again, when each prime is hundreds of digits long, would take longer than anyone can wait. RSA, one of the most widely used systems of public key cryptography, is built on that gap: the public key contains the product, and only someone who knows the two primes can make the private key. The note on public keys works through RSA with small numbers, 61 and 53. The same idea protects much of what travels over the web through encryption, although many systems now use elliptic-curve methods instead.

Primes turn up in nature in one well-known case: some periodical cicadas in North America emerge every 13 or 17 years, both primes. One hypothesis is that a prime cycle rarely lines up with the shorter cycles of predators or with other broods, though the explanation is still debated.

Check yourself

• Without looking back, explain why you only need to test divisors up to a number's square root.
• Factor 360 into primes, and explain why any other way of splitting it ends in the same primes.
• In Euclid's proof, why doesn't it matter whether the product of the primes plus one is itself prime?

Sources

• Euclid's Elements, Book IX, Proposition 20 — David E. Joyce, Clark University
• Prime number — Eric Weisstein, Wolfram MathWorld
• Sieve of Eratosthenes — Eric Weisstein, Wolfram MathWorld
• GIMPS discovers largest known prime number, 2^136,279,841 − 1 — Great Internet Mersenne Prime Search, 21 October 2024
• List of known Mersenne prime numbers — Great Internet Mersenne Prime Search
• Prime number — Wikipedia