Contents / Number Theory / Divisors & Primes

Chapter 1

Divisors & Primes

Divisibility and its algebra; the division algorithm with existence and uniqueness; tau and sigma from the factorisation, with odd tau characterising the squares; Euclid's infinitude of primes and a second proof via Fermat numbers; the sieve proved correct and the sqrt(n) bound; the Euclidean algorithm, Bezout, Euclid's lemma, and the Fundamental Theorem of Arithmetic with existence and uniqueness kept separate; and Lame's bound with its Fibonacci worst case.

Introduction

Multiplication takes two integers and returns one. Reversing it — given $n$ , which pairs multiply to give it? — is the whole of this chapter, and it is very much harder than the forward direction. The forward direction is a single algorithm you learned at seven. The reverse direction supports an industry: the security of most public-key cryptography rests on the belief that recovering the two factors of a $2048$ -bit product is infeasible, while forming the product takes microseconds.

That asymmetry is not the only surprise. The atoms of multiplication, the primes, are simultaneously rigid and unruly. Rigid, because every integer above $1$ breaks into primes in exactly one way — the Fundamental Theorem of Arithmetic, which is so familiar that its content is easy to miss and whose proof genuinely needs an idea. Unruly, because no formula produces the primes, they thin out but never stop, and the gaps between them can be made as large as you please while pairs of them apparently stay two apart forever.

The chapter is built around one algorithm and one theorem. The algorithm is division with remainder, and everything in the second half is a consequence of iterating it: the Euclidean algorithm, Bézout's identity, Euclid's lemma, and through Euclid's lemma the uniqueness half of the Fundamental Theorem. The theorem is the Fundamental Theorem itself, whose two halves — existence and uniqueness — are proved separately, by completely different arguments, and are kept visibly apart here because conflating them is the classic way to produce a proof that proves nothing.

Along the way we count divisors, sum them, sieve for primes, certify primality with a $n$ bound, and finish with Lamé's theorem: the Euclidean algorithm's worst input is a pair of consecutive Fibonacci numbers, and consequently the algorithm never takes more than about five times the number of decimal digits of the smaller argument. Throughout, integer means element of $Z$ , and $N = {1, 2, 3, \dots}$ . The one axiom we lean on repeatedly is well-ordering: every nonempty set of non-negative integers has a least element.

1.1Divisibility: the definition and its immediate consequences

Divisibility is a relation between integers, defined by an existence statement. It is worth noticing at the outset that the definition never mentions division, remainders or fractions — only multiplication. That is what makes it usable inside $Z$ , where division is not available.

Definition 1.1 (Divisibility). Let $d$ and $n$ be integers. We say $d$ divides $n$ , written $d ∣ n$ , if there exists an integer $k$ with

n = d k .

We then call $d$ a divisor or factor of $n$ , and $n$ a multiple of $d$ . If no such $k$ exists we write $d ∤ n$ .

Intuition. $d ∣ n$ says that $n$ objects can be laid out in rows of $d$ with nothing left over. The quotient $k$ is the number of rows. Negative and zero cases are the same statement read literally: $d ∣ 0$ for every $d$ because $0 = d \cdot 0$ , and $0 ∣ n$ only for $n = 0$ because $0 \cdot k$ is always $0$ .

The asymmetry of $0$ trips people up, so state it once. Every integer divides $0$ ; $0$ divides nothing except $0$ . This is not a convention adopted for convenience — it is forced by the definition, and any rule below that would fail at $0$ carries the hypothesis $n \neq = 0$ explicitly.

Proposition 1.2 (Elementary consequences of the definition). For all integers $a, b, n$ :

$1 ∣ n$ and $n ∣ n$ and $n ∣ 0$ .
If $a ∣ b$ and $b \neq = 0$ , then $∣ a ∣ \leq ∣ b ∣$ .
If $a ∣ b$ and $b ∣ a$ , then $a = \pm b$ .

Proof. For (1), take $k = n$ , $k = 1$ and $k = 0$ respectively in the definition.

For (2), write $b = ak$ . Since $b \neq = 0$ , neither $a$ nor $k$ is zero, so $∣ k ∣ \geq 1$ and $∣ b ∣ = ∣ a ∣∣ k ∣ \geq ∣ a ∣$ .

For (3), if either of $a, b$ is $0$ then the other is too, by the remark that $0$ divides only $0$ , and the conclusion holds. Otherwise both are nonzero and (2) applies in both directions, giving $∣ a ∣ \leq ∣ b ∣$ and $∣ b ∣ \leq ∣ a ∣$ , hence $∣ a ∣ = ∣ b ∣$ , which for integers means $a = \pm b$ .∎

Part (2) is the workhorse of every finiteness argument in the chapter: the divisors of a nonzero $n$ all lie in $[- ∣ n ∣, ∣ n ∣]$ , so there are finitely many of them and a search for them terminates. Part (3) says divisibility is antisymmetric up to sign, which is why it is a partial order on $N$ rather than on $Z$ .

Example 1.3 (Reading the definition off a product). Decide whether $17 ∣ 1054$ , and whether $6 ∣ - 138$ .

Solution.

For the first, look for an integer $k$ with $1054 = 17 k$ . Since $17 \cdot 62 = 1054$ , such a $k$ exists and $17 ∣ 1054$ .
For the second, $- 138 = 6 \cdot (- 23)$ , and $- 23$ is an integer, so $6 ∣ - 138$ . The sign of the quotient is irrelevant: the definition asks only that $k$ be an integer.

□

Pitfall. $d ∣ n$ and $\frac{n}{d}$ are different kinds of object. The first is a statement, true or false; the second is a number, and only meaningful when $d \neq = 0$ . Writing " $6 ∣ 4 = 0.666 \dots$ " confuses the two. The vertical bar is not a slash.

Exercises for §1.1 →

1.2Proper divisors and the classification of numbers

Once we can list the divisors of $n$ , we can add them up, and comparing that sum with $n$ itself produces the oldest classification in arithmetic.

Definition 1.4 (Proper divisor). A proper divisor of a positive integer $n$ is a positive divisor $d$ of $n$ with $d < n$ . Thus $n$ itself is excluded, while $1$ is included whenever $n > 1$ .

Definition 1.5 (Divisor functions). For a positive integer $n$ write

τ (n) = # {d \in N : d ∣ n}, σ (n) = d ∣ n, d \in N \sum d,

the number of divisors and the sum of divisors. The sum of the proper divisors is then $s (n) = σ (n) - n$ .

Definition 1.6 (Perfect, abundant, deficient). A positive integer $n$ is perfect if $s (n) = n$ , equivalently $σ (n) = 2 n$ ; abundant if $s (n) > n$ ; and deficient if $s (n) < n$ .

Intuition. Think of $n$ as a budget and its proper divisors as the pieces you are allowed to spend. A perfect number spends its budget exactly: $6 = 1 + 2 + 3$ . An abundant number overshoots, a deficient one falls short. Deficiency is overwhelmingly the common case — every prime is deficient, with $s (p) = 1$ — and perfection is rare enough that only $51$ perfect numbers are known.

Example 1.7 (Classifying 28 and 12). Classify $28$ and $12$ as perfect, abundant or deficient.

Solution.

The positive divisors of $28$ are $1, 2, 4, 7, 14, 28$ , so $σ (28) = 56$ and $s (28) = 56 - 28 = 28$ . Since $s (28) = 28$ , the number $28$ is perfect.
The positive divisors of $12$ are $1, 2, 3, 4, 6, 12$ , so $σ (12) = 28$ and $s (12) = 16 > 12$ . Hence $12$ is abundant.
For contrast, $σ (15) = 1 + 3 + 5 + 15 = 24$ and $s (15) = 9 < 15$ , so $15$ is deficient.

□

Remark. Euclid proved that if $2^{p} - 1$ is prime then $2^{p - 1} (2^{p} - 1)$ is perfect, and Euler proved that every even perfect number has that shape. Whether an odd perfect number exists is open after more than two thousand years; it is known that one would have to exceed $1 0^{1500}$ .

Exercises for §1.2 →

1.3Transitivity and linearity

