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.

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))$.

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).

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.

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.

Lectures/CDM-L08.md · 17.3 KB · updated 2026-08-01 20:05