# Lecture 8. Number theory

## Overview

The integers are the oldest object of mathematics and the natural place to
*practise* the proof methods of Lecture 7. Everything here rests on a single
relation — **divisibility** — yet it grows into primes, unique factorization,
the Euclidean algorithm, and modular arithmetic, which in turn underpin hashing,
error-correcting codes, and public-key cryptography. Two threads from earlier
lectures reappear: **congruence modulo $n$** is an equivalence relation
(Lecture 3), and each theorem below is established by a **direct proof**, a proof
by **contradiction**, or **induction** (Lecture 7).

By the end of this chapter you should be able to:

- use divisibility and the **division algorithm**, and reason about parity;
- test primality by trial division to $\sqrt{n}$ and prove the **infinitude of primes**;
- compute $\gcd$ with the **Euclidean algorithm** and recover Bézout coefficients with its **extended** form;
- state and use the **Fundamental Theorem of Arithmetic** and the identity $\gcd\cdot\operatorname{lcm}=ab$;
- compute with **congruences**, find **modular inverses**, and solve **linear congruences**;
- apply **Euler's** and **Fermat's** theorems and the **totient** $\varphi(n)$, and combine congruences with the **Chinese Remainder Theorem**;
- use the **pigeonhole principle** to force repetition.

## 8.1 Divisibility and parity

**Definition (divisibility).** For integers $a$ and $b$, we say $b$ **divides**
$a$, written $b \mid a$, if $a = b\,k$ for some integer $k$. Then $b$ is a
**divisor** of $a$ and $a$ a **multiple** of $b$. An integer is **even** if
$2 \mid n$ and **odd** otherwise.

**Proposition 8.1 (basic laws).** For all integers $a,b,c$:

1. $a \mid a$; if $a \mid b$ and $b \mid c$ then $a \mid c$ (transitivity);
2. if $d \mid a$ and $d \mid b$ then $d \mid (ax + by)$ for all integers $x,y$.

*Proof.* (1) $a = a\cdot 1$. If $b = a k$ and $c = b\ell$ then $c = a(k\ell)$.
(2) Write $a = d m$, $b = d n$; then $ax + by = d(mx + ny)$. $\blacksquare$

Part (2) — every **linear combination** of $a$ and $b$ is divisible by any common
divisor — is used constantly below.

## 8.2 The division algorithm

**Theorem 8.2 (division algorithm).** For integers $a$ and $b > 0$ there exist
**unique** integers $q$ (quotient) and $r$ (remainder) with

$$a = b q + r, \qquad 0 \le r < b.$$

*Proof (existence).* Consider $S = \{a - bq : q \in \mathbb{Z},\ a - bq \ge 0\}$.
$S$ is nonempty and bounded below by $0$, so by well-ordering it has a least
element $r = a - bq$. If $r \ge b$ then $a - b(q+1) = r - b \ge 0$ is a smaller
member of $S$, a contradiction; hence $0 \le r < b$. Uniqueness: if
$a = bq_1 + r_1 = bq_2 + r_2$ then $b(q_1 - q_2) = r_2 - r_1$, so $b \mid (r_2 -
r_1)$; but $|r_2 - r_1| < b$, forcing $r_1 = r_2$ and then $q_1 = q_2$.
$\blacksquare$

We write $r = a \bmod b$. Parity is the case $b = 2$.

## 8.3 Primes and the infinitude of primes

**Definition (prime).** An integer $p > 1$ is **prime** if its only positive
divisors are $1$ and $p$; otherwise it is **composite**.

![Sieve of Eratosthenes: primes up to 31 highlighted](img/l08_sieve.png)

**Lemma 8.3.** Every integer $n > 1$ has a prime divisor.

*Proof (strong induction / least criminal).* If $n$ is prime, done. Otherwise
$n = ab$ with $1 < a < n$; by the induction hypothesis $a$ has a prime divisor
$p$, and $p \mid a \mid n$. $\blacksquare$

**Theorem 8.4 (Euclid).** There are infinitely many primes.

*Proof (by contradiction).* Suppose the primes are exactly $p_1, \dots, p_k$.
Let $N = p_1 p_2 \cdots p_k + 1$. Since $N > 1$, by Lemma 8.3 it has a prime
divisor $p$. That $p$ equals some $p_i$; but $p_i \mid (N - 1)$, so if $p_i \mid
N$ then $p_i \mid \bigl(N - (N-1)\bigr) = 1$ — impossible. Hence $p$ is a prime
outside the list, a contradiction. $\blacksquare$