Two rules carry almost all the weight in divisibility arguments. The first says the relation composes; the second says the set of multiples of $d$ is closed under integer combinations. Nearly every "show that $d$ divides..." exercise is one of these two applied once or twice.

Theorem 1.8 (Transitivity of divisibility). If $a ∣ b$ and $b ∣ c$ , then $a ∣ c$ .

Proof. By hypothesis there are integers $j$ and $k$ with $b = aj$ and $c = bk$ . Substituting the first into the second,

c = bk = (aj) k = a (jk) .

Since $jk$ is an integer, the definition of divisibility is satisfied with quotient $jk$ .∎

Theorem 1.9 (Linearity of divisibility). If $d ∣ a$ and $d ∣ b$ , then for all integers $x$ and $y$ ,

d ∣ (a x + b y) .

Proof. Write $a = d α$ and $b = d β$ with $α, β \in Z$ . Then

a x + b y = d αx + d β y = d (αx + β y),

and $αx + β y$ is an integer, so $d$ divides $a x + b y$ .∎

An expression $a x + b y$ with $x, y \in Z$ is called an integer linear combination of $a$ and $b$ . The theorem Linearity of divisibility therefore reads: any common divisor of $a$ and $b$ divides every linear combination of them. That single sentence is the seed of the Euclidean algorithm, of Bézout's identity, and of the contradiction in Euclid's proof that the primes do not stop.

Corollary 1.10 (Divisors of a difference). If $d ∣ a$ and $d ∣ (a + b)$ , then $d ∣ b$ .

Proof. Apply the theorem Linearity of divisibility to the two multiples $a + b$ and $a$ with coefficients $x = 1$ and $y = - 1$ : $d$ divides $(a + b) \cdot 1 + a \cdot (- 1) = b$ .∎

Example 1.11 (A divisibility chain). Given that $d ∣ 12$ and $d ∣ 20$ for some positive integer $d$ , what are the possible values of $d$ , and what does the theorem Linearity of divisibility predict about $d ∣ 4$ ?

Solution.

Linearity with $x = 2$ , $y = - 1$ gives $d ∣ (2 \cdot 12 - 20) = 4$ .
So every common divisor of $12$ and $20$ divides $4$ , leaving $d \in {1, 2, 4}$ .
All three do occur, since $1, 2, 4$ each divide both $12$ and $20$ . Notice how the argument found the answer without listing the divisors of either number.

□

Example 1.12 (Transitivity applied twice). Show that if $a ∣ b$ and $b ∣ c$ and $c ∣ 360$ , then $a ∣ 360$ , and give the largest such $a$ when $b = 12$ .

Solution.

Two applications of the theorem Transitivity of divisibility: from $a ∣ b$ and $b ∣ c$ we get $a ∣ c$ , and from $a ∣ c$ and $c ∣ 360$ we get $a ∣ 360$ .
With $b = 12$ the constraint $a ∣ 12$ already forces $a \leq 12$ , and $a = 12$ works since $12 ∣ 360$ .
Largest value: $12$ .

□

Exercises for §1.3 →

1.4Counting and summing the divisors

If $n$ is given in factored form the divisors can be counted without being listed, and the counting argument is a clean piece of combinatorics. It presumes the Fundamental Theorem of Arithmetic, proved later in this chapter in Existence of a prime factorisation and Uniqueness of the prime factorisation; nothing below is circular, since those proofs do not use anything from this section.

Theorem 1.13 (The divisor-counting formula). Let $n > 1$ have prime factorisation

n = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{r}^{a_{r}}

with distinct primes $p_{i}$ and exponents $a_{i} \geq 1$ . Then

τ (n) = (a_{1} + 1) (a_{2} + 1) \dots (a_{r} + 1) .

Proof. We exhibit a bijection between the positive divisors of $n$ and the tuples $(e_{1}, \dots, e_{r})$ of integers with $0 \leq e_{i} \leq a_{i}$ .

If $d = p_{1}^{e_{1}} \dots p_{r}^{e_{r}}$ with $0 \leq e_{i} \leq a_{i}$ , then $n = d \cdot p_{1}^{a_{1} - e_{1}} \dots p_{r}^{a_{r} - e_{r}}$ , and the second factor is an integer, so $d ∣ n$ . This maps tuples to divisors.

Conversely let $d$ be a positive divisor, say $n = d m$ . Factor $d$ and $m$ into primes; concatenating those two factorisations gives a prime factorisation of $n$ , which by uniqueness must be the one we started with. Hence every prime occurring in $d$ is some $p_{i}$ , and its exponent $e_{i}$ in $d$ is at most its exponent $a_{i}$ in $n$ . So $d$ has the stated form, and the map is onto.

It is injective because uniqueness of factorisation says two distinct exponent tuples give distinct integers. Finally, the number of tuples is $\prod_{i = 1}^{r} (a_{i} + 1)$ , since $e_{i}$ is chosen independently from a set of $a_{i} + 1$ values.∎

Intuition. Building a divisor is shopping from $r$ shelves. Shelf $i$ holds the powers $p_{i}^{0}, p_{i}^{1}, \dots, p_{i}^{a_{i}}$ — that is $a_{i} + 1$ options — and you must take exactly one item from each shelf. Multiply the options.

Theorem 1.14 (The divisor-sum formula). With $n$ as in the theorem The divisor-counting formula,

σ (n) = i = 1 \prod r \frac{p _{i}^{a_{i} + 1} - 1}{p _{i} - 1} .

Proof. By the bijection established in the proof of The divisor-counting formula, summing over divisors is summing over exponent tuples:

σ (n) = e_{1} = 0 \sum a_{1} \dots e_{r} = 0 \sum a_{r} p_{1}^{e_{1}} \dots p_{r}^{e_{r}} = i = 1 \prod r (e = 0 \sum a_{i} p_{i}^{e}),

where the second equality is the distributive law: expanding the product of the $r$ sums produces each tuple's term exactly once. Each inner sum is a finite geometric series with ratio $p_{i} \neq = 1$ , whose value is $(p_{i}^{a_{i} + 1} - 1) / (p_{i} - 1)$ .∎

Corollary 1.15 (Odd divisor count characterises squares). A positive integer $n$ has an odd number of positive divisors if and only if $n$ is a perfect square.

Proof. By the theorem The divisor-counting formula, $τ (n) = \prod (a_{i} + 1)$ is odd exactly when every factor $a_{i} + 1$ is odd, that is when every exponent $a_{i}$ is even. Writing $a_{i} = 2 b_{i}$ gives $n = (\prod p_{i}^{b_{i}})^{2}$ , a square. Conversely a square has all exponents even, since squaring doubles every exponent. For $n = 1$ both sides hold, as $τ (1) = 1$ .∎

Intuition. Divisors pair off as $d \leftrightarrow n / d$ , which consumes them two at a time. The only way a divisor can fail to have a distinct partner is $d = n / d$ , that is $d = n$ — which exists exactly when $n$ is a square. That is why $36$ has the odd count $9$ and $35$ the even count $4$ .

Example 1.16 (Divisors of 360). Compute $τ (360)$ and $σ (360)$ .

Solution.

Factor: $360 = 2^{3} \cdot 3^{2} \cdot 5$ .
By The divisor-counting formula, $τ (360) = (3 + 1) (2 + 1) (1 + 1) = 4 \cdot 3 \cdot 2 = 24$ .
By The divisor-sum formula, $σ (360) = \frac{2 ^{4} - 1}{1} \cdot \frac{3 ^{3} - 1}{2} \cdot \frac{5 ^{2} - 1}{4} = 15 \cdot 13 \cdot 6 = 1170$ .
Since $s (360) = 1170 - 360 = 810 > 360$ , the number $360$ is abundant.

□

Example 1.17 (Designing a number with a prescribed divisor count). Find the smallest positive integer with exactly $12$ divisors.

Solution.

We need exponents $a_{i}$ with $\prod (a_{i} + 1) = 12$ . The possible multisets of $(a_{i} + 1)$ are ${12}$ , ${6, 2}$ , ${4, 3}$ , ${3, 2, 2}$ and ${2, 2, 3}$ — the last two coincide.
To minimise the integer, assign the largest exponents to the smallest primes. The candidates are $2^{11} = 2048$ , $2^{5} 3 = 96$ , $2^{3} 3^{2} = 72$ , and $2^{2} \cdot 3 \cdot 5 = 60$ .
The smallest is $60$ , and indeed $τ (60) = (2 + 1) (1 + 1) (1 + 1) = 12$ .

