Appearance
1.5 — Primes: The Atoms of Arithmetic
Take any whole number and try to break it into a product of smaller whole numbers. 12 = 3 \times 4, and 4 = 2 \times 2, so 12 = 2 \times 2 \times 3. Now try to break 2, or 3. You cannot. They are indivisible — the atoms that everything else is built from.
A prime number is a whole number greater than 1 whose only divisors are 1 and itself. The first few:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, \ldots
Everything else above 1 is composite — literally, composed of primes.
1. Why 1 is not prime
1 divides only by 1 and itself, which looks like it qualifies. It is excluded, and not arbitrarily.
If 1 were prime, then 12 could be written as 2 \times 2 \times 3, or 1 \times 2 \times 2 \times 3, or 1 \times 1 \times 2 \times 2 \times 3, and every number would have infinitely many prime factorisations. The single most useful fact about primes — that the factorisation is unique — would be destroyed.
So 1 is excluded to protect uniqueness. This is a common pattern in mathematics: a definition is trimmed at the edges so that the theorem you actually care about comes out clean. It is a design decision, and it is worth knowing that it is one.
2. The Fundamental Theorem of Arithmetic
Every whole number greater than 1 can be written as a product of primes in exactly one way, apart from the order of the factors.
60 = 2^2 \times 3 \times 5, \qquad 1001 = 7 \times 11 \times 13, \qquad 97 = 97
It is called fundamental for good reason. It says the primes are a complete and non-redundant description of the integers — like a chemical formula. \text{H}_2\text{O} tells you everything about which atoms are in water, and 2^2 \times 3 \times 5 tells you everything about the multiplicative structure of 60.
Both halves of the theorem need proof, and the second half is the hard one.
Existence is easy and worth doing, because the argument is a beautiful little machine. Suppose some number could not be written as a product of primes. Then there is a smallest such number; call it n. Now n is not prime (a prime is trivially a product of one prime), so n = a \times b with both a and b smaller than n and bigger than 1. But n was the smallest number without a prime factorisation, so a and b both have one. Glue them together and you have a prime factorisation of n — contradicting the assumption. Therefore no such n exists.
That style of argument, "take the smallest counterexample and show it cannot be the smallest", is called infinite descent or strong induction, and Chapter 8.3 develops it properly.
Uniqueness is genuinely harder and rests on a lemma of Euclid: if a prime divides a product ab, then it divides a or it divides b. That sounds obvious and is not — the corresponding statement for non-primes is false, since 6 divides 4 \times 9 = 36 but divides neither 4 nor 9.
What factorisation lets you compute
Once you have the prime factorisations, several things become mechanical.
Greatest common divisor — the largest number dividing both. Take the shared primes, each to the smaller power.
180 = 2^2 \cdot 3^2 \cdot 5, \qquad 168 = 2^3 \cdot 3 \cdot 7
\gcd(180, 168) = 2^2 \cdot 3 = 12
Least common multiple — the smallest number both divide. Take all primes appearing, each to the larger power.
\operatorname{lcm}(180, 168) = 2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520
And a relationship worth remembering, because it saves work:
\gcd(a,b) \times \operatorname{lcm}(a,b) = a \times b
Check: 12 \times 2520 = 30240, and 180 \times 168 = 30240. It holds because every prime's exponent is split into a smaller and a larger part, and the two parts add back to the total.
Counting divisors. If n = p_1^{e_1} p_2^{e_2} \cdots, then the number of divisors is (e_1+1)(e_2+1)\cdots, because each divisor chooses an exponent for each prime independently, anywhere from 0 up to e_i. So 180 = 2^2 3^2 5^1 has 3 \times 3 \times 2 = 18 divisors. You now know how many without listing one.
3. Euclid's algorithm: 2,300 years old and still the fastest
Factorising is fine for small numbers and hopeless for large ones. To find a gcd you do not need factorisation at all, and Euclid knew it.
The insight is one line: \gcd(a, b) = \gcd(b, a \bmod b), where a \bmod b means the remainder when a is divided by b.
Why it works: any number dividing both a and b also divides a - qb for any q, so it divides the remainder too. The set of common divisors is unchanged, so the greatest one is unchanged — and the numbers get smaller each step.
Find \gcd(1071, 462):
1071 = 2 \times 462 + 147
462 = 3 \times 147 + 21
147 = 7 \times 21 + 0
The last nonzero remainder is \mathbf{21}. Three steps, no factorisation, no guessing.
js
// Euclid's algorithm, exactly as reasoned above.
function gcd(a, b) {
while (b !== 0) {
[a, b] = [b, a % b]; // (1)
}
return a; // (2)
}
gcd(1071, 462); // → 21Line (1) replaces the pair (a,b) with (b, a \bmod b), which is the identity above; the % operator is JavaScript's remainder. Line (2) returns a once b has hit zero, because \gcd(a, 0) = a — everything divides zero, so the limiting factor is a itself.
The algorithm runs in a number of steps proportional to the number of digits, not the size — Chapter 1.4's logarithm again. That efficiency is why it sits inside the cryptography of Section 6 and inside every routine that reduces a fraction to lowest terms.
4. There are infinitely many primes
The primes thin out as you go — there are 25 below 100, but only 8 in the hundred numbers around a million. Do they eventually stop?
No, and Euclid's proof from around 300 BCE is one of the most admired arguments ever written. It is short enough to read in a minute and deep enough to have survived twenty-three centuries.
Suppose there were only finitely many primes: p_1, p_2, \ldots, p_k, a complete list. Build the number
N = (p_1 \times p_2 \times \cdots \times p_k) + 1
Now N is bigger than every prime on the list, so it is not on the list, so it must be composite — which means some prime on the list divides it. But every prime on the list divides the product, and therefore leaves a remainder of 1 when dividing N. So no prime on the list divides N. Contradiction. The list cannot have been complete.
Notice what the proof does not do: it does not produce a new prime. 2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30031 = 59 \times 509, which is composite, but its factors are new primes not on the list — which is all the argument needed.
How the primes are spread out
They thin out in a predictable way. The Prime Number Theorem, proved in 1896 independently by Hadamard and de la Vallée Poussin, says the number of primes below x is approximately
\pi(x) \approx \frac{x}{\ln x}
where \pi(x) is standard notation for the prime-counting function and has nothing to do with the circle constant. The practical reading: near a number x, roughly one in every \ln x numbers is prime. Near a trillion, \ln(10^{12}) \approx 27.6, so about one number in twenty-eight is prime. That is why you can find a large prime by picking random numbers and testing them — you will not be looking for long.
Yet the local pattern is stubbornly irregular. There are twin primes like (11,13), (17,19), (41,43) that sit as close as odd numbers can, and it is still unknown whether infinitely many exist. There are also arbitrarily long stretches with no primes at all — easy to prove, in fact: the hundred consecutive numbers 101! + 2, 101! + 3, \ldots, 101! + 101 are each divisible by 2, 3, \ldots, 101 respectively, so none is prime. (Here n! means n \times (n-1) \times \cdots \times 1, the factorial, defined properly in Chapter 7.1.)
5. Finding primes: the sieve
To list every prime up to n, do not test each number. Cross out multiples instead. This is the Sieve of Eratosthenes, from the third century BCE — the same Eratosthenes who measured the Earth's circumference from the shadow of a stick.
Write 2 to n. Circle 2; cross out every multiple of 2. The next uncrossed number is 3; circle it, cross out its multiples. Next uncrossed is 5; and so on. What survives is exactly the primes.
Two optimisations fall straight out of the theory.
Stop at \sqrt{n}. If n = a \times b with both factors above \sqrt{n}, then ab \gt n, a contradiction. So every composite has a factor at or below its square root, and once you have sieved with primes up to \sqrt{n}, everything remaining is prime.
Start crossing out at p^2. Smaller multiples of p have a smaller prime factor and were crossed out already.
The same \sqrt{n} argument makes trial division practical for testing a single number: to check whether 211 is prime, try dividing by primes up to \sqrt{211} \approx 14.5, which is 2, 3, 5, 7, 11, 13. None divides it. It is prime. Six divisions, not two hundred.
6. Why primes secure the internet
Here is the asymmetry that everything rests on.
Multiplying two large primes is trivially fast. Give a computer two 300-digit primes and it produces their 600-digit product instantly.
Factoring that product back is, as far as anyone knows, impossibly slow. No known method on a classical computer factors a general 600-digit number in reasonable time. Not because nobody has tried — this is one of the most attacked problems in computing.
That gap between doing and undoing is called a one-way function, and RSA encryption is built directly on it. Your public key is essentially the product n = pq; your private key depends on knowing p and q separately. Anyone can encrypt with n; only someone who can factor it can decrypt. Volume I, 8.2 works through the actual RSA arithmetic, which uses the modular arithmetic of the next chapter.
Two honest caveats. First, nobody has proved that factoring is hard — it is an assumption backed by decades of failure, which is a different thing from a theorem. Second, Shor's algorithm on a sufficiently large quantum computer would factor efficiently, which is exactly why post-quantum cryptography is being standardised now.
7. Two famous unsolved problems, so you know what they say
Goldbach's conjecture (1742): every even number greater than 2 is the sum of two primes. 4 = 2+2, 10 = 3+7, 100 = 3+97. Checked by computer past 4 \times 10^{18}. Unproven.
The twin prime conjecture: there are infinitely many pairs of primes differing by 2. Unproven, but in 2013 Yitang Zhang — then an unknown lecturer who had worked as an accountant and at a sandwich shop — proved there are infinitely many pairs differing by at most 70 million. Collaborative work has since pushed that bound down to 246. From "no bound at all" to "246" is most of the distance; the last step to 2 remains out of reach.
The Riemann hypothesis, which controls how regularly the primes are distributed, is the most famous unsolved problem in mathematics and gets its own treatment in Chapter 11.4.
Every formula above, built from scratch
None of the results in this chapter are worth memorising, because each one can be rebuilt in under a minute from something simpler. What follows is that rebuilding, one result at a time, so the formula and the reason for it sit on the same page as the explanation that needed them.
Greatest common divisor and lowest common multiple
\gcd(a,b) \times \operatorname{lcm}(a,b) = a \times b
Read it aloud. "The greatest common divisor of a and b, times their lowest common multiple, equals a times b."
Where it comes from. Write both numbers in prime factors — legal by the unique factorisation theorem of 1.5. For each prime p, let a contain p^{i} and b contain p^{j}. The gcd takes the smaller exponent (it must divide both), and the lcm takes the larger (it must be divisible by both). For any two numbers i and j:
\min(i,j) + \max(i,j) = i + j
because between them the min and the max are just the two numbers in some order. So for every prime, the exponent in \gcd \times \operatorname{lcm} equals the exponent in a \times b. Since that holds prime by prime, the products are equal.
A worked case. a = 12 = 2^2 \cdot 3, b = 18 = 2 \cdot 3^2. The gcd takes the smaller exponents: 2^1 \cdot 3^1 = 6. The lcm takes the larger: 2^2 \cdot 3^2 = 36. And 6 \times 36 = 216 = 12 \times 18. This is the practical way to get an lcm: find the gcd with Euclid's algorithm, which is fast, then divide.
Euclid's algorithm
\gcd(a,b) = \gcd(b,\ a \bmod b), \qquad \gcd(a,0) = a
Why it is true. Suppose d divides both a and b. Write a = qb + r, where q is the quotient and r = a \bmod b is the remainder. Then r = a - qb, and since d divides a and divides b, it divides that whole expression, so d divides r. Every common divisor of a and b is therefore also a common divisor of b and r. Running the argument backwards from a = qb + r shows the reverse too. The two pairs have identical sets of common divisors, so they have the same greatest one — and the numbers shrink fast, which is why the algorithm finishes in a blink even for enormous inputs.
Counting divisors from a factorisation
If n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}, then
d(n) = (e_1+1)(e_2+1)\cdots(e_k+1)
Read it aloud. "The number of divisors of n is the product of one more than each exponent."
Where it comes from. A divisor of n is built by choosing how many copies of each prime to include. For p_1 you may take 0, 1, 2, \ldots, e_1 copies — that is e_1 + 1 choices. The choices for different primes are independent, so the total count is the product.
A worked case. 360 = 2^3 \cdot 3^2 \cdot 5^1, so d(360) = 4 \times 3 \times 2 = 24 divisors. And the sum of those divisors has a matching formula, from the geometric series of 2.2 — polynomials:
\sigma(n) = \prod_{i=1}^{k} \frac{p_i^{e_i+1} - 1}{p_i - 1}
For 360: \frac{2^4-1}{1} \times \frac{3^3-1}{2} \times \frac{5^2-1}{4} = 15 \times 13 \times 6 = 1170.
8. Where this shows up in your life
Every HTTPS connection. The padlock in your browser involves large primes, either through RSA or through the elliptic-curve mathematics that has largely replaced it. Volume I, 5.7 covers the handshake.
Every hash table in every program. Table sizes are often chosen prime so that keys with regular spacing do not all collide into the same few slots — a prime size shares no factor with the key pattern.
Gears and cicadas. Gear tooth counts are chosen coprime (gcd of 1) so the same two teeth rarely meet, spreading wear evenly. Some cicada species emerge every 13 or 17 years, both prime, which minimises how often they coincide with predators on shorter cycles.
Every fraction your calculator simplifies. Euclid's algorithm, running invisibly.
The Euclid algorithm's mod operation has been quietly doing the work in this chapter. It deserves its own treatment, because remainders turn out to have an arithmetic of their own — one that keeps clocks, calendars, check digits and cryptography running.