Primes and factorisation

Every whole number greater than $1$ can be broken into primes, and the real question is whether it can be broken in only one way.

The previous lesson ran Euclid's algorithm backwards to get Bézout's identity: for integers $a$ and $b$ , not both zero, there are integers $x$ and $y$ with $a x + b y = \gcd (a, b)$ . This lesson proves Euclid's lemma from Bézout, uses it to prove that factorisation into primes is unique, then turns to finding primes and counting them.

Primes, and why every number has one

An integer $p > 1$ is prime if its only positive divisors are $1$ and $p$ , and an integer $n > 1$ that is not prime is composite, a product $n = a b$ with $1 < a, b < n$ . The number $1$ is neither: if it counted as prime, $6 = 2 \times 3 = 1 \times 2 \times 3$ would already be two factorisations.

Every integer $n > 1$ has a prime divisor, because its smallest divisor $d > 1$ is prime: a divisor $c$ of $d$ with $1 < c < d$ would divide $n$ too, contradicting the choice of $d$ . So the least divisor of $91$ above $1$ is $7$ , which is prime, and $91 = 7 \times 13$ .

That fact carries Euclid's proof that the primes never run out, recalled here from Proof and Logic rather than taught again: for any finite list of primes, their product plus $1$ leaves remainder $1$ on division by each, so its prime divisor is missing from the list. The proof, in Book IX of Euclid's Elements around 300 BC, says nothing about how the primes are spread out, a question the end of this lesson takes up.

Euclid's lemma

Euclid's lemma says: if $p$ is prime and $p ∣ a b$ , then $p ∣ a$ or $p ∣ b$ . (Here $p ∣ a b$ reads " $p$ divides $a b$ ".) Composite numbers fail it: $6 ∣ 4 \times 9$ , yet $6$ divides neither $4$ nor $9$ , because the factors $2$ and $3$ of $6$ went to different places.

The proof is short. Suppose $p ∣ a b$ and $p$ does not divide $a$ . The only positive divisors of $p$ are $1$ and $p$ , so $\gcd (p, a) = 1$ . Bézout's identity gives integers $x$ and $y$ with

p x + a y = 1

Multiply through by $b$ to get $p b x + a b y = b$ . The first term is a multiple of $p$ , and so is the second, since $p ∣ a b$ . So $p$ divides their sum, which is $b$ .

The lemma extends to any number of factors by induction: if $p ∣ a_{1} a_{2} \dots a_{k}$ , write the product as $a_{1} \cdot (a_{2} \dots a_{k})$ , and either $p ∣ a_{1}$ or $p$ divides the shorter product. In particular, if a prime $p$ divides a product of primes $q_{1} q_{2} \dots q_{k}$ , it divides some $q_{j}$ , and since the only divisor of $q_{j}$ above $1$ is $q_{j}$ itself, $p = q_{j}$ .

Example. Prove that $\sqrt{3}$ is irrational.

Suppose $\sqrt{3} = \frac{a}{b}$ with $a$ and $b$ positive integers sharing no common factor. Squaring gives $a^{2} = 3 b^{2}$ , so $3 ∣ a \cdot a$ , and Euclid's lemma gives $3 ∣ a$ . Write $a = 3 c$ ; then $9 c^{2} = 3 b^{2}$ , so $b^{2} = 3 c^{2}$ , and the same step gives $3 ∣ b$ . Now $3$ divides both, contradicting lowest terms. The proof for $\sqrt{2}$ in Proof and Logic used parity at this step; Euclid's lemma works for every prime.

Now you. Prove that $\sqrt{15}$ is irrational.

Answer

Suppose $\sqrt{15} = \frac{a}{b}$ in lowest terms, so $a^{2} = 15 b^{2}$ . Then $3 ∣ a^{2}$ , so $3 ∣ a$ by Euclid's lemma. Writing $a = 3 c$ gives $9 c^{2} = 15 b^{2}$ , that is $3 c^{2} = 5 b^{2}$ . So $3 ∣ 5 b^{2}$ , and since $3$ does not divide $5$ the lemma gives $3 ∣ b^{2}$ and then $3 ∣ b$ . Both $a$ and $b$ are multiples of $3$ , a contradiction.