□

Exercises for §1.4 →

1.5Primes: the atoms of multiplication

Definition 1.18 (Prime and composite). An integer $p > 1$ is prime if its only positive divisors are $1$ and $p$ . An integer $n > 1$ that is not prime is composite; equivalently $n = ab$ for some integers $a, b$ with $1 < a, b < n$ . The integer $1$ is neither prime nor composite.

Remark. Excluding $1$ is not squeamishness. If $1$ counted as prime then $12 = 2^{2} \cdot 3 = 1 \cdot 2^{2} \cdot 3 = 1^{2} \cdot 2^{2} \cdot 3$ would have infinitely many prime factorisations and the Fundamental Theorem of Arithmetic would be false as stated. The convention is chosen to make uniqueness true.

Lemma 1.19 (Every integer above 1 has a prime divisor). Every integer $n > 1$ has at least one prime divisor.

Proof. Consider the set $S$ of divisors of $n$ that are greater than $1$ . It is nonempty, since $n \in S$ , and consists of positive integers, so by well-ordering it has a least element $p$ .

Suppose $p$ were composite. Then $p = ab$ with $1 < a < p$ , and $a ∣ p$ with $p ∣ n$ gives $a ∣ n$ by the theorem Transitivity of divisibility. So $a \in S$ and $a < p$ , contradicting minimality of $p$ . Hence $p$ is prime, and $p ∣ n$ .∎

This is the first of many arguments in the chapter that run on well-ordering. The pattern — take the least element of a set of positive integers, show that any failure of the desired property would produce a smaller element — recurs in the division algorithm, in Bézout's identity and in the existence half of the Fundamental Theorem.

Example 1.20 (Smallest prime factor by hand). Find the smallest prime factor of $391$ .

Solution.

Test primes in increasing order. $391$ is odd, its digit sum $13$ is not divisible by $3$ , and it does not end in $0$ or $5$ .
$391 = 7 \cdot 55 + 6$ , so $7 ∤ 391$ ; $391 = 11 \cdot 35 + 6$ , so $11 ∤ 391$ ; $391 = 13 \cdot 30 + 1$ , so $13 ∤ 391$ .
$391 = 17 \cdot 23$ , so the smallest prime factor is $17$ . (There was no need to test beyond $19$ , since $1 9^{2} = 361 < 391 < 441 = 2 1^{2}$ — see Trial division stops at the square root.)

□

Exercises for §1.5 →

1.6Infinitude of the primes

That the primes never stop is the first theorem in mathematics whose proof is a genuine argument rather than a computation, and it has been reproved in dozens of ways. Two are given here: Euclid's, which is a one-line application of linearity, and a second, due to Goldbach, which produces an infinite family of pairwise coprime integers and reads off a distinct prime from each.

Theorem 1.21 (Euclid: there are infinitely many primes). The set of prime numbers is infinite.

Proof. Suppose, for contradiction, that the primes are exactly $p_{1}, p_{2}, \dots, p_{r}$ , a finite list. Put

N = p_{1} p_{2} \dots p_{r} + 1.

Then $N > 1$ , so by the lemma Every integer above 1 has a prime divisor it has a prime divisor $q$ , and $q$ must be one of the $p_{i}$ since the list is all of them. Now $q$ divides the product $p_{1} \dots p_{r}$ and, by assumption, divides $N$ ; so by the corollary Divisors of a difference, $q$ divides $N - p_{1} \dots p_{r} = 1$ . But no prime divides $1$ , since a prime exceeds $1$ and part (2) of Elementary consequences of the definition forbids a divisor of $1$ from exceeding $1$ . This contradiction shows no finite list can contain every prime.∎

Pitfall. Euclid's argument does not claim that $p_{1} \dots p_{r} + 1$ is prime. Taking the first five primes, $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 + 1 = 2311$ is prime, but $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509$ is not. The claim is only that $N$ has a prime factor outside the list — which is exactly what is needed.

Definition 1.22 (Fermat numbers). The $n$ -th Fermat number is $F_{n} = 2^{2^{n}} + 1$ for $n \geq 0$ . The first few are $F_{0} = 3$ , $F_{1} = 5$ , $F_{2} = 17$ , $F_{3} = 257$ , $F_{4} = 65537$ .

Lemma 1.23 (Fermat numbers telescope). For every $n \geq 1$ ,

F_{0} F_{1} \dots F_{n - 1} = F_{n} - 2.

Proof. Induct on $n$ . For $n = 1$ the left side is $F_{0} = 3$ and the right side is $F_{1} - 2 = 5 - 2 = 3$ .

Assume the identity for $n$ . Then

F_{0} \dots F_{n - 1} F_{n} = (F_{n} - 2) F_{n} = (2^{2^{n}} - 1) (2^{2^{n}} + 1) = 2^{2^{n + 1}} - 1 = F_{n + 1} - 2,

using $(2^{2^{n}})^{2} = 2^{2 \cdot 2^{n}} = 2^{2^{n + 1}}$ . This is the identity for $n + 1$ .∎

Theorem 1.24 (Goldbach: a second proof of infinitude). Distinct Fermat numbers have no common divisor greater than $1$ . Consequently there are infinitely many primes.

Proof. Let $m < n$ and let $d > 0$ divide both $F_{m}$ and $F_{n}$ . By the lemma Fermat numbers telescope, $F_{m}$ divides the product $F_{0} \dots F_{n - 1}$ , which equals $F_{n} - 2$ ; hence $d ∣ F_{n} - 2$ . Since also $d ∣ F_{n}$ , the corollary Divisors of a difference gives $d ∣ 2$ , so $d \in {1, 2}$ . But every Fermat number is odd, being $1$ more than a power of $2$ , so $d \neq = 2$ and therefore $d = 1$ .

Now for each $n$ choose, by the lemma Every integer above 1 has a prime divisor, a prime $q_{n} ∣ F_{n}$ . If $q_{m} = q_{n}$ for some $m < n$ then that prime would be a common divisor of $F_{m}$ and $F_{n}$ exceeding $1$ , which we have just excluded. So $n \mapsto q_{n}$ is injective and produces infinitely many distinct primes.∎

Remark. Euclid's proof is non-constructive about which new prime appears; Goldbach's produces an explicit infinite list of pairwise coprime numbers, one prime harvested from each. A third classical proof, Euler's, observes that $\sum_{p} 1/ p$ diverges, which says far more: the primes are not merely infinite but reasonably dense.

Theorem 1.25 (Arbitrarily large prime gaps). For every integer $k \geq 1$ there exist $k$ consecutive composite integers.

Proof. Consider the $k$ integers

(k + 1)! + 2, (k + 1)! + 3, \dots, (k + 1)! + (k + 1) .

For each $j$ with $2 \leq j \leq k + 1$ , the integer $j$ divides $(k + 1)!$ because $j$ is one of the factors in that product, and $j$ divides itself; so by the theorem Linearity of divisibility, $j ∣ (k + 1)! + j$ . Since $2 \leq j < (k + 1)! + j$ , this exhibits a divisor strictly between $1$ and the number, so $(k + 1)! + j$ is composite. There are $k$ such $j$ , and the integers are consecutive.∎

Remark. The primes thin out in a precise sense. Writing $π (x)$ for the number of primes not exceeding $x$ , the Prime Number Theorem asserts $π (x) \sim x / ln x$ , meaning the ratio tends to $1$ . Its proof requires complex analysis and belongs to Analytic Number Theory; the figure below shows how good the approximation already is by $x = 1000$ . Yet the gaps theorem above shows that within this smooth average behaviour there are deserts of any prescribed length, and the twin prime conjecture asserts that there are also infinitely many gaps of size exactly $2$ . Average regularity and local irregularity coexist.

Figure 1.26. The prime counting function

π (x)

against the Prime Number Theorem's estimate

x / ln x

, for

