Part I · Numbers Chapter 3 of 60
Prime numbers
Some numbers can't be broken into factors. Everything else is built from them by multiplication, there are infinitely many of them, and nobody can say in advance where the next one will turn up.
Builds on: 2 · Zero and minus
You will learn
- check quickly whether a number is prime, and list all primes up to a bound with the sieve of Eratosthenes
- break numbers into prime factors and understand why the factorization is unique
- prove that there are infinitely many primes, and estimate how many there are up to a given number
In the last chapter the integers became well behaved: you can always add, subtract and multiply them. Division doesn't work that way, and the chapter ended with a question it's now time to take seriously. Which numbers divide which? And are there "atoms" among them, numbers from which all the others are assembled by multiplication, the way substances are assembled from chemical elements?
Let's start with tiles. Twelve square tiles can be laid out as a $3 \times 4$ rectangle, or $2 \times 6$, or stretched into a $1 \times 12$ strip. With thirteen tiles that won't work: in two rows one tile is left over, in three rows as well, and so on all the way. Only the strip remains.
The "strip" numbers are our quarry. This chapter is a hunt for them: how to recognise them, how to catch them all at once, how many there are, where they hide, and which of their secrets nobody has cracked yet.
What we are hunting
First let's agree on words. A rectangle of $n$ tiles with sides $a$ and $b$ is the equation $n = a \cdot b$.
A divisor of a number $n$ is a number $d$ such that $n = d \cdot k$ for some integer $k$, that is, $n$ divides by $d$ with no remainder. We write $d \mid n$ and read it "$d$ divides $n$". The number $n$ is then called a multiple of $d$. A natural number also has negative divisors ($-3$ divides $12$), but when we talk about the divisors of a natural number we'll mean the natural ones.
Twelve has six divisors: $1, 2, 3, 4, 6, 12$. One and the number itself always divide it; these divisors come "for free". The interesting question is whether there are others.
A natural number is called prime if it is greater than one and divisible only by $1$ and by itself. A number greater than one that has other divisors as well is called composite.
The primes up to fifty: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47$. Two is the only even prime: every other even number is divisible by two. And one is neither prime nor composite. That convention was chosen on purpose, and there is a good reason for it. We'll get to it once we can see what would break without it.
Which of these numbers is prime?
$51 = 3 \cdot 17$, $57 = 3 \cdot 19$, $91 = 7 \cdot 13$: all three are only pretending. According to a well-known anecdote, Alexander Grothendieck, one of the deepest mathematicians of the twentieth century, when asked to name a specific prime, said $57$; ever since it has jokingly been called "Grothendieck's prime". The only honest prime here is $97$.
How to recognise a single prime
To check whether $97$ is prime, you could go at it head-on: divide it by $2, 3, 4, \dots, 96$ and see whether any division comes out even. That's ninety-five divisions. Almost all of them are unnecessary, and two observations show why.
The smallest divisor greater than one of a natural number $n > 1$ is a prime number.
The idea: if this divisor were composite, it would have a smaller divisor of its own, which would also divide $n$.
Let $d$ be the smallest divisor of $n$ that is greater than one. It exists, because $n$ itself is a divisor of $n$ greater than one. Suppose $d$ is composite. Then $d = e \cdot f$ with $1 < e < d$. Since $d$ divides $n$, we have $n = d \cdot k$ for some integer $k$, and then $n = e \cdot (f k)$: the number $e$ divides $n$ too. That's a divisor of $n$ greater than one and smaller than $d$, whereas we chose $d$ to be the smallest. A contradiction, so $d$ is prime.
Hence the first shortcut: it's enough to divide by primes. If $97$ isn't divisible by $2$, it isn't divisible by $4$, $6$ or $8$ either: anything divisible by four is divisible by two. The second shortcut matters more: it's enough to go up to the square root.
If a natural number $n > 1$ is not divisible by any prime $p$ with $p^2 \le n$, then $n$ is prime.
The trick is to see a composite number as a rectangle: its short side is never longer than the square root.
For $97$ the square root is less than $10$ ($10^2 = 100$), so we check $2, 3, 5, 7$. None of them divides $97$, so it is prime. Four divisions instead of ninety-five.
Find the smallest prime divisor of $221$.
$\sqrt{221}$ is just under $15$ ($15^2 = 225$), so we check $2, 3, 5, 7, 11, 13$. The number isn't divisible by $2$, $3$ or $5$ (it's odd, its digit sum is $5$, and it doesn't end in $0$ or $5$). $221 = 7 \cdot 31 + 4$, $221 = 11 \cdot 20 + 1$, but $221 = 13 \cdot 17$. Answer: $13$.
The sieve: catching them all at once
Checking numbers one at a time is slow if you need all the primes in a row. A better method was devised by Eratosthenes of Cyrene (c. 276 – c. 194 BC), keeper of the Library of Alexandria and the man who measured the circumference of the Earth. His own writings have almost all been lost, and the method reached us as retold by Nicomachus of Gerasa, who wrote around AD 100.
Write out the numbers from $2$ to $120$. The first number, $2$, is prime: circle it and cross out all the even numbers. The first number not crossed out after two is $3$. Two didn't cross it out, so it isn't divisible by $2$, and there are no smaller primes: $3$ is prime. Circle it and cross out the multiples of three. The next survivor is $5$, then $7$. Each time the first survivor is prime: none of the smaller primes divides it, otherwise it would already have been crossed out.
The sieve saves work twice over. It crosses out the multiples of five starting not at $10$ but at $25$: the numbers $10$, $15$ and $20$ are already crossed out by two or three, because each has a factor smaller than five. And the sieve stops at seven. The next survivor, $11$, squared gives $121 > 120$, while a composite number up to $120$ must have a prime divisor no larger than $\sqrt{120} < 11$. All such divisors have already done their job, so everything left standing is prime. Up to $120$ there are thirty of them.
Laid out in sixes, the quarry shows one more telltale sign. After $2$ and $3$, the primes sit in only two columns: they are one less or one more than a multiple of six. The other four columns hold numbers of the form $6k$, $6k + 2$, $6k + 3$, $6k + 4$, and those are divisible by $2$ or by $3$. The converse is false: $25 = 6 \cdot 4 + 1$ and $35 = 6 \cdot 6 - 1$ sit in the "right" columns and are composite all the same.
The sieve of Eratosthenes is a way to list all the prime numbers up to $N$: take the smallest number $p$ not yet crossed out, declare it prime, cross out the multiples of $p$ starting from $p^2$, and repeat while $p^2 \le N$. Everything left is prime.
After the sieve of Eratosthenes has run on the numbers from $2$ to $N$, the numbers left uncrossed are all the primes up to $N$, and only those.
Two things need checking: the sieve never crosses out a prime, and it crosses out every composite.
The sieve crosses out only numbers of the form $m \cdot p$, where $p$ is one of the primes already processed and $m \ge p \ge 2$. Such a number has the divisor $p$, which is neither one nor the number itself (the number is larger than $p$, since $m \ge 2$). So the crossed-out numbers are composite, and the sieve leaves primes alone.
Now take a composite $n \le N$, and let $p$ be its smallest prime divisor: $n = p \cdot m$. Here $m > 1$, and every prime divisor of $m$ divides $n$ and so is at least $p$; hence $m \ge p$ and $n = p \cdot m \ge p^2$. All the more $p^2 \le N$, so the sieve will reach $p$: by what we've just proved nobody crosses $p$ out, and it will be the first survivor after the smaller primes. The sieve crosses out the multiples of $p$ from $p^2$ to $N$, and $n$ is a multiple of $p$ in that range. So $n$ gets crossed out.
For more than twenty centuries the sieve has remained the main way to list primes in a row. Computers sift billions of numbers this way, only they cut them into chunks that fit in memory.
The atoms of multiplication
A composite number by definition splits into a product of two smaller numbers: $360 = 4 \cdot 90$. If a factor is again composite, keep cutting: $4 = 2 \cdot 2$, $90 = 9 \cdot 10$, $9 = 3 \cdot 3$, $10 = 2 \cdot 5$. The numbers keep getting smaller, so sooner or later there will be nothing left to cut. Only primes will remain: the atoms from which the number is built.
However many times you take $360$ apart, at the bottom you'll find three twos, two threes and one five. Repeated factors are conveniently gathered into powers.
A prime factorization writes a number as a product of primes. We've just seen that every number greater than one has one. The main claim of this chapter is that it has only one.
Example: factorizing 2024 in a column
On paper it's handy to set out a factorization like this: on the left what remains, on the right the smallest prime divisor of that number.
$$\begin{array}{r|l} 2024 & 2 \\ 1012 & 2 \\ 506 & 2 \\ 253 & 11 \\ 23 & 23 \\ 1 & \end{array}$$The number $253$ isn't divisible by $2$, $3$, $5$ or $7$, but $253 = 11 \cdot 23$. The number $23$ is prime: $5^2 = 25 > 23$, and it isn't divisible by $2$ or $3$. Result: $2024 = 2^3 \cdot 11 \cdot 23$.
Every natural number greater than one can be written as a product of primes, and this factorization is unique up to the order of the factors.
The idea: keep cutting while you can, and check that you can't cut forever.
Existence is easy. Uniqueness seems just as obvious, but that feeling is deceptive. Here is a world where it breaks.
Suppose this world contains only the numbers $1, 5, 9, 13, 17, 21, 25, 29, \dots$, those that leave remainder $1$ on division by $4$. The product of two of them is again one of them: $(4a + 1)(4b + 1) = 4(4ab + a + b) + 1$. So multiplication works inside the world, and we can ask which of its numbers are "prime", that is, can't be split into smaller numbers of the same world. The number $9$ is prime here: there is no three in this world. The same goes for $21 = 3 \cdot 7$ and $49 = 7 \cdot 7$: their real divisors $3$ and $7$ don't live in this world. Now look:
$$441 = 9 \cdot 49 = 21 \cdot 21.$$Two different factorizations into "primes". This example is attributed to David Hilbert. It shows that uniqueness is a property of the integers specifically, and it has to be proved, not taken on faith.
The proof of uniqueness rests on one fact about primes. In Hilbert's world it fails: the "prime" $9$ divides $21 \cdot 21$ but doesn't divide $21$.
If a prime $p$ divides a product $a \cdot b$ of natural numbers, then $p$ divides $a$ or $p$ divides $b$.
The idea: find the smallest natural number $x$ for which $x \cdot b$ is divisible by $p$, and show that it divides both $p$ and $a$.
Suppose $p$ divides $ab$ but not $a$; we'll prove that then $p$ divides $b$. Call a natural number $x$ suitable if $x \cdot b$ is divisible by $p$. Suitable numbers exist: $p$ is one (the number $pb$ is divisible by $p$) and $a$ is another (by assumption). Let $m$ be the smallest suitable number.
We show that $m$ divides every suitable $x$. Divide $x$ by $m$ with remainder: $x = q m + r$ with $0 \le r < m$ (division with remainder is covered in detail in the next chapter). Then $r b = x b - q \cdot (m b)$. Both $xb$ and $mb$ are divisible by $p$, so their difference $rb$ is too. If $r$ were greater than zero, it would be a suitable number smaller than $m$, but $m$ is the smallest. So $r = 0$, and $m$ divides $x$.
In particular, $m$ divides $p$ and $m$ divides $a$. The only divisors of the prime $p$ are $1$ and $p$. If $m = p$, then $p$ divides $a$, contrary to our assumption. So $m = 1$: the number $1 \cdot b = b$ is divisible by $p$.
In the next chapter the lemma will get a second, very short proof using Euclid's algorithm. For now let's derive uniqueness from it.
Uniqueness of the factorization. Suppose a number has two factorizations into primes: $p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_m$ (factors may repeat). The prime $p_1$ divides the left side, and so the right side, that is, the product $q_1 \cdot (q_2 \cdots q_m)$. By Euclid's lemma $p_1$ divides $q_1$ or divides $q_2 \cdots q_m$; in the second case apply the lemma to $q_2 \cdot (q_3 \cdots q_m)$, and so on. In the end $p_1$ divides one of the $q_j$. The only divisors of the prime $q_j$ are $1$ and $q_j$, and $p_1 > 1$, so $p_1 = q_j$.
Cancel this common factor from both sides. We get two factorizations of a smaller number, with one factor fewer on each side. Repeat the same argument. If one side ran out before the other, the product of the remaining primes would equal $1$, which is impossible: every prime is greater than one. So the factors cancel in pairs to the end, and both factorizations consist of the same primes, each taken the same number of times.
Now it's clear why one was thrown out of the primes. If it were prime, six would have infinitely many factorizations: $6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1 \cdot 1 \cdot 2 \cdot 3 = \dots$, and the main theorem would have to come with the caveat "not counting ones". It's more convenient to exclude one once and for all, in the definition.
The factorization tells you everything about a number as far as divisibility goes. For example, how many divisors it has.
If $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ is the factorization into distinct primes, then $n$ has exactly $(a_1 + 1)(a_2 + 1) \cdots (a_k + 1)$ divisors.
The idea: every divisor is a "piece" of the factorization of $n$, and pieces are easy to count.
Let $d$ divide $n$, that is, $n = d \cdot e$. Factorize $d$ and $e$ into primes and multiply: this gives a factorization of $n$. By uniqueness it coincides with $p_1^{a_1} \cdots p_k^{a_k}$. So the factorization of $d$ contains only the primes $p_1, \dots, p_k$, and each $p_i$ at most $a_i$ times: $d = p_1^{b_1} \cdots p_k^{b_k}$ with $0 \le b_i \le a_i$. Conversely, every such number divides $n$: the quotient is $p_1^{a_1 - b_1} \cdots p_k^{a_k - b_k}$. Different sets of exponents give different numbers, again by uniqueness of factorization. The exponent $b_1$ can be chosen in $a_1 + 1$ ways (from $0$ to $a_1$), $b_2$ in $a_2 + 1$ ways, and so on; all the sets together give $(a_1 + 1)(a_2 + 1) \cdots (a_k + 1)$ divisors.
For $360 = 2^3 \cdot 3^2 \cdot 5$ that's $4 \cdot 3 \cdot 2 = 24$ divisors. The number $60 = 2^2 \cdot 3 \cdot 5$ has twelve divisors, and this abundance is one of the explanations of why the Babylonians counted in sixties.
How many divisors does $72$ have (including $1$ and $72$)?
$72 = 2^3 \cdot 3^2$. A divisor is $2^i \cdot 3^j$ with $i \in \{0, 1, 2, 3\}$ and $j \in \{0, 1, 2\}$: $4 \cdot 3 = 12$ options in all. Here they are: $1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72$.
Factorizing is a skill you'll need in every later chapter about numbers, from fractions to ciphers. Practise it, and if you run into a hard number, the solver will factorize it step by step.
They never run out
The further you go along the number line, the rarer the primes become. Among the first ten numbers there are four, while among the numbers from $91$ to $100$ there is only one, $97$. Maybe somewhere far out they run out altogether, and after the last prime every number is composite?
No. Euclid gave the answer around 300 BC, in Book IX of the Elements (Proposition 20). His proof is still held up as a model: it fits in a few lines and needs nothing beyond division with remainder.
There are infinitely many primes.
The idea: from any finite list of primes, build a number that none of them divides.
This argument is usually retold by contradiction: "suppose there are finitely many primes…" Euclid's own formulation is different and arguably stronger: the primes are more than any proposed multitude of them. His proof works like a machine: feed it any set of primes, and it produces a new one.
Is the number $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1$ prime?
$2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30{,}031 = 59 \cdot 509$. Euclid doesn't claim that $N$ is prime. He claims that $N$ has a prime divisor not on the list. Here there are even two.
What happens if you run the machine again and again
Start with a single two and each time add to the list the smallest prime divisor of $N$. You get the sequence $2, 3, 7, 43, 13, 53, 5, 6{,}221{,}671, 38{,}709{,}183{,}810{,}571, \dots$ It is called the Euclid–Mullin sequence. In 1963 Albert Mullin asked whether every prime eventually appears in it. There is still no answer, although several dozen of its terms have been found. One of the simplest proofs in mathematics leads to a question nobody can answer.
Deserts and twins
There are infinitely many primes, but they are spread very unevenly. After $113$ the next prime is $127$: there are thirteen composite numbers in a row between them. Between $1327$ and $1361$ there are no primes for thirty-three numbers.
A desert of any length can be built on purpose. Write $n!$ for the product $1 \cdot 2 \cdot 3 \cdots n$ (read "$n$ factorial").
For any natural number $n \ge 2$, the numbers $n! + 2,\ n! + 3,\ \dots,\ n! + n$ are $n - 1$ composite numbers in a row.
The idea: $n!$ is divisible by every number from $2$ to $n$, and adding $j$ doesn't spoil that. The drawing shows $n = 4$; the argument is the same for any $n$.
Take $n = 10$: $10! = 3{,}628{,}800$, and all nine numbers from $3{,}628{,}802$ to $3{,}628{,}810$ are composite. With $n = 1000$ you get a desert of $999$ composite numbers. The recipe is wasteful: real deserts of that length occur much earlier. But it proves the main point: the gaps between consecutive primes can be as long as you like.
The number $7! + 5 = 5045$ is certainly composite. Which number from $2$ to $7$ divides it? Find the answer without dividing.
$7! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7$ is divisible by $5$, and so is the term $5$. So the sum is divisible by $5$: $5045 = 5 \cdot 1009$.
And yet the primes keep turning up in pairs one number apart: $3$ and $5$, $5$ and $7$, $11$ and $13$, $17$ and $19$, $29$ and $31$, $41$ and $43$. They can't stand any closer: of two neighbouring numbers one is even, and the only even prime is two, so the only prime neighbours are $2$ and $3$.
Twin primes are pairs of primes that differ by $2$. There are eight pairs below a hundred and thirty-five below a thousand.
The deserts get longer and longer, yet twins keep turning up. Whether they ever run out is one of the most famous unsolved problems; we'll come back to it at the end of the chapter.
A census: how many primes up to x
Since primes are unpredictable one at a time, let's count them wholesale, the way a population is counted.
The prime-counting function $\pi(x)$ is the number of primes not exceeding $x$. For example, $\pi(10) = 4$ (they are $2, 3, 5, 7$) and $\pi(100) = 25$. The letter $\pi$ here has nothing to do with the number $3.14\ldots$; that's just how it turned out.
| $x$ | $\pi(x)$ | $x / \ln x$ | $\pi(x) : \dfrac{x}{\ln x}$ |
|---|---|---|---|
| $10^2$ | $25$ | $22$ | $1.151$ |
| $10^3$ | $168$ | $145$ | $1.161$ |
| $10^4$ | $1229$ | $1086$ | $1.132$ |
| $10^6$ | $78{,}498$ | $72{,}382$ | $1.084$ |
| $10^8$ | $5{,}761{,}455$ | $5{,}428{,}681$ | $1.061$ |
| $10^{10}$ | $455{,}052{,}511$ | $434{,}294{,}482$ | $1.048$ |
The third column holds a guess made by Carl Friedrich Gauss. In a letter to the astronomer Johann Encke (1849) he recalled that he had started thinking about the distribution of primes back in 1792 or 1793, as a teenager, and compiled tables of how many primes fall in each thousand numbers. He noticed that near a number $x$ primes occur with a frequency of about $1/\ln x$.
Here $\ln x$ is the natural logarithm; there's more about it in the chapter on powers and logarithms. For now it's enough to know that it grows very slowly and that for $x = 10^k$ it's roughly $2.3\,k$. Around a thousand $\ln x \approx 6.9$, and about every seventh number is prime; around a million $\ln x \approx 13.8$, so every fourteenth; around a billion, every twenty-first. If every $\ln x$-th number is prime, there are about $x / \ln x$ of them up to $x$.
The sign $\approx$ has to be read with care here. The difference between $\pi(x)$ and $x/\ln x$ doesn't shrink but grows: at $x = 10^6$ it's $6{,}116$, and at $x = 10^{10}$ it's already more than twenty million. What tends to one is the ratio: $1.084$, $1.061$, $1.048$, slowly and not monotonically (from $10^2$ to $10^3$ it even went up), but it does. That is what the theorem says.
The ratio of $\pi(x)$ to $x / \ln x$ tends to one as $x$ grows without bound.
Gauss never managed to prove it. A proof appeared about a hundred years after his observation: in 1896 Jacques Hadamard and Charles-Jean de la Vallée Poussin found it independently. Both built on the ideas of Bernhard Riemann and on complex analysis; we'll walk that path in the chapter on the zeta function.
Gauss's refinement: the logarithmic integral
Gauss himself suggested a more accurate approximation. If the probability of "being prime" near a number $t$ is $1 / \ln t$, then the primes up to $x$ shouldn't be counted by multiplying by a single frequency but by adding up bit by bit: $\mathrm{Li}(x) = \int_2^x \frac{dt}{\ln t}$ (what an integral is, chapter 28 explains). For $x = 10^6$ this gives about $78{,}626$ against the actual $78{,}498$: an error of less than $0.2\,\%$. For $x = 10^{10}$ the error is about three thousand out of four hundred and fifty-five million. How small it stays in general depends on the Riemann hypothesis, the most famous open problem in mathematics.
A pattern on the tablecloth
As Stanisław Ulam told it himself, in 1963 he was bored during a long talk and, for want of anything better to do, began writing numbers in a spiral on a sheet of paper: $1$ in the centre, $2$ to its right, $3$ above that, and on anticlockwise, turn after turn. Then he circled the primes. And he saw something nobody expected: the primes lined up along diagonals.
The pattern was examined on a computer at Los Alamos, where Ulam was working, on spirals of tens of thousands of numbers. In the spring of 1964 the picture made the cover of Scientific American, in Martin Gardner's column, and ever since it has been called the Ulam spiral.
Part of the pattern is easy to explain. The numbers on one diagonal of the spiral are the values of a polynomial of the form $4n^2 + bn + c$. If all its values are even, the diagonal is empty. If the polynomial is never divisible by $2$, $3$ or other small primes for any $n$, its values are prime more often than usual, and the diagonal gets denser.
The record holder among such polynomials has been known since Leonhard Euler, who wrote about it in 1772: $n^2 + n + 41$. For $n = 0, 1, 2, \dots, 39$ it gives forty primes in a row: $41, 43, 47, 53, 61, 71, \dots, 1601$. If you start the spiral at $41$, they all lie on one diagonal.
Forty primes in a row. Does that mean $n^2 + n + 41$ is prime for every $n$?
At $n = 40$ we get $1600 + 40 + 41 = 1681 = 41^2$. And at $n = 41$ all three terms are divisible by $41$: $41 \cdot 43$. It's the same trap as Moser's circle from the introduction, only longer. What's more, no polynomial $f$ with integer coefficients (other than a constant) produces only primes. If $f(1) = p$ is prime, then the difference $f(1 + kp) - f(1)$ is divisible by $(1 + kp) - 1 = kp$, so every value $f(1 + kp)$ is divisible by $p$; and a polynomial can equal $p$ itself for only finitely many values of $k$.
Beyond that, the explanations run out. Why some diagonals are denser than others is described by a conjecture of Godfrey Hardy and John Littlewood (1923), but it hasn't been proved. It isn't even known whether there are infinitely many primes of the form $n^2 + 1$: $2, 5, 17, 37, 101, \dots$ Back in 1912 Edmund Landau put this question on his list of four problems about primes that he considered out of reach. Two questions from the next section made the same list.
The quarry that got away
Primes have been studied for more than two thousand years, and still the simplest-looking questions about them remain open. Here are three that make the newspapers.
Twins
Are there infinitely many pairs of twin primes? Nobody knows. For a long time nobody could even prove that infinitely many pairs of primes lie closer together than some fixed distance, any distance at all. In 2013 Yitang Zhang, then an almost unknown mathematician, proved that there are infinitely many pairs of primes differing by at most $70$ million. Seventy million instead of two, but it was the first finite number. The online collaboration Polymath and James Maynard brought the bound down to $246$. It is separated from two by a barrier that current methods apparently cannot cross.
Goldbach
In 1742 Christian Goldbach, in a letter to Euler, made a guess that today is stated like this: every even number greater than two is the sum of two primes. $4 = 2 + 2$, $28 = 5 + 23 = 11 + 17$, and a hundred can be written in six ways: $3 + 97$, $11 + 89$, $17 + 83$, $29 + 71$, $41 + 59$, $47 + 53$. Computers have checked the conjecture for all even numbers up to $4 \cdot 10^{18}$, but there is no proof. For odd numbers something similar has been proved: in 2013 Harald Helfgott showed that every odd number greater than five is the sum of three primes.
Write $98$ as a sum of two primes. What is the smaller term if you make it as small as possible?
Go through the primes $p$ in increasing order and check whether $98 - p$ is prime: $96$, $95 = 5 \cdot 19$, $93 = 3 \cdot 31$, $91 = 7 \cdot 13$, $87 = 3 \cdot 29$, $85 = 5 \cdot 17$, $81 = 3^4$ are all composite. Only at $p = 19$ do we get the prime $79$. Answer: $98 = 19 + 79$, and the smaller term is $19$. There are three ways in all: also $31 + 67$ and $37 + 61$.
The largest known prime
There are infinitely many primes, but at any moment only finitely many are known, and one of them is the largest. At the time of writing it is $2^{136{,}279{,}841} - 1$, found in October 2024 by the GIMPS project, in which thousands of volunteers donate their computers' power to the search. It has $41{,}024{,}320$ digits: printed at three thousand digits per page, it would fill more than thirteen thousand pages.
The record holders are almost always of the form $2^p - 1$: these are Mersenne numbers, named after the seventeenth-century French friar and scholar Marin Mersenne. There is an especially fast primality test for them. But there's a trap here too: the exponent $p$ must be prime, yet the converse fails. $2^2 - 1 = 3$, $2^3 - 1 = 7$, $2^5 - 1 = 31$, $2^7 - 1 = 127$ are prime, but $2^{11} - 1 = 2047 = 23 \cdot 89$.
Where next
Try to simplify the fraction $\frac{391}{527}$. You can't tell from the numbers what they're divisible by: not $2$, not $3$, not $5$. You could factorize both into primes, as we did in this chapter, and find a common one. For three-digit numbers that's bearable. For twenty-digit numbers trial division stretches to billions of divisions, and numbers with several hundred digits can't be factorized in reasonable time even by a computer.
Is it possible to find a common divisor of two numbers without factorizing them at all? It is, and the method is more than two thousand years old. It's Euclid's algorithm, which opens the next chapter.