The fundamental theorem of arithmetic

Theorem. Every integer $n > 1$ is a product of primes, and this product is unique apart from the order of the factors.

Existence is proved by strong induction, where the hypothesis covers every smaller case at once. The number $2$ is prime. Take $n > 2$ and assume every integer from $2$ to $n - 1$ is a product of primes. If $n$ is prime there is nothing to do. Otherwise $n = a b$ with $1 < a, b < n$ , both $a$ and $b$ are products of primes by hypothesis, and writing one list after the other expresses $n$ . Ordinary induction would not do, since $a$ and $b$ can be anywhere below $n$ .

Uniqueness is where Euclid's lemma enters. Suppose

p_{1} p_{2} \dots p_{r} = q_{1} q_{2} \dots q_{s}

with every $p_{i}$ and $q_{j}$ prime, and argue by induction on $r$ . The prime $p_{1}$ divides the right side, so by the extended lemma $p_{1} = q_{j}$ for some $j$ . Reorder so that this one is $q_{1}$ and cancel it, leaving $p_{2} \dots p_{r} = q_{2} \dots q_{s}$ , a shorter equation of the same kind. By the inductive hypothesis its sides are the same primes in some order, and so were the originals. (When $r = 1$ , cancelling leaves $1 = q_{2} \dots q_{s}$ , which forces $s = 1$ .)

Collecting repeated primes gives the standard form $n = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{k}^{e_{k}}$ with $p_{1} < p_{2} < \dots < p_{k}$ and every exponent at least $1$ , so $360 = 2^{3} \cdot 3^{2} \cdot 5$ . Two numbers are equal exactly when their standard forms agree, which is the sense in which the primes are the atoms of the integers. Euclid had the lemma, but the first clear statement and proof of the whole theorem is in Gauss's Disquisitiones Arithmeticae of 1801.

Why uniqueness is not obvious

Uniqueness can feel too obvious to need proof, since factorising $360$ by any route ends at the same primes. To see that it is a real theorem, look at a system where the existence proof works word for word and uniqueness fails.

Take the even numbers $2 ℕ = {2, 4, 6, 8, \dots}$ and call one "prime" there if it is not a product of two even numbers. Such a product is a multiple of $4$ , so the primes of this system are $2, 6, 10, 14, 18, \dots$ , the even numbers that are not multiples of $4$ . The strong induction goes through unchanged, so every even number is a product of these primes. But

36 = 6 \times 6 = 2 \times 18

and $2$ , $6$ and $18$ are all prime in $2 ℕ$ . What failed is Euclid's lemma: $6$ divides $2 \times 18$ in this system, yet divides neither $2$ nor $18$ , because $18 = 6 \times 3$ and $3$ is not in the system. And the lemma failed because its proof did: $2 ℕ$ has no $1$ , so no Bézout combination can equal $1$ .

The same thing happens in systems mathematicians needed. Among the numbers $a + b \sqrt{- 5}$ with $a$ and $b$ integers, $6 = 2 \times 3 = (1 + \sqrt{- 5}) (1 - \sqrt{- 5})$ , and none of those four factors splits further. In 1847 Gabriel Lamé announced a proof of Fermat's last theorem that quietly assumed unique factorisation in a system of this kind, and it emerged that Ernst Kummer had already shown in 1844 that it can fail there. For the ordinary integers the theorem holds, and the reason is the division algorithm, through Euclid's algorithm and Bézout.

Computing with factorisations