x

up to

1000

. The counted primes (points) run consistently above the estimate, and the ratio

π (x) ln x / x

creeps towards

1

very slowly — it is still only about

1.16

x = 1000

Exercises for §1.6 →

1.7Sieving and primality testing

To decide whether one number is prime, divide by candidate factors. To find every prime up to a bound, do something much better: cross out multiples. Both procedures rest on the same observation about square roots.

Proposition 1.27 (Trial division stops at the square root). If $n > 1$ is composite, then $n$ has a prime divisor $p$ with $p \leq n$ . Consequently, if no prime $p \leq n$ divides $n$ , then $n$ is prime.

Proof. Since $n$ is composite, write $n = ab$ with $1 < a \leq b < n$ . If both factors exceeded $n$ we would get $n = ab > n \cdot n = n$ , which is absurd; so $a \leq n$ . By the lemma Every integer above 1 has a prime divisor, $a$ has a prime divisor $p$ , and $p \leq a \leq n$ . Transitivity of divisibility gives $p ∣ n$ .

The second sentence is the contrapositive: if no prime up to $n$ divides $n$ , then $n$ cannot be composite, and being greater than $1$ it is prime.∎

Intuition. Divisors come in pairs $d$ and $n / d$ straddling $n$ — if one is above, the other is below. So a search below $n$ misses nothing. The saving is enormous: certifying $997$ prime needs trial divisions by the primes up to $31$ , of which there are eleven, not by the $996$ numbers below it.

Method 1.28 (Sieve of Eratosthenes). To list every prime up to $N$ :

Write the integers $2, 3, \dots, N$ , all initially unmarked.
Let $p$ be the smallest unmarked number not yet used as a sieving prime.
Mark every multiple $p^{2}, p^{2} + p, p^{2} + 2 p, \dots$ up to $N$ as composite.
Repeat from step 2 while $p^{2} \leq N$ .
The unmarked numbers are exactly the primes up to $N$ .

Theorem 1.29 (Correctness of the sieve). After the procedure Sieve of Eratosthenes halts, an integer $m$ with $2 \leq m \leq N$ is unmarked if and only if $m$ is prime.

Proof. Suppose $m$ is prime. A number gets marked only as a multiple $k p$ with $k \geq p \geq 2$ , so a marked number has a divisor $p$ with $1 < p < k p$ , hence is composite. A prime is therefore never marked.

Conversely suppose $m \leq N$ is composite. By the proposition Trial division stops at the square root, $m$ has a prime divisor $p \leq m \leq N$ ; take $p$ least such. Write $m = p k$ . Every prime factor of $k$ is at least $p$ by minimality of $p$ , and $k > 1$ , so $k \geq p$ and therefore $m = p k \geq p^{2}$ . Thus $m$ lies in the range $p^{2}, p^{2} + p, \dots$ that step 3 marks. It remains to check that the loop actually reaches $p$ : the loop runs while $p^{2} \leq N$ , and $p^{2} \leq m \leq N$ , so it does. Hence $m$ is marked.

Starting step 3 at $p^{2}$ rather than at $2 p$ loses nothing, precisely because any smaller multiple $k p$ with $k < p$ has a prime factor of $k$ below $p$ and was already marked in an earlier pass.∎

Figure 1.30. The sieve up to

60

, laid out ten to a row with

n

at position

(column, row)

. Crossing out multiples of

2

3

5

and

7

— the primes up to

60 \approx 7.7

— leaves the seventeen primes marked in the result tone. After the pass for

7

nothing new is removed, which is the loop's stopping condition made visible.

Example 1.31 (Sieving up to 30). Carry out the procedure Sieve of Eratosthenes for $N = 30$ and state how many sieving passes are needed.

Solution.

Since the loop runs while $p^{2} \leq 30$ , and $5^{2} = 25 \leq 30 < 36 = 6^{2}$ , only the primes $2, 3, 5$ are used as sieving primes: three passes.
Pass $p = 2$ marks $4, 6, 8, \dots, 30$ . Pass $p = 3$ marks $9, 15, 21, 27$ (the even multiples already went). Pass $p = 5$ marks $25$ alone.
Unmarked: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29$ — ten primes, so $π (30) = 10$ .

□

Example 1.32 (Certifying a prime by trial division). How many trial divisions does Trial division stops at the square root require to certify that $211$ is prime?

Solution.

$211 \approx 14.5$ , so we test the primes $p \leq 14$ : these are $2, 3, 5, 7, 11, 13$ .
None divides $211$ : it is odd, digit sum $4$ , does not end in $0$ or $5$ , and $211 = 7 \cdot 30 + 1 = 11 \cdot 19 + 2 = 13 \cdot 16 + 3$ .
Six trial divisions suffice, and $211$ is prime.

□

Exercises for §1.7 →

1.8A first look at factorisation

Before the theorem is stated in full, it pays to factor a few numbers by hand and watch what happens: repeatedly strip off the smallest prime factor. The lemma below is what guarantees the procedure never gets stuck, and the observation that the answer never depends on the order of stripping is the uniqueness claim in embryo.

Lemma 1.33 (The least divisor above 1 is prime). If $n > 1$ and $p$ is the smallest divisor of $n$ exceeding $1$ , then $p$ is prime and $p \leq n$ unless $n$ itself is prime.

Proof. Primality of $p$ is exactly the argument in Every integer above 1 has a prime divisor: a composite $p$ would have a divisor strictly between $1$ and $p$ which, by transitivity, also divides $n$ , contradicting minimality.

For the bound, suppose $n$ is not prime. Then $p < n$ , and $n / p$ is an integer greater than $1$ , so $n / p$ has a divisor above $1$ , hence $n / p \geq p$ by minimality of $p$ among divisors of $n$ . Multiplying by $p$ gives $n \geq p^{2}$ .∎

Example 1.34 (Factorising 180 by repeated stripping). Factor $180$ into primes by repeatedly dividing out the smallest prime factor, and check the result against $τ (180)$ .

Solution.

$180/2 = 90$ , $90/2 = 45$ ; $45$ is odd, so the powers of $2$ stop at $2^{2}$ .
$45/3 = 15$ , $15/3 = 5$ ; so $3^{2}$ divides and no more.
$5$ is prime, so $180 = 2^{2} \cdot 3^{2} \cdot 5$ .
Check: $τ (180) = 3 \cdot 3 \cdot 2 = 18$ , and $σ (180) = 7 \cdot 13 \cdot 6 = 546$ .

□

Example 1.35 (Order does not matter). Factor $600$ by stripping the largest prime factor first, and compare with the usual order.

Solution.

Largest first: $600/5 = 120$ , $120/5 = 24$ , then $24/3 = 8$ , then $8/2 = 4/1 \dots$ giving $2^{3}$ .
The multiset collected is ${5, 5, 3, 2, 2, 2}$ , so $600 = 2^{3} \cdot 3 \cdot 5^{2}$ .
Smallest first gives $600/2 = 300$ , $300/2 = 150$ , $150/2 = 75$ , $75/3 = 25$ , $25/5 = 5$ , $5/5 = 1$ — the same multiset in a different order. That this always happens is the content of Uniqueness of the prime factorisation.

□

Exercises for §1.8 →

1.9The division algorithm

Everything remaining in the chapter comes from one statement: you can always divide, provided you accept a remainder, and the quotient and remainder are uniquely determined. It is called an algorithm for historical reasons; as stated it is a theorem, and the proof of existence is the well-ordering argument again.

Theorem 1.36 (Division algorithm). Let $a$ and $b$ be integers with $b > 0$ . Then there exist unique integers $q$ and $r$ with

a = b q + r, 0 \leq r < b .

Proof. Existence. Consider the set

S = {a - bk : k \in Z, a - bk \geq 0} .

$S$ is nonempty: taking $k = - ∣ a ∣$ gives $a + b ∣ a ∣ \geq a + ∣ a ∣ \geq 0$ , since $b \geq 1$ . So $S$ is a nonempty set of non-negative integers and by well-ordering has a least element $r = a - b q$ for some integer $q$ . By construction $r \geq 0$ and $a = b q + r$ .