**Proposition 8.5 (primality by trial division).** If $n > 1$ has no prime
divisor $p \le \sqrt{n}$, then $n$ is prime.

*Proof.* If $n = ab$ with $1 < a \le b$ then $a \le \sqrt{n}$, and $a$ has a prime
divisor $\le a \le \sqrt{n}$. Contrapositive gives the claim. $\blacksquare$

This proposition is exactly the $O(\sqrt{n})$ test implemented in Lab 5.

## 8.4 The greatest common divisor and Euclid's algorithm

**Definition (gcd).** The **greatest common divisor** $\gcd(a,b)$ of integers
(not both $0$) is the largest integer dividing both. Integers with
$\gcd(a,b) = 1$ are **coprime**.

**Lemma 8.6 (the key identity).** For $b \ne 0$,
$\gcd(a,b) = \gcd(b,\ a \bmod b)$.

*Proof.* Write $a = bq + r$ with $r = a \bmod b$. If $d \mid a$ and $d \mid b$
then $d \mid (a - bq) = r$; conversely if $d \mid b$ and $d \mid r$ then
$d \mid (bq + r) = a$. So $\{a,b\}$ and $\{b,r\}$ have **the same** common
divisors, hence the same greatest one. $\blacksquare$

Iterating Lemma 8.6 until the remainder is $0$ is the **Euclidean algorithm**;
it terminates because the remainders strictly decrease, and the last nonzero
remainder is $\gcd(a,b)$. For example
$\gcd(48,18) = \gcd(18,12) = \gcd(12,6) = \gcd(6,0) = 6$. The number of steps is
$O(\log \min(a,b))$.

![Euclidean algorithm: gcd(48, 18) = 6 in three steps](img/l08_euclidean.png)

**Theorem 8.7 (Bézout).** There exist integers $x,y$ with $\gcd(a,b) = ax + by$.

*Proof.* Run the Euclidean algorithm and back-substitute; each remainder
$r_i = r_{i-2} - q\, r_{i-1}$ is a linear combination of $a$ and $b$, so the last
nonzero one — the gcd — is too. (This is the *extended* Euclidean algorithm.)
$\blacksquare$

*Worked example (extended Euclidean algorithm).* Take $a = 30$, $b = 7$. Forward:

$$30 = 4\cdot 7 + 2, \qquad 7 = 3\cdot 2 + 1, \qquad 2 = 2\cdot 1 + 0,$$

so $\gcd(30,7) = 1$. Back-substitute from the last nonzero remainder:

$$1 = 7 - 3\cdot 2 = 7 - 3\,(30 - 4\cdot 7) = 13\cdot 7 - 3\cdot 30 .$$

Thus $(x,y) = (-3, 13)$ solves $30x + 7y = 1$; read modulo $30$ it gives the
inverse $7^{-1} \equiv 13 \pmod{30}$ (used in §8.9).

## 8.5 The least common multiple

**Definition (lcm).** $\operatorname{lcm}(a,b)$ is the smallest positive common
multiple of $a$ and $b$.

**Theorem 8.8.** For positive $a,b$, $\ \gcd(a,b)\cdot\operatorname{lcm}(a,b) =
a b.$

*Proof.* Write the prime factorizations $a = \prod_p p^{\,a_p}$ and
$b = \prod_p p^{\,b_p}$ (§8.6). For each prime $p$, the exponent of $p$ in
$\gcd(a,b)$ is $\min(a_p, b_p)$ and in $\operatorname{lcm}(a,b)$ is
$\max(a_p, b_p)$. Since $\min(a_p,b_p) + \max(a_p,b_p) = a_p + b_p$ for every $p$,
multiplying over all primes gives
$\gcd(a,b)\cdot\operatorname{lcm}(a,b) = \prod_p p^{\,a_p + b_p} = ab$.
$\blacksquare$

Hence $\operatorname{lcm}(a,b) = ab/\gcd(a,b)$; e.g. $\operatorname{lcm}(15,20) =
300/5 = 60$.

## 8.6 The Fundamental Theorem of Arithmetic

**Lemma 8.9 (Euclid's lemma).** If $p$ is prime and $p \mid ab$, then $p \mid a$
or $p \mid b$.

*Proof.* If $p \nmid a$ then $\gcd(p,a) = 1$, so by Bézout $1 = px + ay$.
Multiply by $b$: $b = pbx + aby$. Now $p \mid pbx$ and $p \mid ab \mid aby$, so
$p \mid b$. $\blacksquare$

**Theorem 8.10 (Fundamental Theorem of Arithmetic).** Every integer $n > 1$
factors into primes, and the factorization is **unique** up to order:

$$n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}.$$