In standard form, divisibility becomes a comparison of exponents. If $n = p_{1}^{e_{1}} \dots p_{k}^{e_{k}}$ , then $d ∣ n$ exactly when $d = p_{1}^{f_{1}} \dots p_{k}^{f_{k}}$ with $0 \leq f_{i} \leq e_{i}$ for every $i$ . Conversely, if $n = d m$ , the standard forms of $d$ and $m$ together factorise $n$ , so by uniqueness no prime appears in $d$ more often than in $n$ .

Each divisor is then a choice of exponent for each prime, $e_{i} + 1$ options for $p_{i}$ , so by the product rule the number of positive divisors is

d (n) = (e_{1} + 1) (e_{2} + 1) \dots (e_{k} + 1)

For the gcd and lcm, write both numbers over the same primes, allowing exponent $0$ . A common divisor may take at most the smaller exponent of each prime and a common multiple needs at least the larger, so the gcd takes minimum exponents and the lcm maximum ones. Since $\min (e, f) + \max (e, f) = e + f$ , this proves $\gcd (a, b) \cdot lcm (a, b) = a b$ .

For large numbers Euclid's algorithm is far faster, since nobody knows a fast way to factorise, a gap a later lesson on RSA turns into a lock. By hand, the standard forms show everything at once.

Example. Find the number of divisors of $360$ , and $\gcd (360, 756)$ and $lcm (360, 756)$ .

Factorise: $360 = 2^{3} \cdot 3^{2} \cdot 5$ and $756 = 2^{2} \cdot 3^{3} \cdot 7$ . So $d (360) = 4 \cdot 3 \cdot 2 = 24$ . Over the primes $2, 3, 5, 7$ the exponents are $(3, 2, 1, 0)$ and $(2, 3, 0, 1)$ . Minimums give $\gcd = 2^{2} \cdot 3^{2} = 36$ , and maximums give $lcm = 2^{3} \cdot 3^{3} \cdot 5 \cdot 7 = 7560$ . Check: $36 \times 7560 = 272 160 = 360 \times 756$ .

Now you. Find the number of divisors of $1008$ , and $\gcd (1008, 840)$ and $lcm (1008, 840)$ .

Answer

$1008 = 2^{4} \cdot 3^{2} \cdot 7$ and $840 = 2^{3} \cdot 3 \cdot 5 \cdot 7$ . So $d (1008) = 5 \cdot 3 \cdot 2 = 30$ . The exponents over $2, 3, 5, 7$ are $(4, 2, 0, 1)$ and $(3, 1, 1, 1)$ , giving $\gcd = 2^{3} \cdot 3 \cdot 7 = 168$ and $lcm = 2^{4} \cdot 3^{2} \cdot 5 \cdot 7 = 5040$ , and $168 \times 5040 = 1008 \times 840$ .

The sieve of Eratosthenes

To list the primes up to a bound, the method credited to Eratosthenes of Cyrene, the third century BC scholar who also measured the Earth, crosses out composites instead of testing each number. Write out $2, 3, \dots, n$ . The first number, $2$ , is prime; cross out its multiples. The next survivor, $3$ , is prime, since no smaller prime divides it; cross out its multiples. Each number that survives to its turn is prime, and its multiples go.

The sieve can stop early. If $n = a b$ is composite with $a \leq b$ , then $a^{2} \leq a b = n$ , so $a \leq \sqrt{n}$ : every composite up to $n$ has a prime factor no bigger than $\sqrt{n}$ . Once the primes up to $\sqrt{n}$ have been used, every composite is gone. For the same reason the pass for $p$ can start at $p^{2}$ : smaller multiples of $p$ have a smaller prime factor too.

Run to $100$ , the sieve needs only $2$ , $3$ , $5$ and $7$ . The pass for $2$ crosses out the $49$ even numbers from $4$ to $100$ ; the pass for $3$ removes $16$ new ones, the odd multiples of $3$ from $9$ to $99$ ; the pass for $5$ removes only $25, 35, 55, 65, 85, 95$ ; and the pass for $7$ only $49, 77, 91$ . That is $74$ composites out of the $99$ numbers from $2$ to $100$ , leaving the $25$ primes.

