Prime Numbers Explained Simply
Written by Viktor Jonas · Reading time about 10 minutes
A prime number is a natural number greater than 1 with exactly two divisors: 1 and itself. 7 is prime, because only 1 and 7 divide it evenly. 8 is not, because 2 and 4 fit as well. Primes are the building blocks every other number is made of — which is why they keep turning up in almost every area of mathematics.
Divisor — a number that divides evenly, with no remainder.
Prime number — exactly two divisors.
Composite number — more than two divisors, for example 12.
Prime factorisation — writing a number as a product of primes.
Sieve of Eratosthenes — a method for finding all primes up to a limit.
Twin primes — two primes two apart, such as 11 and 13.
Why 1 does not count
This looks arbitrary but there is a solid reason. The fundamental theorem of arithmetic says every number above 1 can be split into prime factors in exactly one way. If 1 were prime there would be infinitely many splittings — 12 = 2 · 2 · 3 = 1 · 2 · 2 · 3 = 1 · 1 · 2 · 2 · 3 and so on. Uniqueness would be gone. So 1 is excluded to keep the most important theorem about numbers clean.
Prime factorisation
180 ÷ 2 = 90
90 ÷ 2 = 45
45 ÷ 3 = 15
15 ÷ 3 = 5
5 ÷ 5 = 1
360 = 23 · 32 · 5
The method is blunt and always works: divide by the smallest prime that fits, then carry on with the result until 1 is left. From the factorisation you can then read off things you would otherwise have to guess at — the lowest common multiple or the greatest common divisor of two numbers, for instance.
The sieve of Eratosthenes
| Step | What happens | Crossed out |
|---|---|---|
| 1 | 2 stays, cross out all its multiples | 4, 6, 8, 10 … |
| 2 | 3 stays, cross out all its multiples | 9, 15, 21, 27 |
| 3 | 5 stays, cross out all its multiples | 25 |
| 4 | done, because 7 · 7 = 49 > 30 | — |
What remains is 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. The last step is the most useful one: you only have to sieve up to the square root of the limit. To check whether 97 is prime you test the divisors 2, 3, 5 and 7 — and no further, because 11 · 11 = 121 is already above 97.
Common mistakes
- Counting 1 as a prime
- It is not one.
- Forgetting 2
- It is the only even prime and often gets skipped when listing quickly.
- Testing every number as a divisor
- Checking up to the square root is enough — for three-digit numbers that saves almost all the work.
- "All odd numbers are prime."
- 9, 15, 21 and 25 say otherwise.
There are infinitely many
Euclid proved this more than two thousand years ago, and the proof fits into four lines. Suppose there were only finitely many primes. Multiply them all together and add 1. Dividing the new number by any of the assumed primes leaves a remainder of 1 — none of them fits. So the new number is either prime itself or has a prime factor that was not on the list. Both contradict the assumption. The list can therefore never be complete.
Check whether 143 is a prime number. Explain which divisors you have to test and why you can stop there.
Show solution
The square root of 143 lies between 11 and 12, since 11 · 11 = 121 and
12 · 12 = 144. So only the primes up to 11 need testing: 2, 3, 5, 7 and 11.
2 is out (143 is odd), 3 as well (digit sum 8), 5 too (the last digit is neither 0
nor 5), and 7 does not fit (7 · 20 = 140, remainder 3). But
11 · 13 = 143.
So 143 is not prime. Had 11 failed as well, 143 would have been
prime — any larger divisor would need a smaller partner, and every smaller one has
been checked.
Primes are not only school material. The encryption your browser uses to send banking data relies on the fact that two very large primes are effortless to multiply while the product is practically impossible to take apart again.
Twin primes and record-breaking primes
The further up the number line you go, the rarer primes become — but they never disappear. Sometimes two of them stand close together: 3 and 5, 11 and 13, 17 and 19, 29 and 31, 41 and 43. Pairs with a gap of 2 are called twin primes. A small trick shows where to look: every prime above 3 sits right next to a multiple of 6, because all the other remainders give even numbers or multiples of 3. So apart from the pair 3 and 5, every twin pair has the form 6k − 1 and 6k + 1, for example 5 and 7 or 17 and 19.
Whether there are infinitely many twin primes is still unproven. In 2013, though, the mathematician Yitang Zhang achieved a breakthrough: he showed that there are infinitely many pairs of primes whose gap is at most 70 million. Other researchers then pushed that bound down to 246. So there is still a long way to go before reaching 2.
The largest known primes almost always have the form 2p − 1, where the exponent p is itself a prime. They are called Mersenne primes. The first ones are 2² − 1 = 3, 2³ − 1 = 7, 2⁵ − 1 = 31 and 2⁷ − 1 = 127. It is not automatic, though: already 2¹¹ − 1 = 2,047 is not prime, because 23 · 89 = 2,047. For numbers of this shape there is a particularly fast test, the Lucas-Lehmer test. That is why records can be pushed much further here than for arbitrary numbers. The search is carried out in the community project GIMPS (Great Internet Mersenne Prime Search), where volunteers donate the computing time of their computers. The record numbers have many millions of digits — written out, they would fill many thousands of book pages.
Find all twin primes below 50 and check whether every pair except 3 and 5 has the form 6k − 1 and 6k + 1.
Show solution
The primes up to 50 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47. Two apart are: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31) and (41, 43).
As a check: 5 and 7 lie around 6 (k = 1), 11 and 13 around 12 (k = 2), 17 and 19 around 18 (k = 3), 29 and 31 around 30 (k = 5), 41 and 43 around 42 (k = 7). Only (3, 5) is the odd one out, because 3 itself is a divisor of 6. The prime 47 has no twin, since 45 and 49 are both composite.
How RSA encryption uses primes
The RSA method, named after its inventors Rivest, Shamir and Adleman, has protected data on the internet since the 1970s. The basic idea: you choose two very large primes p and q and multiply them to get n = p · q. The product n is published, the two factors stay secret. Anyone who wants to encrypt a message needs only n and a second public number e. Anyone who wants to read it also needs a secret exponent d, and that can only be worked out by someone who knows p and q.
p = 61 and q = 53, so n = 61 · 53 = 3,233
(p − 1) · (q − 1) = 60 · 52 = 3,120
public: e = 17, secret: d = 2,753
Check: 17 · 2,753 = 46,801 = 15 · 3,120 + 1
Encrypt the message 65: 6517 divided by 3,233 leaves the remainder 2,790
Decrypt: 2,7902753 divided by 3,233 leaves the remainder 65 again
That the message really comes back follows from a theorem of Euler about remainders in division. What matters is the view on security: anyone can split the small number 3,233 in seconds. Real keys use an n of 2,048 bits, which is over 600 decimal digits. Trial division would have to run up to the square root of n, a number with about 300 digits, and that is impossible. Even the fastest known factoring methods take unimaginably long for such numbers on today's computers. It has not been proven, however, that no fast way exists. As far as we know today, quantum computers could in theory provide one if they can ever be built large enough. The security of RSA therefore rests on experience, not on a proof.
Twins, gaps and records
Primes are spread out unevenly, and that is exactly what makes them interesting. Sometimes two sit close together, like 11 and 13 or 41 and 43 — such pairs are called twin primes. Sometimes there are wide gaps: between 113 and 127 there is not a single one. Gaps like that can even be produced to order. Take 101! and add 2, then 3, then 4 and so on up to 101: each of those hundred numbers is divisible by the value you added, so none of them is prime. Arbitrarily long prime-free stretches therefore certainly exist — and yet the primes never stop.
Whether there are infinitely many twins is still unknown. The question is one of the most famous open problems in mathematics. What is known is that primes get rarer as the numbers grow: near a number n, roughly every ln(n)-th number is still prime on average. For three-digit numbers that is about every seventh; around a million, only about every fourteenth.
The RSA method that browsers and banks use to encrypt data relies on two very large primes, each several hundred digits long. Multiplying them takes a fraction of a second. The public key contains only the product — and recovering the two factors from it is, with every known method, practically impossible. That imbalance between an easy forward step and a hopeless reverse step is the entire security of the system. If someone found a fast factorisation method tomorrow, half the encryption on the internet would have to be replaced.