*Proof.* **Existence** is Lemma 8.3 applied repeatedly (strong induction).
**Uniqueness**: given two factorizations, a prime on the left divides the right
side, so by Euclid's lemma it equals some prime there; cancel it and induct.
$\blacksquare$

For example $56 = 2^3 \cdot 7$ (the format produced in Lab 5).

![Factor tree: 56 = 2 times 2 times 2 times 7](img/l08_factor_tree.png)

## 8.7 Modular arithmetic and congruences

**Definition (congruence).** For $n > 0$, $a$ is **congruent** to $b$ **modulo**
$n$, written $a \equiv b \pmod{n}$, if $n \mid (a - b)$.

**Theorem 8.11.** Congruence modulo $n$ is an **equivalence relation** on
$\mathbb{Z}$.

*Proof.* *Reflexive:* $n \mid 0 = a - a$. *Symmetric:* $n \mid (a-b) \Rightarrow
n \mid (b-a)$. *Transitive:* if $n \mid (a-b)$ and $n \mid (b-c)$ then, by
Proposition 8.1(2), $n \mid \bigl((a-b)+(b-c)\bigr) = a - c$. $\blacksquare$

This is the promised callback to Lecture 3: the equivalence classes are the $n$
**residue classes** $[0], [1], \dots, [n-1]$, and they **partition**
$\mathbb{Z}$. Congruences may be added and multiplied: if $a \equiv a'$ and
$b \equiv b' \pmod n$, then $a + b \equiv a' + b'$ and $ab \equiv a'b' \pmod n$ —
which is why one can reduce mod $n$ at any point in a calculation.

## 8.8 Euler's totient function

**Definition (totient).** $\varphi(n)$ is the number of integers in
$\{1, \dots, n\}$ that are **coprime** to $n$.

For a prime power, $\varphi(p^k) = p^k - p^{k-1} = p^k\!\left(1 - \tfrac1p\right)$
(the multiples of $p$ are the only non-coprime residues). Moreover $\varphi$ is
**multiplicative** on coprime arguments — $\varphi(mn) = \varphi(m)\varphi(n)$
whenever $\gcd(m,n) = 1$ — because the Chinese Remainder Theorem (§8.9) matches
the residues modulo $mn$ bijectively with pairs of residues modulo $m$ and
modulo $n$, and such a pair is coprime to $mn$ exactly when both coordinates are
coprime to their moduli. Factoring $n = p_1^{e_1}\cdots p_k^{e_k}$ therefore gives

$$\varphi(n) = n \prod_{i=1}^{k}\left(1 - \frac{1}{p_i}\right).$$

For example $\varphi(12) = 12\left(1-\tfrac12\right)\left(1-\tfrac13\right) = 4$,
counting $\{1,5,7,11\}$ — the value computed in Lab 5.