Suppose $r \geq b$ . Then $r - b = a - b (q + 1) \geq 0$ , so $r - b \in S$ ; but $r - b < r$ because $b > 0$ , contradicting minimality. Hence $r < b$ .

Uniqueness. Suppose $a = b q_{1} + r_{1} = b q_{2} + r_{2}$ with $0 \leq r_{1}, r_{2} < b$ . Subtracting,

b (q_{1} - q_{2}) = r_{2} - r_{1} .

The right-hand side satisfies $- b < r_{2} - r_{1} < b$ , so $∣ b (q_{1} - q_{2}) ∣ < b$ , which forces $∣ q_{1} - q_{2} ∣ < 1$ . An integer of absolute value below $1$ is zero, so $q_{1} = q_{2}$ , and then $r_{1} = r_{2}$ .∎

Corollary 1.37 (Division by a nonzero divisor of either sign). For integers $a$ and $b$ with $b \neq = 0$ there are unique integers $q, r$ with $a = b q + r$ and $0 \leq r < ∣ b ∣$ .

Proof. If $b > 0$ this is the theorem Division algorithm. If $b < 0$ apply that theorem to $a$ and $∣ b ∣ = - b$ , obtaining $a = ∣ b ∣ q^{'} + r$ with $0 \leq r < ∣ b ∣$ , and set $q = - q^{'}$ , so $a = b q + r$ . Uniqueness transfers the same way: any representation with divisor $b$ gives one with divisor $∣ b ∣$ by negating the quotient, and those are unique.∎

Intuition. On the number line, mark the multiples of $b$ . They cut $Z$ into blocks of length $b$ , and $a$ lies in exactly one block: $q$ names the block and $r$ names the position inside it. Existence is "the blocks cover everything"; uniqueness is "the blocks do not overlap".

Pitfall. The remainder is always taken non-negative, even when $a$ is negative. Dividing $- 17$ by $5$ gives $q = - 4$ and $r = 3$ , since $- 17 = 5 (- 4) + 3$ ; it does not give $q = - 3, r = - 2$ . Many programming languages disagree with the theorem here, returning $- 2$ for -17 % 5, so never trust a language's % to implement the division algorithm without checking.

Example 1.38 (Dividing with a negative dividend). Find the $q$ and $r$ guaranteed by Division algorithm for $a = - 100$ , $b = 7$ .

Solution.

We need the largest multiple of $7$ at or below $- 100$ . Since $7 \cdot (- 15) = - 105 \leq - 100$ and $7 \cdot (- 14) = - 98 > - 100$ , take $q = - 15$ .
Then $r = - 100 - 7 (- 15) = - 100 + 105 = 5$ , and indeed $0 \leq 5 < 7$ .
So $q = - 15$ , $r = 5$ .

□

Exercises for §1.9 →

1.10The Euclidean algorithm

Definition 1.39 (Greatest common divisor). For integers $a, b$ not both zero, the greatest common divisor $g cd (a, b)$ is the largest integer dividing both. It exists because the set of common divisors is nonempty (it contains $1$ ) and bounded above by $max (∣ a ∣, ∣ b ∣)$ , using part (2) of Elementary consequences of the definition. We set $g cd (0, 0) = 0$ , and call $a, b$ coprime when $g cd (a, b) = 1$ .

Definition 1.40 (Least common multiple). For nonzero integers $a, b$ , the least common multiple $lcm (a, b)$ is the smallest positive integer divisible by both. It exists by well-ordering, since $∣ ab ∣$ is one such multiple.

The naive way to compute $g cd (a, b)$ is to factor both. That is hopeless for large inputs — factoring is the hard problem — and completely unnecessary, because the following one-line identity lets us shrink the problem instead.

Lemma 1.41 (The gcd is invariant under division). If $a = b q + r$ then $g cd (a, b) = g cd (b, r)$ .

Proof. It suffices to show that the pairs $(a, b)$ and $(b, r)$ have the same set of common divisors; the greatest element of that set is then the same number.

If $d ∣ a$ and $d ∣ b$ , then $d ∣ a - b q = r$ by the theorem Linearity of divisibility, so $d$ is a common divisor of $b$ and $r$ . Conversely if $d ∣ b$ and $d ∣ r$ then $d ∣ b q + r = a$ , again by linearity, so $d$ is a common divisor of $a$ and $b$ .∎

Method 1.42 (Euclidean algorithm). To compute $g cd (a, b)$ with $a \geq b > 0$ :

Divide: $a = b q_{1} + r_{1}$ with $0 \leq r_{1} < b$ .
If $r_{1} = 0$ , stop and return $b$ .
Otherwise replace $(a, b)$ by $(b, r_{1})$ and go back to step 1.

Theorem 1.43 (Correctness and termination of the Euclidean algorithm). For $a \geq b > 0$ the procedure Euclidean algorithm halts after finitely many divisions, and the last nonzero remainder is $g cd (a, b)$ .

Proof. Termination. Write the successive remainders $r_{1} > r_{2} > \dots$ , where $r_{k + 1}$ is the remainder on dividing $r_{k - 1}$ by $r_{k}$ . The theorem Division algorithm guarantees $0 \leq r_{k + 1} < r_{k}$ , so the remainders form a strictly decreasing sequence of non-negative integers. No such sequence is infinite — by well-ordering, the set of remainders produced has a least element, and the step after it must yield remainder $0$ . Hence the algorithm halts.

Correctness. Set $r_{- 1} = a$ , $r_{0} = b$ , and let $r_{n}$ be the last nonzero remainder, so $r_{n + 1} = 0$ . Repeated application of the lemma The gcd is invariant under division gives

g cd (a, b) = g cd (r_{0}, r_{1}) = g cd (r_{1}, r_{2}) = \dots = g cd (r_{n - 1}, r_{n}) = g cd (r_{n}, 0) .

Finally $g cd (r_{n}, 0) = r_{n}$ , since every integer divides $0$ and the greatest divisor of $r_{n}$ is $r_{n}$ itself. So the returned value $r_{n}$ is $g cd (a, b)$ .∎

Figure 1.44. The Euclidean algorithm on

g cd (1071, 462)

as a descending staircase: each bar is a remainder, and each is strictly shorter than the one before. The run

1071, 462, 147, 21

ends when the next remainder is

0

, so the answer is the last nonzero bar,

21

. The strict decrease is exactly what the termination argument uses.

Example 1.45 (Euclid on 1071 and 462). Compute $g cd (1071, 462)$ and count the divisions used.

Solution.

$1071 = 2 \cdot 462 + 147$ .
$462 = 3 \cdot 147 + 21$ .
$147 = 7 \cdot 21 + 0$ .
The last nonzero remainder is $21$ , so $g cd (1071, 462) = 21$ , found in three divisions. Factoring would have required discovering $1071 = 3 \cdot 7 \cdot 51 = 3^{2} \cdot 7 \cdot 17$ and $462 = 2 \cdot 3 \cdot 7 \cdot 11$ — more work for the same answer.

□

Example 1.46 (A coprime pair). Compute $g cd (1234, 4321)$ .

Solution.

$4321 = 3 \cdot 1234 + 619$ .
$1234 = 1 \cdot 619 + 615$ .
$619 = 1 \cdot 615 + 4$ ; $615 = 153 \cdot 4 + 3$ ; $4 = 1 \cdot 3 + 1$ ; $3 = 3 \cdot 1 + 0$ .
Last nonzero remainder $1$ , so the two numbers are coprime.

□

Exercises for §1.10 →

1.11Bézout's identity and the extended algorithm

The Euclidean algorithm computes $g cd (a, b)$ ; run backwards it does more, expressing that gcd as an integer combination of $a$ and $b$ . This is the single most useful fact in elementary number theory, and it is what finally pays for Euclid's lemma and hence for uniqueness of factorisation.