Example. Find the primes between $100$ and $130$ .

Since $\sqrt{130} < 12$ , only $2, 3, 5, 7, 11$ are needed. The pass for $2$ leaves the fifteen odd numbers $101, 103, \dots, 129$ . The pass for $3$ removes $105, 111, 117, 123, 129$ ; the pass for $5$ removes $115$ and $125$ ; the pass for $7$ removes $119 = 7 \times 17$ ; and the pass for $11$ removes $121 = 11^{2}$ . The survivors are $101, 103, 107, 109, 113$ and $127$ , six primes.

Now you. Find the primes between $130$ and $160$ .

Answer

$\sqrt{160} < 13$ , so sieve with $2, 3, 5, 7, 11$ . Of the odd numbers from $131$ to $159$ , the pass for $3$ removes $135, 141, 147, 153, 159$ , the pass for $5$ removes $145$ and $155$ , the pass for $7$ removes $133 = 7 \times 19$ , and the pass for $11$ removes $143 = 11 \times 13$ . The primes are $131, 137, 139, 149, 151, 157$ .

How the primes thin out

Up to $100$ a quarter of the numbers are prime, from $101$ to $160$ only twelve of sixty. Write $π (x)$ for the number of primes up to $x$ (a name here, unrelated to $3.14159 \dots$ ). A computer sieve gives the counts below, set against $\frac{x}{\ln x}$ , with $\ln$ the natural logarithm.

$x$	$π (x)$	$x / \ln x$	ratio
100	25	21.7	1.151
1,000	168	144.8	1.161
10,000	1,229	1,085.7	1.132
1,000,000	78,498	72,382.4	1.084
1,000,000,000	50,847,534	48,254,942.4	1.054

The ratio drifts down towards $1$ , slowly. Carl Friedrich Gauss noticed the pattern in tables of primes around 1792, aged fifteen, and Adrien-Marie Legendre published a similar formula in 1798, but neither could prove it. In 1896 Jacques Hadamard and Charles de la Vallée Poussin, independently, proved the prime number theorem:

lim_{x \to \infty} \frac{π (x)}{x / \ln x} = 1

Both proofs used complex analysis, building on Bernhard Riemann's 1859 work on the zeta function. The theorem has a plain reading: near $x$ , roughly one number in $\ln x$ is prime. Near a million that is one in $14$ , near a billion one in $21$ . Up to a billion the average gap between primes is $10^{9} / 50 847 534 \approx 19.7$ , just under $\ln (10^{9}) \approx 20.7$ , the same slow convergence as in the table.

Locally the primes are irregular. Gaps can be as long as desired: for $n \geq 2$ the $n - 1$ numbers $n! + 2, \dots, n! + n$ are all composite, since $k$ divides $n! + k$ for each $k$ from $2$ to $n$ . Yet primes two apart, like $101$ and $103$ , keep appearing, and whether they do forever is unknown.

Divisibility is a question about remainders

Everything in this lesson has asked whether one number divides another, and that is a question about a remainder: $a ∣ b$ exactly when dividing $b$ by $a$ leaves remainder $0$ . The remainder of a product depends only on the remainders of its factors. Numbers leaving remainders $3$ and $5$ on division by $7$ are $7 s + 3$ and $7 t + 5$ , and their product is $7 (7 s t + 5 s + 3 t) + 15$ , which leaves the same remainder as $15$ , namely $1$ .

In that language Euclid's lemma says: if neither $a$ nor $b$ leaves remainder $0$ on division by a prime $p$ , neither does $a b$ . Nonzero remainders multiply without ever producing $0$ . For a composite divisor this fails, since $2 \times 3$ leaves remainder $0$ on division by $6$ : a divisor of a product that divides neither factor, as $6$ was in $2 ℕ$ . So the natural setting for divisibility is the remainders themselves, and the next lesson makes them into a number system with its own addition and multiplication, where some elements have inverses and equations can be solved.