![Euler's totient phi(12) = 4: coprime residues 1, 5, 7, 11](img/l08_totient.png)

## 8.9 Modular inverses, and the theorems of Euler and Fermat

**Modular inverse.** An **inverse** of $a$ modulo $n$ is an integer $a^{-1}$ with
$a\,a^{-1}\equiv 1\pmod n$. It exists **iff** $\gcd(a,n)=1$: Bézout (Theorem 8.7)
gives $ax+ny=1$, and reducing mod $n$ leaves $ax\equiv 1$, so $a^{-1}\equiv x$ — and
the **extended** Euclidean algorithm computes $x$. *Example:* $3\cdot 5=15\equiv 1
\pmod 7$, so $3^{-1}\equiv 5\pmod 7$. This is also why a common factor may be
cancelled from a congruence **only** when it is coprime to the modulus:
$2\cdot 3\equiv 2\cdot 0\pmod 6$, yet $3\not\equiv 0\pmod 6$.

**Theorem 8.12 (Euler).** If $\gcd(a,n)=1$ then $a^{\varphi(n)}\equiv 1\pmod n$.

*Proof.* Let $r_1,\dots,r_{\varphi(n)}$ be the residues coprime to $n$. Multiplication
by $a$ permutes this set modulo $n$ (it is a bijection, with inverse "multiply by
$a^{-1}$"), so $\prod_i (a r_i)\equiv \prod_i r_i \pmod n$, i.e.
$a^{\varphi(n)}\prod_i r_i\equiv \prod_i r_i$. Each $r_i$ is invertible, so the product
$\prod_i r_i$ cancels, leaving $a^{\varphi(n)}\equiv 1$. $\blacksquare$

**Corollary 8.13 (Fermat's little theorem).** If $p$ is prime and $p\nmid a$, then
$a^{p-1}\equiv 1\pmod p$ (since $\varphi(p)=p-1$); equivalently $a^{p}\equiv a\pmod p$
for **every** integer $a$.

These are the engine of public-key cryptography: in **RSA** a message is encrypted by
raising it to a public exponent $e$ modulo $n=pq$, and decrypted by raising the result
to $d\equiv e^{-1}\pmod{\varphi(n)}$ — a modular inverse — with Euler's theorem
guaranteeing the round trip recovers the original.

**Linear congruences.** The congruence $ax\equiv b\pmod n$ is solvable **iff**
$\gcd(a,n)\mid b$; when $\gcd(a,n)=1$ the solution is unique modulo $n$, namely
$x\equiv a^{-1}b$. For example $3x\equiv 2\pmod 7$ gives $x\equiv 5\cdot 2\equiv 3$.

**Fast modular exponentiation.** To evaluate $a^{e}\bmod n$ cheaply, use
**square-and-multiply**: scan the bits of $e$, squaring the running value at each step
and multiplying in $a$ on every $1$-bit — $O(\log e)$ multiplications instead of $e$.
This is what makes RSA practical for large exponents.

**Chinese Remainder Theorem (CRT).** If $n_1,\dots,n_k$ are **pairwise coprime** with
product $N=n_1\cdots n_k$, the system $x\equiv a_i\pmod{n_i}$ $(i=1,\dots,k)$ has a
**unique** solution modulo $N$:
$$x\equiv \sum_{i=1}^{k} a_i\,M_i\,M_i^{-1}\pmod N,\qquad M_i=\tfrac{N}{n_i},\quad M_iM_i^{-1}\equiv 1\pmod{n_i}.$$
*(Each $M_i$ is coprime to $n_i$, so $M_i^{-1}$ exists; the $i$-th term is $\equiv a_i$
modulo $n_i$ and $\equiv 0$ modulo every other $n_j$, and two solutions differ by a
common multiple of all the $n_i$, hence of $N$.)* Example: $x\equiv 2\ (\mathrm{mod}\ 3)$
and $x\equiv 3\ (\mathrm{mod}\ 5)$ give $x\equiv 8\pmod{15}$.

## 8.10 The pigeonhole principle

A small but powerful counting tool, and a favourite source of slick proofs.

**Theorem 8.14 (pigeonhole principle).** If $n+1$ objects are placed into $n$
boxes, some box contains at least two objects.

*Proof.* If every box held at most one object, the total would be at most $n < n
+1$. $\blacksquare$

**Corollary 8.15.** Among any $n+1$ integers, two are congruent modulo $n$.

*Proof.* There are only $n$ residue classes modulo $n$ (§8.7); with $n+1$
integers, two share a class. $\blacksquare$

This corollary is the engine behind arguments that force repetition — for
instance the **pumping lemma** for finite automata (Lecture 14), where among the
states visited along a long run, two must coincide.

## Exercises

**Warm-up.**

1. List all divisors of $36$ and give its prime factorization.
2. Compute $\gcd(84, 30)$ by the Euclidean algorithm, showing each step, then
   $\operatorname{lcm}(84,30)$.
3. Which residue class modulo $7$ contains $100$?

4. Find the inverse $5^{-1} \bmod 11$.

**Standard.**

5. Prove that if $a \mid b$ and $b \mid a$ then $a = \pm b$.
6. Compute $\varphi(360)$ using the product formula.
7. Prove that $n^2 - n$ is even for every integer $n$ (a direct proof; cf.
   Lecture 7).
8. Use the extended Euclidean algorithm (Bézout's identity) to find integers
   $x,y$ with $17x + 5y = 1$.
9. Solve the linear congruence $6x \equiv 8 \pmod{10}$, listing all solutions
   modulo $10$.
10. Use Fermat's little theorem to compute $2^{100} \bmod 7$.

**Challenge.**

11. Prove that there are infinitely many primes of the form $4k + 3$. *(Adapt
    Euclid's argument in §8.3.)*
12. Show that $a \equiv b \pmod{m}$ and $a \equiv b \pmod{n}$ with
    $\gcd(m,n)=1$ imply $a \equiv b \pmod{mn}$.
13. Solve the system $x \equiv 2 \pmod 3$, $x \equiv 3 \pmod 4$,
    $x \equiv 1 \pmod 5$ with the Chinese Remainder Theorem.

## Selected answers & hints

1. $36 = 2^2 3^2$; the nine divisors are $1,2,3,4,6,9,12,18,36$.
2. $84 = 2\cdot 30 + 24$, $30 = 1\cdot 24 + 6$, $24 = 4\cdot 6 + 0$, so
   $\gcd = 6$; then $\operatorname{lcm}(84,30) = 84\cdot 30 / 6 = 420$.
3. $[2]$, since $100 = 14\cdot 7 + 2$.
4. $5\cdot 9 = 45 = 4\cdot 11 + 1 \equiv 1 \pmod{11}$, so $5^{-1} \equiv 9$.
5. If both are nonzero, $b = ak$ and $a = b\ell$ give $a = a k\ell$, so
   $k\ell = 1$ and $k,\ell \in \{\pm 1\}$; hence $a = \pm b$. (If either is $0$,
   divisibility forces the other to be $0$ as well.)
6. $360 = 2^3 3^2 5$, so $\varphi(360) = 360\cdot\tfrac12\cdot\tfrac23\cdot
   \tfrac45 = 96$.
7. $n^2 - n = n(n-1)$ is a product of two consecutive integers, one of which is
   even, so the product is even.
8. $17 = 3\cdot 5 + 2$, $5 = 2\cdot 2 + 1$, so
   $1 = 5 - 2\cdot 2 = 5 - 2\,(17 - 3\cdot 5) = 7\cdot 5 - 2\cdot 17$; thus
   $(x,y) = (-2, 7)$.
9. $\gcd(6,10) = 2$ divides $8$, so there are two solutions modulo $10$. Dividing
   through by $2$: $3x \equiv 4 \pmod 5$, and $3^{-1} \equiv 2 \pmod 5$, so
   $x \equiv 2\cdot 4 \equiv 3 \pmod 5$; hence $x \equiv 3$ or $8 \pmod{10}$.
10. $2^6 \equiv 1 \pmod 7$ (Fermat) and $100 = 6\cdot 16 + 4$, so
    $2^{100} \equiv 2^4 = 16 \equiv 2 \pmod 7$.
11. Suppose only finitely many such primes $p_1,\dots,p_k$ (all $\ge 3$), and put
    $N = 4\,p_1\cdots p_k - 1$. Then $N \equiv 3 \pmod 4$, so — since a product of
    primes that are all $\equiv 1 \pmod 4$ would itself be $\equiv 1$ — $N$ has a
    prime factor $q \equiv 3 \pmod 4$. But $q$ divides no $p_i$ (each $p_i$
    divides $N+1$), so $q$ is a new prime of that form, a contradiction.
12. $m \mid (a-b)$ and $n \mid (a-b)$; write Bézout $1 = ms + nt$. Then
    $a - b = (a-b)ms + (a-b)nt$, and $mn$ divides both terms (the first because
    $n \mid (a-b)$, the second because $m \mid (a-b)$), so $mn \mid (a-b)$.
13. From $x \equiv 3 \pmod 4$ and $x \equiv 1 \pmod 5$ we get $x \equiv 11
    \pmod{20}$ (indeed $11 \bmod 4 = 3$, $11 \bmod 5 = 1$); and $11 \equiv 2
    \pmod 3$ already holds, so $x \equiv 11 \pmod{60}$.

## Chapter summary

- **Divisibility** $b \mid a$ and the **division algorithm** $a = bq + r$ are the
  foundation; common divisors survive linear combinations.
- **Primes** are the multiplicative atoms: every $n>1$ has a prime divisor, there
  are **infinitely many** primes (Euclid), and trial division to $\sqrt{n}$
  decides primality.
- The **Euclidean algorithm** computes $\gcd$ in $O(\log)$ steps; **Bézout** and
  **Euclid's lemma** give the **Fundamental Theorem of Arithmetic** — unique prime
  factorization — and $\gcd\cdot\operatorname{lcm} = ab$.
- **Congruence mod $n$** is an equivalence relation partitioning $\mathbb{Z}$ into
  $n$ residue classes; **Euler's totient** $\varphi(n) = n\prod(1-1/p)$ counts the
  coprime residues.
- The **pigeonhole principle** forces repetition — a proof tool reused for
  automata (Lecture 14).

**Cross-references within this course:** Lecture 3 (relations and equivalence —
congruence is an equivalence relation), Lecture 7 (methods of proof — every result
here is a direct/contradiction/induction proof), and **Laboratory Work 5**, which
implements parity, primality, GCD/LCM, factorization, and the totient.

## Further reading

- K. Rosen, *Discrete Mathematics and Its Applications* — number theory chapters.
- G. H. Hardy, E. M. Wright, *An Introduction to the Theory of Numbers*.
- V. Shoup, *A Computational Introduction to Number Theory and Algebra*.