Theorem 1.47 (Bézout's identity). Let $a, b$ be integers, not both zero. Then there exist integers $x, y$ with

a x + b y = g cd (a, b) .

Proof. We may assume $a \geq b > 0$ , since changing signs only changes the signs of $x, y$ , and the case $b = 0$ is $a \cdot 1 + 0 \cdot 0 = a = g cd (a, 0)$ .

Run the Euclidean algorithm, producing $r_{- 1} = a$ , $r_{0} = b$ and

r_{k - 1} = q_{k + 1} r_{k} + r_{k + 1}, k = 0, 1, \dots, n,

with $r_{n + 1} = 0$ and $r_{n} = g cd (a, b)$ by Correctness and termination of the Euclidean algorithm.

We prove by strong induction on $k$ that each $r_{k}$ is an integer combination of $a$ and $b$ . For $k = - 1$ and $k = 0$ this is clear: $r_{- 1} = a \cdot 1 + b \cdot 0$ and $r_{0} = a \cdot 0 + b \cdot 1$ . For the step, suppose $r_{k - 1} = a x_{k - 1} + b y_{k - 1}$ and $r_{k} = a x_{k} + b y_{k}$ . Rearranging the division equation,

r_{k + 1} = r_{k - 1} - q_{k + 1} r_{k} = a (x_{k - 1} - q_{k + 1} x_{k}) + b (y_{k - 1} - q_{k + 1} y_{k}),

which is again an integer combination. Taking $k = n$ gives the claim for $g cd (a, b) = r_{n}$ .∎

The induction in that proof is an algorithm: carry the pair $(x_{k}, y_{k})$ alongside each remainder and update it by the same recurrence, $x_{k + 1} = x_{k - 1} - q_{k + 1} x_{k}$ , and likewise for $y$ . That is the extended Euclidean algorithm, and it costs no more divisions than the plain one.

Corollary 1.48 (The gcd is the least positive combination). For $a, b$ not both zero, $g cd (a, b)$ is the smallest positive integer of the form $a x + b y$ with $x, y \in Z$ . Moreover an integer $c$ is of the form $a x + b y$ if and only if $g cd (a, b) ∣ c$ .

Proof. Let $g = g cd (a, b)$ and let $m$ be the least positive integer of the form $a x + b y$ , which exists by well-ordering since the set of such positive values is nonempty (it contains $∣ a ∣$ ). By the theorem Linearity of divisibility, $g ∣ a x + b y = m$ , so $g \leq m$ . By Bézout's identity, $g$ is itself of that form, so $m \leq g$ . Hence $m = g$ .

For the second claim, if $c = a x + b y$ then $g ∣ c$ by linearity. Conversely if $c = g t$ then writing $g = a x_{0} + b y_{0}$ gives $c = a (x_{0} t) + b (y_{0} t)$ .∎

Corollary 1.49 (Common divisors divide the gcd). If $d ∣ a$ and $d ∣ b$ then $d ∣ g cd (a, b)$ .

Proof. Write $g cd (a, b) = a x + b y$ by Bézout's identity and apply the theorem Linearity of divisibility.∎

This is a strengthening worth pausing on. The definition only says the gcd is the largest common divisor; the corollary says it is a multiple of every common divisor — greatest in the divisibility order, not merely in size. That is the property which generalises to rings where "largest" makes no sense.

Theorem 1.50 (Euclid's lemma). If $p$ is prime and $p ∣ ab$ , then $p ∣ a$ or $p ∣ b$ .

Proof. Suppose $p ∤ a$ . The only positive divisors of $p$ are $1$ and $p$ , so $g cd (p, a) \in {1, p}$ ; it cannot be $p$ , since $p ∣ a$ would follow. Hence $g cd (p, a) = 1$ , and by Bézout's identity there are integers $x, y$ with

p x + a y = 1.

Multiply through by $b$ :

p b x + ab y = b .

Now $p$ divides $p b x$ outright, and $p$ divides $ab y$ because $p ∣ ab$ by hypothesis. By the theorem Linearity of divisibility, $p$ divides their sum, which is $b$ .∎

Pitfall. Primality is essential. $6 ∣ 4 \cdot 9 = 36$ , yet $6 ∤ 4$ and $6 ∤ 9$ . The step that fails for a composite $m$ is $g cd (m, a) \in {1, m}$ : for $m = 6, a = 4$ the gcd is $2$ , neither of the two.

Corollary 1.51 (Euclid's lemma for several factors). If a prime $p$ divides a product $a_{1} a_{2} \dots a_{k}$ , then $p ∣ a_{i}$ for some $i$ .

Proof. Induct on $k$ . The case $k = 1$ is trivial. For $k > 1$ write the product as $a_{1} \cdot (a_{2} \dots a_{k})$ ; by Euclid's lemma either $p ∣ a_{1}$ , and we are done, or $p$ divides $a_{2} \dots a_{k}$ , to which the inductive hypothesis applies.∎

Example 1.52 (Extended Euclid on 240 and 46). Find integers $x, y$ with $240 x + 46 y = g cd (240, 46)$ .

Solution.

Forward: $240 = 5 \cdot 46 + 10$ ; $46 = 4 \cdot 10 + 6$ ; $10 = 1 \cdot 6 + 4$ ; $6 = 1 \cdot 4 + 2$ ; $4 = 2 \cdot 2 + 0$ . So $g cd = 2$ .
Back-substitute: $2 = 6 - 1 \cdot 4 = 6 - (10 - 6) = 2 \cdot 6 - 10$ .
Continue: $= 2 (46 - 4 \cdot 10) - 10 = 2 \cdot 46 - 9 \cdot 10 = 2 \cdot 46 - 9 (240 - 5 \cdot 46) = 47 \cdot 46 - 9 \cdot 240$ .
So $x = - 9$ , $y = 47$ , and a check gives $- 2160 + 2162 = 2$ .

□

Example 1.53 (Solving a linear Diophantine equation). Does $18 x + 30 y = 24$ have an integer solution? Find one if it does.

Solution.

By The gcd is the least positive combination, a solution exists exactly when $g cd (18, 30) ∣ 24$ . Here $g cd (18, 30) = 6$ and $6 ∣ 24$ , so yes.
Bézout for the gcd: $6 = 18 \cdot 2 + 30 \cdot (- 1)$ .
Scale by $24/6 = 4$ : $24 = 18 \cdot 8 + 30 \cdot (- 4)$ , so $(x, y) = (8, - 4)$ .

□

Exercises for §1.11 →

1.12The Fundamental Theorem of Arithmetic: statement

Theorem 1.54 (Fundamental Theorem of Arithmetic). Every integer $n > 1$ can be written as a product of primes,

n = p_{1} p_{2} \dots p_{k},

and this representation is unique up to the order of the factors. Collecting equal primes, every $n > 1$ has a unique canonical factorisation

n = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{r}^{a_{r}}, p_{1} < p_{2} < \dots < p_{r}, a_{i} \geq 1.

The theorem makes two independent claims, and they are proved below in two separate sections because they need entirely different tools. Existence — that a factorisation exists at all — is a induction on size and uses nothing about primes beyond the definition. Uniqueness — that there is only one — is the deep half, and it needs Euclid's lemma, hence Bézout, hence the division algorithm.

Remark. The temptation is to think uniqueness is obvious. It is not, and the standard way to see this is to look at a number system where it fails. In the set $E = {2, 4, 6, 8, \dots}$ of even numbers, closed under multiplication, call an element "irreducible" if it is not a product of two elements of $E$ . Then $2, 6, 10, 30$ are all irreducible in $E$ , and

60 = 2 \cdot 30 = 6 \cdot 10

gives two genuinely different factorisations. Nothing in the existence argument is violated; what fails is Euclid's lemma, since $6 ∣ 2 \cdot 30$ but $6$ divides neither $2$ nor $30$ within $E$ . Uniqueness is a theorem about $Z$ , not a law of thought.

Note. Adopting the convention that the empty product equals $1$ lets the theorem include $n = 1$ , factored as the product of no primes. This also makes the statement " $τ (1) = 1$ " consistent with the divisor-counting formula read as an empty product.

Exercises for §1.12 →

1.13Existence of a factorisation

Theorem 1.55 (Existence of a prime factorisation). Every integer $n > 1$ is a product of (one or more) primes.

Proof. Strong induction on $n$ . Suppose the claim holds for every integer $m$ with $1 < m < n$ .

If $n$ is prime, it is a product of one prime and there is nothing to prove.

Otherwise $n$ is composite, so $n = ab$ with $1 < a < n$ and $1 < b < n$ . Both $a$ and $b$ fall in the range covered by the inductive hypothesis, so $a = p_{1} \dots p_{s}$ and $b = q_{1} \dots q_{t}$ for primes $p_{i}, q_{j}$ . Concatenating,

n = p_{1} \dots p_{s} q_{1} \dots q_{t},

a product of primes. By strong induction the claim holds for every $n > 1$ .∎

Remark. The same argument can be run as a minimal-counterexample proof, which some find clearer: if some integer above $1$ had no prime factorisation, well-ordering would give a least such $n$ ; $n$ could not be prime, so $n = ab$ with both factors smaller and above $1$ , and both would then factor by minimality, giving a factorisation of $n$ after all. Strong induction and least-counterexample are the same argument in two dresses.

Notice what the existence proof did not use: nothing about Bézout, nothing about Euclid's lemma, and no property of primes except the definition of composite. That is why it also works in the even-numbers system of the remark above, where uniqueness fails — existence is cheap.

Example 1.56 (Existence made explicit). Follow the existence proof on $n = 1386$ , recording the splits it performs.

Solution.

$1386$ is composite: $1386 = 2 \cdot 693$ .
$693$ is composite: $693 = 3 \cdot 231$ , and $231 = 3 \cdot 77$ , and $77 = 7 \cdot 11$ .
Every leaf of this splitting tree is prime, so $1386 = 2 \cdot 3 \cdot 3 \cdot 7 \cdot 11 = 2 \cdot 3^{2} \cdot 7 \cdot 11$ .
Each split strictly decreased the numbers involved, which is exactly why the recursion terminates.

□

Exercises for §1.13 →

1.14Uniqueness of the factorisation

Theorem 1.57 (Uniqueness of the prime factorisation). If

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

with all $p_{i}$ and $q_{j}$ prime, then $s = t$ and the list $q_{1}, \dots, q_{t}$ is a rearrangement of $p_{1}, \dots, p_{s}$ .

Proof. Induct on $s$ .

Base case $s = 1$ . Then $p_{1} = q_{1} \dots q_{t}$ . If $t \geq 2$ the right-hand side has the divisor $q_{1}$ with $1 < q_{1} < p_{1}$ , contradicting primality of $p_{1}$ . So $t = 1$ and $p_{1} = q_{1}$ .

Inductive step. Let $s \geq 2$ and assume the statement for products of $s - 1$ primes. The prime $p_{1}$ divides the left side, hence divides $q_{1} \dots q_{t}$ ; by the corollary Euclid's lemma for several factors, $p_{1} ∣ q_{j}$ for some $j$ . Reordering the $q$ 's, take $j = 1$ . Since $q_{1}$ is prime its only divisors above $1$ are $1$ and $q_{1}$ , and $p_{1} > 1$ , so $p_{1} = q_{1}$ .

Cancel this common factor — legitimate because $p_{1} \neq = 0$ and $Z$ has no zero divisors — to get

p_{2} \dots p_{s} = q_{2} \dots q_{t} .

The left side is a product of $s - 1$ primes, so the inductive hypothesis gives $s - 1 = t - 1$ and a matching of the remaining factors. Restoring $p_{1} = q_{1}$ completes the matching of the full lists.∎

Intuition. The whole weight sits on the single sentence " $p_{1}$ divides the product, so it divides one of the factors". Without Euclid's lemma a prime could sneak in as a divisor of a product while dividing no individual factor, and the two factorisations would never be forced to align — which is precisely what happens in the even-numbers system, where $6$ divides $2 \cdot 30$ but neither factor.

Example 1.58 (Uniqueness as a constraint). Given that $n = 2^{a} 3^{b}$ and $n^{2}$ has $45$ divisors, find $n$ .

Solution.

$n^{2} = 2^{2 a} 3^{2 b}$ , so by The divisor-counting formula, $τ (n^{2}) = (2 a + 1) (2 b + 1) = 45$ .
Both factors are odd; the factorisations of $45$ into two odd factors are $45 \cdot 1$ , $15 \cdot 3$ , $9 \cdot 5$ and their reversals. These give $(a, b) \in {(22, 0), (0, 22), (7, 1), (1, 7), (4, 2), (2, 4)}$ .
Requiring both exponents positive and $a \geq b$ leaves $(7, 1)$ and $(4, 2)$ , that is $n = 384$ or $n = 144$ . Uniqueness of factorisation is what makes the exponent bookkeeping in step 1 valid at all.

□

Exercises for §1.14 →

1.15gcd and lcm from the factorisations

With uniqueness in hand, both the gcd and the lcm can be read off the exponents. This is the conceptually clean description; the Euclidean algorithm remains the one you actually compute with, because it does not require factoring.

Theorem 1.59 (gcd and lcm by exponents). Let $a, b$ be positive integers and write them over a common set of primes,

a = i \prod p_{i}^{a_{i}}, b = i \prod p_{i}^{b_{i}}, a_{i}, b_{i} \geq 0.

Then

g cd (a, b) = i \prod p_{i}^{m i n (a_{i}, b_{i})}, lcm (a, b) = i \prod p_{i}^{m a x (a_{i}, b_{i})} .

Proof. As in the proof of The divisor-counting formula, uniqueness of factorisation says $d = \prod p_{i}^{e_{i}}$ divides $a$ if and only if $e_{i} \leq a_{i}$ for every $i$ . So $d$ is a common divisor of $a$ and $b$ exactly when $e_{i} \leq a_{i}$ and $e_{i} \leq b_{i}$ for all $i$ , that is $e_{i} \leq min (a_{i}, b_{i})$ . The largest such $d$ takes $e_{i} = min (a_{i}, b_{i})$ throughout, which is the stated formula.

The multiple case is dual: $m = \prod p_{i}^{f_{i}}$ is divisible by $a$ exactly when $f_{i} \geq a_{i}$ , so a common multiple needs $f_{i} \geq max (a_{i}, b_{i})$ , and the smallest one takes equality.∎

Theorem 1.60 (Product of gcd and lcm). For positive integers $a$ and $b$ ,

g cd (a, b) \cdot lcm (a, b) = ab .

Proof. Fix a prime $p_{i}$ and compare exponents on both sides. On the left, by the theorem gcd and lcm by exponents, the exponent is $min (a_{i}, b_{i}) + max (a_{i}, b_{i})$ . On the right it is $a_{i} + b_{i}$ . For any two numbers, the smaller plus the larger is the sum of the two, so $min (a_{i}, b_{i}) + max (a_{i}, b_{i}) = a_{i} + b_{i}$ . The two sides have identical exponents at every prime, and by uniqueness of factorisation two positive integers with the same canonical factorisation are equal.∎

Corollary 1.61 (lcm from the Euclidean algorithm). For positive $a, b$ , $lcm (a, b) = ab / g cd (a, b)$ , so the lcm is computable without factoring.

Proof. Divide the identity of Product of gcd and lcm by $g cd (a, b)$ , which is positive and hence nonzero.∎

Pitfall. The identity $g cd \cdot lcm = ab$ is a statement about two numbers only. For three it fails: $g cd (2, 3, 4) = 1$ and $lcm (2, 3, 4) = 12$ , but $1 \cdot 12 \neq = 24$ .

Example 1.62 (gcd and lcm two ways). Compute $g cd (84, 360)$ and $lcm (84, 360)$ , first from factorisations and then check with the Euclidean algorithm.

Solution.

$84 = 2^{2} \cdot 3 \cdot 7$ and $360 = 2^{3} \cdot 3^{2} \cdot 5$ .
Exponentwise minima: $2^{2} \cdot 3^{1} \cdot 5^{0} \cdot 7^{0} = 12$ . Maxima: $2^{3} \cdot 3^{2} \cdot 5 \cdot 7 = 2520$ .
Euclid: $360 = 4 \cdot 84 + 24$ , $84 = 3 \cdot 24 + 12$ , $24 = 2 \cdot 12 + 0$ , giving $g cd = 12$ as expected.
Check the product law: $12 \cdot 2520 = 30240 = 84 \cdot 360$ .

□

Example 1.63 (Recovering a number from gcd and lcm). Two positive integers have gcd $6$ and lcm $180$ , and one of them is $36$ . Find the other.

Solution.

By Product of gcd and lcm, the product of the two numbers is $6 \cdot 180 = 1080$ .
Dividing by the known one: $1080/36 = 30$ .
Check: $g cd (36, 30) = 6$ and $lcm (36, 30) = 180$ . The other number is $30$ .

□

Exercises for §1.15 →

1.16How fast is Euclid? Lamé's theorem

The Euclidean algorithm terminates; the practical question is how quickly. The answer, found by Lamé in 1844 and often called the first theorem in computational complexity, is that the worst inputs are consecutive Fibonacci numbers, and that the step count is linear in the number of digits.

Definition 1.64 (Fibonacci numbers). The Fibonacci numbers are defined by $F_{1} = F_{2} = 1$ and $F_{k} = F_{k - 1} + F_{k - 2}$ for $k \geq 3$ , giving $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \dots$

Lemma 1.65 (Fibonacci pairs are the slowest). If the Euclidean algorithm applied to $a > b > 0$ performs exactly $n$ divisions, then $a \geq F_{n + 2}$ and $b \geq F_{n + 1}$ .

Proof. Induct on $n$ . For $n = 1$ the algorithm halts at once, so $b \geq 1 = F_{2}$ and $a > b$ gives $a \geq 2 = F_{3}$ .

Assume the statement for $n - 1$ and suppose the run on $(a, b)$ takes $n$ divisions, the first being $a = q_{1} b + r_{1}$ with $0 < r_{1} < b$ . The remaining run is on the pair $(b, r_{1})$ and takes $n - 1$ divisions, so by the inductive hypothesis $b \geq F_{n + 1}$ and $r_{1} \geq F_{n}$ . Since $r_{1} < b$ and $q_{1} \geq 1$ ,

a = q_{1} b + r_{1} \geq b + r_{1} \geq F_{n + 1} + F_{n} = F_{n + 2} .

∎

Theorem 1.66 (Lamé's theorem). If $a > b > 0$ and the Euclidean algorithm takes $n$ divisions to compute $g cd (a, b)$ , then $n$ is at most five times the number of decimal digits of $b$ . The bound is attained by consecutive Fibonacci numbers.

Proof. By the lemma Fibonacci pairs are the slowest, $b \geq F_{n + 1}$ . A standard induction shows $F_{k + 1} > φ^{k - 1}$ for $k \geq 2$ , where $φ = (1 + 5) /2$ : it holds at $k = 2, 3$ , and $F_{k + 1} = F_{k} + F_{k - 1} > φ^{k - 2} + φ^{k - 3} = φ^{k - 3} (φ + 1) = φ^{k - 3} φ^{2} = φ^{k - 1}$ , using $φ^{2} = φ + 1$ .

Hence $b > φ^{n - 1}$ , so taking base- $10$ logarithms, $lo g_{10} b > (n - 1) lo g_{10} φ$ . Now $lo g_{10} φ = 0.20898 \dots > 1/5$ , so

n - 1 < \frac{lo g _{10} b}{lo g _{10} φ} < 5 lo g_{10} b .

If $b$ has $D$ decimal digits then $lo g_{10} b < D$ , so $n < 5 D + 1$ , that is $n \leq 5 D$ .

For attainment, run the algorithm on $(F_{k + 1}, F_{k})$ : since $F_{k + 1} = 1 \cdot F_{k} + F_{k - 1}$ with $0 \leq F_{k - 1} < F_{k}$ , every quotient is $1$ and the remainder sequence is the Fibonacci sequence run backwards, so the number of divisions is as large as the lemma permits.∎

Intuition. Every quotient of $1$ is a wasted step: the pair barely shrinks. The Fibonacci recurrence is the extreme case where every quotient is $1$ , so the algorithm crawls. Any quotient of $2$ or more at least halves the larger argument, which is why typical inputs finish far faster than the bound — on random inputs the expected number of divisions is about $0.843 ln b$ .

Example 1.67 (The worst case at five digits). How many divisions does the Euclidean algorithm use on $g cd (89, 55)$ , and how does that compare with Lamé's bound?

Solution.

$89 = 1 \cdot 55 + 34$ ; $55 = 1 \cdot 34 + 21$ ; $34 = 1 \cdot 21 + 13$ ; $21 = 1 \cdot 13 + 8$ ; $13 = 1 \cdot 8 + 5$ ; $8 = 1 \cdot 5 + 3$ ; $5 = 1 \cdot 3 + 2$ ; $3 = 1 \cdot 2 + 1$ ; $2 = 2 \cdot 1 + 0$ .
That is nine divisions, every quotient $1$ until the last — the Fibonacci signature.
$b = 55$ has $D = 2$ digits, so Lamé allows up to $5 \cdot 2 = 10$ divisions. Nine is just under the bound, showing the bound is tight to within one step here.

□

Example 1.68 (Bounding work before doing it). Before computing, bound the number of divisions the Euclidean algorithm can need for $g cd (1000003, 987654)$ .

Solution.

The smaller argument $b = 987654$ has $D = 6$ decimal digits.
By Lamé's theorem the algorithm uses at most $5 \cdot 6 = 30$ divisions.
In fact it uses far fewer; the bound is a worst-case guarantee, and worst cases are Fibonacci-shaped, which $987654$ is not.

□

Summary. The chapter's logical spine, in order of dependence: well-ordering gives the division algorithm; iterating division gives the Euclidean algorithm, which terminates because remainders strictly decrease; running it backwards gives Bézout's identity; Bézout gives Euclid's lemma; Euclid's lemma gives uniqueness in the Fundamental Theorem, whose existence half is a separate and much easier strong induction. On top of the Fundamental Theorem sit the exponent formulas for $τ$ , $σ$ , $g cd$ and $lcm$ ; on top of the Euclidean algorithm sits Lamé's bound.

Exercises for §1.16 →

Common Mistakes

Confusing $d ∣ n$ with $d / n$ or $n / d$ . The bar is a relation and produces a truth value; the slash is an operation and produces a number. " $3 ∣ 12 = 4$ " is not a sentence.
Getting the direction of the bar backwards. $3 ∣ 12$ says three divides twelve. Reading it as "3 divided by 12" reverses every subsequent inference.
Mishandling zero. Every integer divides $0$ ; $0$ divides only $0$ . In particular $g cd (0, n) = ∣ n ∣$ , and the bound $∣ a ∣ \leq ∣ b ∣$ from Elementary consequences of the definition needs $b \neq = 0$ .
Calling $1$ prime. It is a unit, not a prime, and admitting it would destroy uniqueness in the Fundamental Theorem of Arithmetic.
Claiming Euclid's proof produces a prime. $p_{1} \dots p_{r} + 1$ need not be prime — $30031 = 59 \cdot 509$ — only that it has a prime factor outside the list.
Trial dividing past $n$ . By Trial division stops at the square root the search may stop there; going further is wasted work, and stopping short of it is an error. Test $n$ itself when it is an integer.
Assuming a negative remainder is allowed. The division algorithm demands $0 \leq r < ∣ b ∣$ , so $- 17 = 5 (- 4) + 3$ , not $5 (- 3) - 2$ . A language's % operator may disagree.
Using Euclid's lemma with a composite modulus. $6 ∣ 4 \cdot 9$ but $6$ divides neither factor. The lemma is a statement about primes.
Proving only existence and calling it the Fundamental Theorem. The existence half is a three-line induction; uniqueness is the content, and it needs Euclid's lemma.
Extending $g cd \cdot lcm = ab$ to three or more numbers. It is false: $g cd (2, 3, 4) lcm (2, 3, 4) = 12 \neq = 24$ .
Reversing the Bézout coefficients. In $240 (- 9) + 46 (47) = 2$ the coefficient $- 9$ belongs to $240$ . Always substitute back and check the arithmetic; a sign slip here is the most common error in the extended algorithm.
Reading Lamé's bound as a count rather than a ceiling. Five times the digit count is the worst case, achieved only by Fibonacci-like inputs; typical pairs finish in a fraction of that.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

Practice this chapter