Contents / Discrete Mathematics / Number Theory

Chapter 6

Number Theory

The division algorithm with existence and uniqueness; primes, the square-root test and Euclid's infinitude; the Euclidean algorithm with its logarithmic bound and Fibonacci worst case; Bezout's identity from the extended algorithm; modular arithmetic, inverses and linear congruences; fast exponentiation by squaring; Fermat's little theorem, Euler's totient and the Chinese remainder theorem; and RSA with its correctness proved.

Introduction

Every other chapter of a discrete mathematics course teaches you to reason about finite structures. This one teaches you to compute inside one — the integers under addition and multiplication, cut down to a finite world by the single operation of taking remainders. That is a narrower subject than the number theory a mathematics department teaches, and deliberately so. The site's separate Number Theory subject develops divisibility, congruences and the classical theorems in their full generality, with the arithmetic of ideals waiting at the end of it. What follows is the working toolkit a computing student actually reaches for: how to decide whether a number is prime, how to compute a greatest common divisor quickly, how to invert and exponentiate modulo $n$ , how to reassemble a number from its remainders, and why those four skills are exactly what a public-key cryptosystem is built out of.

The word quickly is doing real work in that sentence, and it is the reason this material belongs in a computer science curriculum rather than being left to the mathematicians. Two problems about a $2048$ -bit integer $n$ look superficially alike: find $g cd (n, m)$ and find the prime factors of $n$ . The first is over in a few thousand machine operations. The second has resisted sixty years of concentrated effort and is believed to need more operations than there are atoms available to run them on. The gap between those two costs is not a footnote to the theory; it is the load-bearing wall under RSA, and the whole chapter is arranged to let you see where the gap comes from. Every algorithm here is stated with an operation count, and every operation count is proved.

The plan is linear. We start from division with remainder, which is the only primitive we assume, and from it derive the primes and the $n$ bound that makes small-scale primality testing feasible. Then we iterate division with remainder to get the Euclidean algorithm, prove that it is correct and that it runs in a number of steps proportional to the number of digits of its input — the Fibonacci numbers turn out to be its worst case, which is the prettiest complexity result in elementary mathematics. Running the same algorithm backwards produces Bézout coefficients, and Bézout coefficients produce modular inverses. Inverses plus fast exponentiation give us everything needed for the Chinese Remainder Theorem and then for RSA, whose decryption step we prove correct in the last section.

Throughout, $Z$ is the set of integers and $N = {1, 2, 3, \dots}$ . We assume one property of $Z$ without proof, the well-ordering principle: every nonempty set of non-negative integers contains a least element. Every existence proof below is ultimately an appeal to it.

6.1Division with Remainder and the Primes

Nothing in this chapter predates the operation you learned in primary school: divide, and keep the remainder. Stated precisely it is a theorem, not a definition, and the two clauses that make it useful — that the remainder exists, and that it is unique — both need an argument.

Theorem 6.1 (The division algorithm). Let $a \in Z$ and $n \in N$ . Then there exist unique integers $q$ and $r$ with

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

We call $q$ the quotient and $r$ the remainder, and write $r = a mod n$ .

Proof. Existence. Consider the set $S = {a - kn : k \in Z, a - kn \geq 0}$ of non-negative numbers of that shape. It is nonempty: taking $k = - ∣ a ∣$ gives $a + ∣ a ∣ n \geq a + ∣ a ∣ \geq 0$ , since $n \geq 1$ . By well-ordering $S$ has a least element $r = a - q n$ for some $q$ . If we had $r \geq n$ then $r - n = a - (q + 1) n$ would be a smaller non-negative member of $S$ , contradicting minimality. Hence $0 \leq r < n$ .

Uniqueness. Suppose $a = q n + r = q^{'} n + r^{'}$ with both remainders in $[0, n)$ . Subtracting, $(q - q^{'}) n = r^{'} - r$ . The right-hand side satisfies $∣ r^{'} - r ∣ < n$ , while the left-hand side is a multiple of $n$ ; the only multiple of $n$ of absolute value less than $n$ is $0$ . So $r = r^{'}$ , and then $(q - q^{'}) n = 0$ with $n \neq = 0$ forces $q = q^{'}$ .∎

Remark. The insistence that $0 \leq r < n$ is what makes $a mod n$ a function rather than a family of choices, and it is where hand computation and machine computation part company. In C, Java and Go the % operator takes the sign of the dividend, so -7 % 3 is $- 1$ , not the mathematical $2$ . Python's % agrees with this theorem. When a congruence in your code behaves strangely for negative inputs, this is almost always why; the repair is ((a % n) + n) % n.

Definition 6.2 (Divisibility). For integers $d$ and $a$ we say $d$ divides $a$ , written $d ∣ a$ , if $a = d k$ for some integer $k$ . Equivalently, when $d \in N$ : $d ∣ a$ exactly when $a mod d = 0$ .

Definition 6.3 (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, and then $n = ab$ for some integers $a, b$ with $1 < a \leq b < n$ .

The exclusion of $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 theorem that makes the primes worth naming would be false. A unit is not an atom.

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

Proof. Let $D$ be the set of divisors of $n$ that are greater than $1$ . It is nonempty, since $n \in D$ , so by well-ordering it has a least element $p$ . If $p$ were composite it would have a divisor $d$ with $1 < d < p$ , and $d ∣ p$ together with $p ∣ n$ gives $d ∣ n$ , so $d$ would be a member of $D$ smaller than $p$ . That is impossible, so $p$ is prime.∎

That lemma is the engine of two very different results: the $n$ bound, which makes primality testing cheap for small numbers, and Euclid's proof that the primes never run out.

Theorem 6.5 (The square-root bound). 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. Write $n = ab$ with $1 < a \leq b < n$ , which is possible because $n$ is composite. If both factors exceeded $n$ we would have $n = ab > n \cdot n = n$ , a contradiction; so $a \leq n$ . Since $a > 1$ , the lemma Every integer above one has a prime divisor gives a prime $p ∣ a$ , and $p \leq a \leq n$ . Transitivity of divisibility gives $p ∣ n$ .

The second sentence is the contrapositive of the first, together with the observation that $n$ is either prime or composite.∎

Method 6.6 (Trial division). To test $n > 1$ for primality: for each integer $d = 2, 3, 4, \dots$ while $d^{2} \leq n$ , test whether $d ∣ n$ . If some $d$ divides $n$ , report composite with witness $d$ . If the loop finishes, report prime.

Note the loop condition d*d <= n rather than d <= sqrt(n): it avoids a floating-point square root whose rounding could cut the search one step short. Testing every $d$ rather than every prime $d$ costs a constant factor and saves you from needing a list of primes before you can test for primality.

Proposition 6.7 (The cost of trial division). Trial division performs at most $n$ divisions. In terms of the input length $ℓ = ⌈ lo g_{2} n ⌉$ — the number of bits actually written down — this is about $2^{ℓ /2}$ divisions, which is exponential in $ℓ$ .

Proof. The loop variable runs over $2 \leq d \leq n$ , so there are fewer than $n$ iterations, each one division. Substituting $n \approx 2^{ℓ}$ gives $n \approx 2^{ℓ /2}$ .∎

Intuition. Halving an exponent sounds like progress, and for a $30$ -bit number it is: $2^{15}$ divisions is nothing. For a $2048$ -bit RSA modulus it is $2^{1024}$ divisions, which is not a large number of operations so much as a way of writing "never". The moral to carry forward is that a cost of $n$ is slow when $n$ is an input written in binary, while a cost of $lo g n$ is fast. Every algorithm in the rest of the chapter is on the $lo g n$ side of that line, and trial division is the only one that is not.

Example 6.8 (Certifying 211 prime). Show that $211$ is prime, and count the divisions performed.

Solution.

Since $1 4^{2} = 196 \leq 211$ and $1 5^{2} = 225 > 211$ , the loop runs over $d = 2, \dots, 14$ : thirteen divisions at most.
$211$ is odd, so $2 ∤ 211$ . Its digit sum is $4$ , so $3 ∤ 211$ . It does not end in $0$ or $5$ , so $5 ∤ 211$ . Then $211 = 7 \cdot 30 + 1$ , $211 = 11 \cdot 19 + 2$ , $211 = 13 \cdot 16 + 3$ , and the composite values of $d$ cannot divide $211$ if no prime below them does.
The loop finishes with no witness, so by the theorem The square-root bound, $211$ is prime.

□

Example 6.9 (Factoring 8633 by trial division). Factor $8633$ completely.

Solution.

$8633 \approx 92.9$ , so a prime factor at or below $92$ must exist if the number is composite.
Testing in order, $2, 3, 5, 7, 11, \dots$ all fail until $d = 89$ : $8633 = 89 \cdot 97$ .
Both $89$ and $97$ are prime — neither has a prime factor at or below $9$ — so $8633 = 89 \cdot 97$ is the complete factorisation.
Notice how hard the search worked: twenty-three divisions to split a four-digit number whose factors are nearly equal. Factoring is easy only when a small factor exists, and a cryptographer chooses $p$ and $q$ of equal size precisely to deny you that.

□

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

n = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{k}^{e_{k}}

with $p_{1} < p_{2} < \dots < p_{k}$ and each $e_{i} \geq 1$ , and this expression is unique.

Proof. Existence, by strong induction on $n$ . If $n$ is prime the factorisation is $n$ itself. Otherwise $n = ab$ with $1 < a \leq b < n$ ; both $a$ and $b$ are smaller than $n$ and greater than $1$ , so by the induction hypothesis each is a product of primes, and concatenating those two products expresses $n$ as a product of primes. Collecting equal primes into powers and sorting gives the stated form.

Uniqueness needs Euclid's lemma — if a prime divides a product it divides one of the factors — which in turn needs Bézout's identity, proved below as Bézout's identity. The argument is carried out in full in the chapter Divisibility and Primes, and we use the result here without repeating it.∎

Corollary 6.11 (Reading off exponents). Let $m$ and $n$ be positive integers written over a common list of primes as $m = \prod_{i} p_{i}^{a_{i}}$ and $n = \prod_{i} p_{i}^{b_{i}}$ , where an exponent of $0$ records an absent prime. Then $m ∣ n$ if and only if $a_{i} \leq b_{i}$ for every $i$ .

Proof. If $a_{i} \leq b_{i}$ for all $i$ , then $n = m \cdot \prod_{i} p_{i}^{b_{i} - a_{i}}$ and the second factor is a positive integer, so $m ∣ n$ . Conversely if $n = m c$ , factor $c$ into primes; the factorisation of $n$ obtained by concatenating those of $m$ and $c$ must, by uniqueness, be the factorisation of $n$ , so every exponent in $m$ is at most the corresponding exponent in $n$ .∎

The primes are therefore a coordinate system: a positive integer is a vector of exponents, multiplication is vector addition, and divisibility is coordinatewise $\leq$ . The catch — the one that keeps cryptography in business — is that converting a number into those coordinates is the hard problem of the previous example.

Theorem 6.12 (Infinitude of the primes). There are infinitely many primes.

Proof. Suppose there were only finitely many, say $p_{1}, \dots, p_{k}$ , and set

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

Then $N > 1$ , so by the lemma Every integer above one has a prime divisor it has a prime divisor $p$ , which must be some $p_{i}$ from the list. But $p_{i}$ divides the product $p_{1} \dots p_{k}$ , and it divides $N$ , hence it divides their difference $N - p_{1} \dots p_{k} = 1$ . No prime divides $1$ , a contradiction. So no finite list contains every prime.∎

Pitfall. Euclid's argument does not claim that $p_{1} p_{2} \dots p_{k} + 1$ is prime. It claims that its prime factors are missing from the list. The distinction is easy to check: $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509$ , which is composite, yet both $59$ and $509$ are indeed absent from ${2, 3, 5, 7, 11, 13}$ , exactly as the proof predicts.

Method 6.13 (Sieve of Eratosthenes). To list every prime up to $N$ : create a boolean array indexed $2 \dots N$ , all initially true. For each $p$ from $2$ while $p^{2} \leq N$ , if $p$ is still marked true, mark false every entry $p^{2}, p^{2} + p, p^{2} + 2 p, \dots$ up to $N$ . The indices still true at the end are exactly the primes.

Proposition 6.14 (The sieve is correct). After the sieve terminates, index $m$ is marked true if and only if $m$ is prime.

Proof. No prime is ever marked false: the entries marked in the pass for $p$ are the multiples $k p$ with $k \geq p$ , all of which are composite.

Conversely let $m \leq N$ be composite. By the theorem The square-root bound it has a prime divisor $p \leq m \leq N$ , so the pass for $p$ does occur, and $p$ is still true at that moment since no prime is ever marked false. Write $m = k p$ ; from $p \leq m$ we get $k = m / p \geq p$ , so $m = k p$ lies in the marked progression $p^{2}, p^{2} + p, \dots$ and is set false.∎

Starting each pass at $p^{2}$ rather than $2 p$ is worth noticing: every smaller multiple of $p$ has a prime factor below $p$ and was therefore already struck out. The total work is $\sum_{p \leq N} N / p$ , which is about $N ln ln N$ — essentially linear, and the reason a sieve is the right way to get all primes below a bound while trial division is the right way to test one number.

Example 6.15 (Sieving up to 30). Run the sieve to $N = 30$ and count the primes found.

Solution.

$p = 2$ : strike $4, 6, 8, \dots, 30$ .
$p = 3$ : still true, so strike $9, 15, 21, 27$ (even multiples are already gone).
$p = 4$ : already false, skip. $p = 5$ : strike $25$ . Then $6^{2} = 36 > 30$ , so the loop ends.
Survivors: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29$ — that is $π (30) = 10$ primes.

□

Remark. The prime counting function $π (x)$ satisfies $π (x) \sim x / ln x$ , the Prime Number Theorem. For a working programmer the useful reading is: a random odd integer near $2^{1024}$ is prime with probability about $2/ ln (2^{1024}) \approx 1/355$ , so generating an RSA prime means testing a few hundred candidates. The analytic machinery behind that estimate is developed in Analytic Number Theory; the estimate itself is all we need.

Exercises for §6.1 →

6.2Divisors, gcd and lcm

Divisibility rarely appears alone. What a computation usually needs is the largest thing two numbers have in common, or the smallest thing that contains both.

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

Proof. Write $a = d α$ and $b = d β$ . Then $a x + b y = d (αx + β y)$ , and $αx + β y$ is an integer.∎

Small as it is, this proposition is used in almost every proof that follows; whenever an argument concludes "so $d$ divides the remainder too", this is why.

Definition 6.17 (Greatest common divisor). For integers $a, b$ not both zero, $g cd (a, b)$ is the largest positive integer dividing both. If $g cd (a, b) = 1$ we call $a$ and $b$ coprime. By convention $g cd (a, 0) = ∣ a ∣$ for $a \neq = 0$ .

Definition 6.18 (Least common multiple). For positive integers $a, b$ , $lcm (a, b)$ is the smallest positive integer that both $a$ and $b$ divide.

The gcd is well defined because the common divisors of $a$ and $b$ all lie in $[1, max (∣ a ∣, ∣ b ∣)]$ when one of them is nonzero, so the set of them is finite and nonempty — it contains $1$ .

Theorem 6.19 (gcd and lcm from the factorisations). Let $a = \prod_{i} p_{i}^{a_{i}}$ and $b = \prod_{i} p_{i}^{b_{i}}$ over a common list of primes. 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. Let $g = \prod_{i} p_{i}^{m i n (a_{i}, b_{i})}$ . By the corollary Reading off exponents, an integer $d = \prod_{i} p_{i}^{d_{i}}$ divides $a$ exactly when $d_{i} \leq a_{i}$ for all $i$ , and divides $b$ exactly when $d_{i} \leq b_{i}$ . So $d$ is a common divisor precisely when $d_{i} \leq min (a_{i}, b_{i})$ for every $i$ , which says exactly that $d ∣ g$ . Every common divisor divides $g$ , hence is at most $g$ , and $g$ is itself a common divisor; so $g$ is the greatest.

The lcm argument is the same with the inequalities reversed: $a ∣ m$ and $b ∣ m$ hold together precisely when $m_{i} \geq max (a_{i}, b_{i})$ for each $i$ , and the least such $m$ takes equality throughout.∎

Corollary 6.20 (Product of gcd and lcm). For positive integers $a$ and $b$ , $g cd (a, b) \cdot lcm (a, b) = ab$ .

Proof. For any two real numbers, $min (a_{i}, b_{i}) + max (a_{i}, b_{i}) = a_{i} + b_{i}$ . Multiplying the two formulas of the theorem gcd and lcm from the factorisations adds the exponents prime by prime, giving $\prod_{i} p_{i}^{a_{i} + b_{i}} = ab$ .∎

That corollary is how lcm is computed in practice: never by factoring, but as a / gcd(a,b) * b, dividing first so the intermediate value does not overflow.

Theorem 6.21 (Divisor-counting formula). If $n = p_{1}^{e_{1}} \dots p_{k}^{e_{k}}$ then the number of positive divisors of $n$ is

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

Proof. By the corollary Reading off exponents, the divisors of $n$ correspond exactly to the exponent tuples $(d_{1}, \dots, d_{k})$ with $0 \leq d_{i} \leq e_{i}$ , and distinct tuples give distinct integers by uniqueness of factorisation. There are $e_{i} + 1$ choices for each coordinate, chosen independently, so the product rule gives $\prod_{i} (e_{i} + 1)$ tuples.∎

Example 6.22 (Divisors, gcd and lcm of 84 and 360). Compute $τ (360)$ , $g cd (84, 360)$ and $lcm (84, 360)$ .

Solution.

Factor: $84 = 2^{2} \cdot 3 \cdot 7$ and $360 = 2^{3} \cdot 3^{2} \cdot 5$ .
$τ (360) = (3 + 1) (2 + 1) (1 + 1) = 24$ .
Minimum exponents: $2^{m i n (2, 3)} 3^{m i n (1, 2)} 5^{m i n (0, 1)} 7^{m i n (1, 0)} = 2^{2} \cdot 3 = 12$ , so $g cd = 12$ .
Maximum exponents: $2^{3} \cdot 3^{2} \cdot 5 \cdot 7 = 2520$ , so $lcm = 2520$ .
Check: $12 \cdot 2520 = 30240 = 84 \cdot 360$ , as the corollary Product of gcd and lcm requires.

□

Pitfall. This section's formulas are correct and almost useless for large inputs, because they all begin "factor $n$ ". A $2048$ -bit gcd computed by factoring would take longer than the universe has existed; the same gcd by the algorithm of the next section takes under a millisecond. Keep the factorisation picture for understanding what the gcd is, and use Euclid to get it.

Exercises for §6.2 →

6.3The Euclidean Algorithm and its Cost

Euclid's algorithm is the oldest non-trivial algorithm still in daily use, and it is the first place where a student sees a proof of correctness and a proof of running time sitting side by side. Both are short. Both matter.

Lemma 6.23 (Euclid's identity). For integers $a$ and $n$ with $n > 0$ ,

g cd (a, n) = g cd (n, a mod n) .

Proof. Write $a = q n + r$ with $r = a mod n$ , as the theorem The division algorithm permits. If $d$ divides both $a$ and $n$ , then by Linearity of divisibility it divides $a - q n = r$ , so $d$ is a common divisor of $n$ and $r$ . Conversely if $d$ divides both $n$ and $r$ , the same proposition gives $d ∣ q n + r = a$ , so $d$ is a common divisor of $a$ and $n$ .

The two pairs therefore have identical sets of common divisors, and so the same greatest one.∎

Method 6.24 (Euclidean algorithm). Given $a \geq b \geq 0$ , repeat $(a, b) \leftarrow (b, a mod b)$ until $b = 0$ . Then output $a$ .

Theorem 6.25 (Correctness of the Euclidean algorithm). On input $(a, b)$ with $a \geq b \geq 0$ and $a > 0$ , the algorithm terminates and outputs $g cd (a, b)$ .

Proof. Termination. The second component of the pair is a sequence of non-negative integers, and after the first step each is a remainder modulo its predecessor, hence strictly smaller: $b > a mod b \geq 0$ . A strictly decreasing sequence of non-negative integers is finite, so some component eventually equals $0$ and the loop stops.

Correctness. The quantity $g cd (a, b)$ is an invariant of the loop body: the lemma Euclid's identity says precisely that replacing $(a, b)$ by $(b, a mod b)$ leaves it unchanged. It holds on entry, so it holds on exit, where the pair is $(g, 0)$ for some $g$ . Since $g cd (g, 0) = g$ , the returned value is the gcd of the original inputs.∎

Termination is one thing; speed is another. A decreasing sequence of integers could take $a$ steps to reach zero. It does not, and the reason is that a remainder is not merely smaller than the divisor — it is smaller by a lot, at least every other step.

Lemma 6.26 (Two steps at least halve). If $a \geq b > 0$ , then $a mod b < a /2$ .

Proof. Two cases. If $b \leq a /2$ then $a mod b < b \leq a /2$ , since a remainder is always less than the divisor. If $b > a /2$ then the quotient is $1$ , because $b \leq a < 2 b$ , and so $a mod b = a - b < a - a /2 = a /2$ .∎

Theorem 6.27 (The Euclidean algorithm runs in logarithmic time). On input $(a, b)$ with $a \geq b \geq 0$ , the Euclidean algorithm performs at most $2 lo g_{2} a + 1$ division steps. In terms of the input length $ℓ$ in bits, this is $O (ℓ)$ divisions.

Proof. Let $r_{0} = a$ , $r_{1} = b$ and $r_{i + 1} = r_{i - 1} mod r_{i}$ be the sequence of values. The lemma Two steps at least halve applied to the pair $(r_{i - 1}, r_{i})$ gives $r_{i + 1} < r_{i - 1} /2$ . So along either the even-indexed or the odd-indexed subsequence, the values at least halve each time, and therefore

r_{2 k} < \frac{r _{0}}{2 ^{k}} .

Since the values are non-negative integers, the sequence must reach $0$ once $r_{0} / 2^{k}$ drops to $1$ or below, i.e. by $k = ⌊ lo g_{2} a ⌋ + 1$ . Each increment of $k$ covers two steps, giving at most $2 lo g_{2} a + 1$ divisions.

An integer with $ℓ$ bits satisfies $a < 2^{ℓ}$ , so the bound is at most $2 ℓ + 1$ divisions.∎

Intuition. Compare the two costs honestly. Factoring a $2048$ -bit number to get its gcd would take about $2^{1024}$ operations; Euclid takes about $4096$ divisions. The algorithm never learns a single prime factor of either input, and that is exactly why it is fast — it extracts the one piece of shared structure you asked for without solving the hard problem that also contains it. Almost every fast number-theoretic algorithm has this shape.

The bound $2 lo g_{2} a$ is not tight, and the exact worst case is a small miracle: it is the input on which every quotient is as small as possible, namely $1$ , which forces the sequence of remainders to run backwards through the Fibonacci numbers.

Theorem 6.28 (Fibonacci inputs are the worst case). Let $F_{1} = F_{2} = 1$ and $F_{k + 1} = F_{k} + F_{k - 1}$ . If the Euclidean algorithm on input $(a, b)$ with $a > b > 0$ performs exactly $k$ division steps, then $a \geq F_{k + 2}$ and $b \geq F_{k + 1}$ . The pair $(F_{k + 2}, F_{k + 1})$ attains this, taking exactly $k$ steps.

Proof. Induct on $k$ . For $k = 1$ the algorithm stops after one division, which needs $b \geq 1 = F_{2}$ and $a > b$ so $a \geq 2 = F_{3}$ .

Suppose the claim holds for $k - 1$ and let $(a, b)$ take $k$ steps. The first step produces the pair $(b, r)$ with $r = a mod b$ , which takes $k - 1$ steps, so by induction $b \geq F_{k + 1}$ and $r \geq F_{k}$ . The first division gives $a = q b + r$ with $q \geq 1$ because $a > b$ , hence

a \geq b + r \geq F_{k + 1} + F_{k} = F_{k + 2} .

For the attainment, run the algorithm on $(F_{k + 2}, F_{k + 1})$ : since $F_{k + 2} = 1 \cdot F_{k + 1} + F_{k}$ and $0 \leq F_{k} < F_{k + 1}$ for $k \geq 2$ , every quotient is $1$ and the pair becomes $(F_{k + 1}, F_{k})$ . Repeating, the algorithm descends the Fibonacci sequence one index per step and halts on $(F_{2}, F_{1}) = (1, 1) \to (1, 0)$ after exactly $k$ steps.∎

Corollary 6.29 (Lamé's bound). The number of division steps on input $(a, b)$ with $b \leq a$ is at most $5$ times the number of decimal digits of $b$ .

Proof. If the algorithm takes $k$ steps then $b \geq F_{k + 1}$ by the theorem Fibonacci inputs are the worst case. Since $F_{k + 1} \geq φ^{k - 1}$ where $φ = (1 + 5) /2$ , taking base- $10$ logarithms gives $(k - 1) lo g_{10} φ \leq lo g_{10} b$ , and $lo g_{10} φ \approx 0.2090 > 1/5$ . Hence $k - 1 < 5 lo g_{10} b$ , so $k \leq 5 d$ where $d$ is the number of decimal digits of $b$ .∎

Figure 6.30. The remainder sequence collapses on a typical input and crawls on the Fibonacci worst case. Both start near

1000

; one is finished in four steps, the other needs fifteen.

Example 6.31 (Counting the steps on a Fibonacci pair). How many division steps does the Euclidean algorithm take on $(89, 55)$ , and what is the gcd?

Solution.

$89 = F_{11}$ and $55 = F_{10}$ , so the theorem Fibonacci inputs are the worst case predicts $k$ steps where $k + 2 = 11$ , that is $k = 9$ .
Running it: $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.
The last nonzero remainder is $1$ , so $g cd (89, 55) = 1$ — consecutive Fibonacci numbers are always coprime.
For comparison, $g cd (1000, 999)$ takes two steps despite the larger inputs. Size is not what makes the algorithm work hard; small quotients are.

□

Running the algorithm backwards: Bézout

Every division step wrote a remainder as a combination of the two numbers above it. Keeping those combinations as we go expresses the gcd itself in terms of the original inputs, which is the single most useful by-product in the chapter.

Theorem 6.32 (Bézout's identity). For any integers $a, b$ not both zero there exist integers $x, y$ with

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

Proof. We prove it by exhibiting the algorithm that produces $x$ and $y$ . Alongside the remainder sequence $r_{0} = a$ , $r_{1} = b$ , $r_{i + 1} = r_{i - 1} - q_{i} r_{i}$ , maintain coefficient sequences

x_{0} = 1, x_{1} = 0, y_{0} = 0, y_{1} = 1, x_{i + 1} = x_{i - 1} - q_{i} x_{i}, y_{i + 1} = y_{i - 1} - q_{i} y_{i},

using the same quotients $q_{i}$ . We claim the invariant $r_{i} = a x_{i} + b y_{i}$ holds for every $i$ .

It holds at $i = 0$ and $i = 1$ by the initial values. Assuming it for $i - 1$ and $i$ ,

r_{i + 1} = r_{i - 1} - q_{i} r_{i} = (a x_{i - 1} + b y_{i - 1}) - q_{i} (a x_{i} + b y_{i}) = a (x_{i - 1} - q_{i} x_{i}) + b (y_{i - 1} - q_{i} y_{i}) = a x_{i + 1} + b y_{i + 1} .

By the theorem Correctness of the Euclidean algorithm the last nonzero remainder $r_{m}$ equals $g cd (a, b)$ , and the invariant at $i = m$ reads $g cd (a, b) = a x_{m} + b y_{m}$ .∎

Method 6.33 (Extended Euclidean algorithm). Keep a table with columns $r$ , $q$ , $x$ , $y$ . Seed the first two rows with $(a, -, 1, 0)$ and $(b, -, 0, 1)$ . At each step compute $q = ⌊ r_{i - 1} / r_{i} ⌋$ , then subtract $q$ times the current row from the row above it, componentwise, to produce the next row. Stop when $r$ reaches $0$ ; the previous row reads $(g cd, \cdot, x, y)$ with $a x + b y = g cd$ .

Example 6.34 (A full extended Euclid trace). Compute $g cd (240, 46)$ and Bézout coefficients.

Solution.

Set up the table and run it. Each row is (remainder, quotient used to make it, $x$ , $y$ ):

r 24046106420 q - - 54112 x 101 - 4 5 - 9 y 01 - 5 21 - 26 47

Row three, for instance, comes from $240 - 5 \cdot 46 = 10$ applied to all three columns: $1 - 5 \cdot 0 = 1$ and $0 - 5 \cdot 1 = - 5$ .
The last nonzero remainder is $2$ , so $g cd (240, 46) = 2$ , with $x = - 9$ and $y = 47$ .
Check the invariant on the final row: $240 \cdot (- 9) + 46 \cdot 47 = - 2160 + 2162 = 2$ .

□

Corollary 6.35 (The gcd is the least positive combination). $g cd (a, b)$ is the smallest positive integer expressible as $a x + b y$ with $x, y \in Z$ . Consequently $a x + b y = c$ has an integer solution if and only if $g cd (a, b) ∣ c$ .

Proof. Let $g = g cd (a, b)$ . By Bézout's identity, $g$ is expressible. By Linearity of divisibility, $g$ divides every combination $a x + b y$ , so every positive combination is at least $g$ ; hence $g$ is the least.

For the second claim. If $a x + b y = c$ then $g ∣ c$ by the same linearity. Conversely if $c = g k$ , multiply a Bézout expression by $k$ to get $a (x k) + b (y k) = c$ .∎

Example 6.36 (When can a linear Diophantine equation be solved?). Does $6 x + 15 y = 21$ have an integer solution? Does $6 x + 15 y = 20$ ?

Solution.

$g cd (6, 15) = 3$ . Since $3 ∣ 21$ , the corollary The gcd is the least positive combination guarantees a solution to the first.
Bézout for $(6, 15)$ : $6 \cdot 3 + 15 \cdot (- 1) = 3$ . Multiplying through by $7$ gives $6 \cdot 21 + 15 \cdot (- 7) = 21$ , so $(x, y) = (21, - 7)$ works.
For the second, $3 ∤ 20$ , so no integer solution exists — every value of $6 x + 15 y$ is a multiple of $3$ .

□

Exercises for §6.3 →

6.4Modular Arithmetic

Reducing modulo $n$ throws away everything about an integer except its remainder. What survives is still a system in which you can add, subtract and multiply, and it is finite — which is why a computer can work in it exactly, with no overflow and no rounding, for arbitrarily long computations.

Definition 6.37 (Congruence). For $n \in N$ and integers $a, b$ , write $a \equiv b (mod n)$ if $n ∣ (a - b)$ ; equivalently, if $a$ and $b$ leave the same remainder on division by $n$ .

Definition 6.38 (Residue classes). Congruence modulo $n$ is an equivalence relation, and its classes are the residue classes modulo $n$ . There are exactly $n$ of them, represented by $0, 1, \dots, n - 1$ ; the set of classes with its induced arithmetic is written $Z_{n}$ .

Proposition 6.39 (Arithmetic respects congruence). If $a \equiv b$ and $c \equiv d (mod n)$ , then

a + c \equiv b + d, a - c \equiv b - d, a c \equiv b d (mod n),

and hence $a^{k} \equiv b^{k} (mod n)$ for every $k \geq 1$ .

Proof. Write $a - b = n s$ and $c - d = n t$ . Then $(a + c) - (b + d) = n (s + t)$ and $(a - c) - (b - d) = n (s - t)$ , both multiples of $n$ . For the product,

a c - b d = a c - b c + b c - b d = c (a - b) + b (c - d) = n (cs + b t),

again a multiple of $n$ . The power statement follows by induction on $k$ , multiplying the congruence $a^{k - 1} \equiv b^{k - 1}$ by $a \equiv b$ .∎

This proposition is a licence to reduce early and often. It is what keeps intermediate values bounded by $n^{2}$ in a computation that would otherwise produce numbers with millions of digits.

Figure 6.40. Arithmetic modulo

12

lives on a dial. Adding

5

to the class of

10

walks five places clockwise and lands on

3

, because

15 - 3

is a multiple of

12

Pitfall. Cancellation is the one rule that does not carry over. From $a c \equiv b c (mod n)$ you may not conclude $a \equiv b$ . Modulo $12$ , $4 \cdot 3 \equiv 4 \cdot 6$ (both are $0$ ), yet $3 \neq \equiv 6$ . The precise condition under which cancelling $c$ is legal is $g cd (c, n) = 1$ , and the next theorem says why.

Definition 6.41 (Modular inverse). An integer $x$ is an inverse of $a$ modulo $n$ if $a x \equiv 1 (mod n)$ . We then write $x \equiv a^{- 1} (mod n)$ .

Theorem 6.42 (Inverses exist exactly for coprime residues). Let $n \in N$ and $a \in Z$ . Then $a$ has an inverse modulo $n$ if and only if $g cd (a, n) = 1$ , and in that case the inverse is unique modulo $n$ .

Proof. ( $\Leftarrow$ ) Suppose $g cd (a, n) = 1$ . By Bézout's identity there are integers $x, y$ with $a x + n y = 1$ . Reading this modulo $n$ kills the term $n y$ , leaving $a x \equiv 1 (mod n)$ .

( $\Rightarrow$ ) Suppose $a x \equiv 1 (mod n)$ , so $a x - 1 = nk$ for some $k$ , that is $a x - nk = 1$ . Any common divisor $d$ of $a$ and $n$ divides the left side by Linearity of divisibility, hence divides $1$ ; so $g cd (a, n) = 1$ .

Uniqueness. If $a x \equiv 1$ and $a x^{'} \equiv 1$ , multiply the first congruence by $x^{'}$ to get $x^{'} a x \equiv x^{'}$ , and the second by $x$ to get $x a x^{'} \equiv x$ . The left sides are equal, so $x \equiv x^{'} (mod n)$ .∎

The proof is an algorithm. To invert $a$ modulo $n$ , run extended Euclid on $(a, n)$ , check the gcd is $1$ , and reduce the coefficient $x$ into $[0, n)$ . The cost is the cost of Euclid — logarithmic — which is why inversion is a cheap operation even for cryptographic-size moduli.

Example 6.43 (Inverting 17 modulo 43). Find $1 7^{- 1} mod 43$ .

Solution.

Extended Euclid on $(43, 17)$ : $43 = 2 \cdot 17 + 9$ , $17 = 1 \cdot 9 + 8$ , $9 = 1 \cdot 8 + 1$ , $8 = 8 \cdot 1 + 0$ . So $g cd = 1$ and an inverse exists.
Back-substitute: $1 = 9 - 8 = 9 - (17 - 9) = 2 \cdot 9 - 17 = 2 (43 - 2 \cdot 17) - 17 = 2 \cdot 43 - 5 \cdot 17$ .
Hence $- 5 \cdot 17 \equiv 1 (mod 43)$ , so $1 7^{- 1} \equiv - 5 \equiv 38 (mod 43)$ .
Check: $17 \cdot 38 = 646 = 15 \cdot 43 + 1$ .

□

Corollary 6.44 (Cancellation modulo n). If $g cd (c, n) = 1$ and $a c \equiv b c (mod n)$ , then $a \equiv b (mod n)$ .

Proof. By the theorem Inverses exist exactly for coprime residues, $c^{- 1}$ exists modulo $n$ . Multiply both sides of $a c \equiv b c$ by it and use Arithmetic respects congruence: $a \equiv a c c^{- 1} \equiv b c c^{- 1} \equiv b$ .∎

Theorem 6.45 (Solving a linear congruence). Let $d = g cd (a, n)$ . The congruence $a x \equiv b (mod n)$ has a solution if and only if $d ∣ b$ , and then it has exactly $d$ solutions modulo $n$ , forming one residue class modulo $n / d$ .

Proof. The congruence says $a x - b = nk$ for some integer $k$ , i.e. $a x - nk = b$ , which by the corollary The gcd is the least positive combination is solvable exactly when $d ∣ b$ .

Suppose $d ∣ b$ and write $a = d a^{'}$ , $b = d b^{'}$ , $n = d n^{'}$ with $g cd (a^{'}, n^{'}) = 1$ . Dividing the equation $a x \equiv b (mod n)$ through by $d$ gives the equivalent congruence $a^{'} x \equiv b^{'} (mod n^{'})$ , whose unique solution modulo $n^{'}$ is $x \equiv (a^{'})^{- 1} b^{'} (mod n^{'})$ , the inverse existing by Inverses exist exactly for coprime residues. A single class modulo $n^{'} = n / d$ splits into exactly $d$ classes modulo $n$ , namely $x_{0}, x_{0} + n^{'}, \dots, x_{0} + (d - 1) n^{'}$ .∎

Example 6.46 (A congruence with three solutions). Solve $6 x \equiv 9 (mod 15)$ .

Solution.

$d = g cd (6, 15) = 3$ and $3 ∣ 9$ , so solutions exist — three of them modulo $15$ .
Divide through by $3$ : $2 x \equiv 3 (mod 5)$ . Since $2^{- 1} \equiv 3 (mod 5)$ , we get $x \equiv 9 \equiv 4 (mod 5)$ .
Lifting to modulus $15$ : $x \in {4, 9, 14}$ .
Check $x = 9$ : $6 \cdot 9 = 54 = 3 \cdot 15 + 9$ .

□

Fast modular exponentiation

Computing $a^{k} mod n$ by multiplying $a$ by itself $k - 1$ times is hopeless when $k$ has hundreds of digits — and in RSA it always does. The fix is to exploit the binary expansion of the exponent.

Method 6.47 (Square-and-multiply). Write $k$ in binary as $k = \sum_{i = 0}^{t} b_{i} 2^{i}$ with $b_{t} = 1$ . Set $y \leftarrow 1$ and, reading the bits from the most significant down to the least, at each bit replace $y \leftarrow y^{2} mod n$ and then, if that bit is $1$ , replace $y \leftarrow y \cdot a mod n$ .

Theorem 6.48 (Correctness and cost of square-and-multiply). Square-and-multiply outputs $a^{k} mod n$ using at most $2 ⌊ lo g_{2} k ⌋$ modular multiplications: one squaring per bit of $k$ after the first, plus one extra multiplication for each $1$ -bit.

Proof. Correctness. Let $k_{j} = \sum_{i = j}^{t} b_{i} 2^{i - j}$ be the number formed by the top $t - j + 1$ bits of $k$ . We claim that after processing bit $b_{j}$ the variable satisfies $y \equiv a^{k_{j}} (mod n)$ , by downward induction on $j$ .

Before any bit is processed, $y = 1 = a^{0}$ , the empty prefix. Suppose $y \equiv a^{k_{j + 1}}$ before bit $b_{j}$ is processed. Appending a bit to a binary numeral doubles the value and adds the bit: $k_{j} = 2 k_{j + 1} + b_{j}$ . The step squares, giving $y^{2} \equiv a^{2 k_{j + 1}}$ , and then multiplies by $a$ exactly when $b_{j} = 1$ , giving $y \equiv a^{2 k_{j + 1} + b_{j}} = a^{k_{j}}$ . Each congruence is legitimate by Arithmetic respects congruence, which also permits the reduction modulo $n$ at every step.

After the last bit, $k_{0} = k$ and $y \equiv a^{k} (mod n)$ .

Cost. The number of bits is $t + 1 = ⌊ lo g_{2} k ⌋ + 1$ . Each contributes one squaring, and the $1$ -bits contribute one multiplication each; there are at most $t + 1$ of those. The leading squaring acts on $y = 1$ and can be skipped, leaving at most $2 ⌊ lo g_{2} k ⌋ + 1$ multiplications, all of operands smaller than $n$ .∎

Intuition. Repeated squaring gets you $a, a^{2}, a^{4}, a^{8}, \dots$ — exponents that double — so after $60$ squarings you have reached $a^{2^{60}}$ . The binary digits of $k$ tell you which of those doubling milestones to keep and multiply together. This is the same doubling trick as binary search or fast integer multiplication by shifts, and it is the reason a $2048$ -bit RSA exponentiation costs a few thousand multiplications instead of $2^{2048}$ of them.

Figure 6.49. Naive exponentiation costs one multiplication per unit of the exponent; square-and-multiply costs at most two per *bit*. The gap is already a factor of ten by

k = 64

and grows without bound.

Example 6.50 (Computing $7^{13} mod 11$ by hand). Evaluate $7^{13} mod 11$ with square-and-multiply, and count the multiplications.

Solution.

$13 = 110 1_{2}$ , so the bits from the top are $1, 1, 0, 1$ .
Start $y = 1$ . Bit $1$ : square to $1$ , multiply by $7$ , giving $y = 7$ ( $= a^{1}$ ).
Bit $1$ : $y = 7^{2} = 49 \equiv 5$ , then $y = 5 \cdot 7 = 35 \equiv 2$ ( $= a^{3}$ ).
Bit $0$ : $y = 2^{2} = 4$ ( $= a^{6}$ ).
Bit $1$ : $y = 4^{2} = 16 \equiv 5$ , then $y = 5 \cdot 7 = 35 \equiv 2$ ( $= a^{13}$ ).
So $7^{13} \equiv 2 (mod 11)$ , using three squarings and three multiplications after the trivial first step — six operations in place of twelve, on numbers never exceeding $49$ .

□

Remark. Hash tables are the other everyday use of this section. A division hash sends a key $k$ to $k mod m$ ; the theory says the result is uniform only if the keys are, and that a modulus sharing a factor with structure in the keys (say $m = 2^{p}$ when keys are pointers, always multiples of $8$ ) collapses the table into a fraction of its buckets. Choosing $m$ to be a prime not close to a power of two is the standard defence, and it is the theorem Inverses exist exactly for coprime residues in disguise: multiplying by a unit modulo a prime permutes the residues, so no bucket is privileged.

Fermat's little theorem

Definition 6.51 (Euler's totient). $φ (n)$ is the number of integers in ${1, 2, \dots, n}$ that are coprime to $n$ . Equivalently, by the theorem Inverses exist exactly for coprime residues, it counts the invertible residues modulo $n$ .

Theorem 6.52 (Fermat's little theorem). Let $p$ be prime and let $a$ be an integer with $p ∤ a$ . Then

a^{p - 1} \equiv 1 (mod p) .

Proof. Consider the $p - 1$ numbers $a, 2 a, \dots, (p - 1) a$ reduced modulo $p$ . None is $\equiv 0$ , since $p ∤ a$ and $p ∤ j$ for $1 \leq j \leq p - 1$ . They are pairwise incongruent: if $ia \equiv ja$ then, since $g cd (a, p) = 1$ , the corollary Cancellation modulo n gives $i \equiv j$ , and both lie in $[1, p - 1]$ , so $i = j$ .

So these $p - 1$ residues are distinct and nonzero, hence are exactly $1, 2, \dots, p - 1$ in some order. Multiplying them together,

a^{p - 1} (p - 1)! \equiv (p - 1)! (mod p) .

Since $p$ is prime, $(p - 1)!$ is coprime to $p$ and may be cancelled, leaving $a^{p - 1} \equiv 1$ .∎

Remark. This is the special case $n = p$ of Euler's theorem, $a^{φ (n)} \equiv 1 (mod n)$ whenever $g cd (a, n) = 1$ , whose proof is the same argument run over the invertible residues instead of all nonzero ones. Both, with the group theory that explains them and the primality tests built on them, are treated at length in Classical Theorems; here we need only the two statements.

Example 6.53 (An exponent reduced by Fermat). Compute $3^{100} mod 7$ .

Solution.

$7$ is prime and $7 ∤ 3$ , so Fermat's little theorem gives $3^{6} \equiv 1 (mod 7)$ .
Write $100 = 6 \cdot 16 + 4$ . Then $3^{100} = (3^{6})^{16} \cdot 3^{4} \equiv 1^{16} \cdot 3^{4} (mod 7)$ .
$3^{4} = 81 = 11 \cdot 7 + 4$ , so $3^{100} \equiv 4 (mod 7)$ .
The exponent dropped from $100$ to $4$ before any work was done — reducing the exponent modulo $p - 1$ is always the first move.

□

Exercises for §6.4 →

6.5The Chinese Remainder Theorem

A number can be described by its remainders against several moduli instead of by its value. The Chinese Remainder Theorem says that when the moduli are pairwise coprime this description loses nothing, and that the translation back is a formula you can run.

Theorem 6.54 (Chinese Remainder Theorem). Let $n_{1}, \dots, n_{k}$ be pairwise coprime positive integers, $N = n_{1} n_{2} \dots n_{k}$ , and let $a_{1}, \dots, a_{k}$ be any integers. Then the system

x \equiv a_{1} (mod n_{1}), \dots, x \equiv a_{k} (mod n_{k})

has a solution, and it is unique modulo $N$ . Explicitly, writing $N_{i} = N / n_{i}$ and letting $y_{i}$ be an inverse of $N_{i}$ modulo $n_{i}$ ,

x \equiv i = 1 \sum k a_{i} N_{i} y_{i} (mod N) .

Proof. The inverses exist. Fix $i$ . For each $j \neq = i$ we have $g cd (n_{i}, n_{j}) = 1$ , and a number coprime to each of several factors is coprime to their product: any prime dividing $n_{i}$ and $N_{i}$ would divide some $n_{j}$ , contradicting coprimality. So $g cd (N_{i}, n_{i}) = 1$ and the theorem Inverses exist exactly for coprime residues supplies $y_{i}$ .

The formula solves the system. Fix $j$ and reduce $x = \sum_{i} a_{i} N_{i} y_{i}$ modulo $n_{j}$ . For $i \neq = j$ the factor $N_{i}$ contains $n_{j}$ , so that term vanishes. The surviving term is $a_{j} N_{j} y_{j} \equiv a_{j} \cdot 1 = a_{j} (mod n_{j})$ , by the defining property of $y_{j}$ . Hence $x \equiv a_{j} (mod n_{j})$ for every $j$ .

Uniqueness. If $x$ and $x^{'}$ both solve the system then $n_{j} ∣ (x - x^{'})$ for every $j$ . The $n_{j}$ are pairwise coprime, so by the theorem gcd and lcm from the factorisations their lcm is their product $N$ , and a number divisible by each $n_{j}$ is divisible by that lcm. Hence $N ∣ (x - x^{'})$ , i.e. $x \equiv x^{'} (mod N)$ .∎

Corollary 6.55 (Splitting a modulus). If $n = n_{1} n_{2}$ with $g cd (n_{1}, n_{2}) = 1$ , the map sending $x mod n$ to the pair $(x mod n_{1}, x mod n_{2})$ is a bijection from $Z_{n}$ to $Z_{n_{1}} \times Z_{n_{2}}$ that preserves sums and products. In particular $φ (n) = φ (n_{1}) φ (n_{2})$ .

Proof. The map is well defined, and it is onto by the existence half of the Chinese Remainder Theorem and one-to-one by its uniqueness half; both sides have $n$ elements. Sums and products are preserved because reduction modulo $n_{1}$ and modulo $n_{2}$ each respect arithmetic, by Arithmetic respects congruence.

For the totient: $x$ is invertible modulo $n$ exactly when $g cd (x, n) = 1$ , which happens exactly when $g cd (x, n_{1}) = 1$ and $g cd (x, n_{2}) = 1$ . So the bijection matches invertible elements with pairs of invertible elements, and counting gives $φ (n) = φ (n_{1}) φ (n_{2})$ .∎

Proposition 6.56 (Totient of a prime and of a semiprime). For a prime $p$ , $φ (p) = p - 1$ . For distinct primes $p \neq = q$ , $φ (pq) = (p - 1) (q - 1)$ .

Proof. Every one of $1, \dots, p - 1$ is coprime to $p$ since $p$ has no divisors strictly between $1$ and $p$ , and $p$ itself is not; so $φ (p) = p - 1$ . The second claim is the corollary Splitting a modulus applied to $n_{1} = p$ , $n_{2} = q$ , which are coprime because they are distinct primes.∎

Intuition. Think of two gears with $n_{1}$ and $n_{2}$ teeth. Coprimality means no tooth alignment repeats until both gears have completed a whole number of turns, so the combined pattern has full period $n_{1} n_{2}$ and every pair of positions occurs exactly once. When the gears share a factor the combined period collapses, some pairs never occur — which is why $x \equiv 0 (mod 2)$ , $x \equiv 1 (mod 4)$ has no solution — and the theorem fails.

Example 6.57 (Reconstructing a number from three remainders). Find the smallest non-negative $x$ with $x \equiv 2 (mod 3)$ , $x \equiv 3 (mod 5)$ , $x \equiv 2 (mod 7)$ , using the constructive formula.

Solution.

$N = 105$ , and $N_{1} = 35$ , $N_{2} = 21$ , $N_{3} = 15$ .
Inverses: $35 \equiv 2 (mod 3)$ and $2 \cdot 2 = 4 \equiv 1$ , so $y_{1} = 2$ . $21 \equiv 1 (mod 5)$ , so $y_{2} = 1$ . $15 \equiv 1 (mod 7)$ , so $y_{3} = 1$ .
Assemble: $x \equiv 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 = 140 + 63 + 30 = 233$ .
Reduce: $233 = 2 \cdot 105 + 23$ , so $x \equiv 23 (mod 105)$ , and the smallest non-negative solution is $23$ .
Check: $23 = 7 \cdot 3 + 2$ , $23 = 4 \cdot 5 + 3$ , $23 = 3 \cdot 7 + 2$ .

□

Example 6.58 (Successive substitution instead of the formula). Solve $x \equiv 4 (mod 9)$ and $x \equiv 7 (mod 11)$ .

Solution.

From the first congruence write $x = 9 t + 4$ and substitute into the second: $9 t + 4 \equiv 7 (mod 11)$ , so $9 t \equiv 3 (mod 11)$ .
Invert $9$ modulo $11$ : $9 \cdot 5 = 45 = 4 \cdot 11 + 1$ , so $9^{- 1} \equiv 5$ . Then $t \equiv 15 \equiv 4 (mod 11)$ .
So $t = 11 s + 4$ and $x = 9 (11 s + 4) + 4 = 99 s + 40$ , i.e. $x \equiv 40 (mod 99)$ .
Check: $40 = 4 \cdot 9 + 4$ and $40 = 3 \cdot 11 + 7$ . By hand, substitution is usually faster than the formula; the formula is what you implement, because it parallelises over $i$ .

□

Remark. CRT is not only an existence theorem, it is an optimisation. RSA private-key operations are routinely performed by reducing modulo $p$ and modulo $q$ separately, exponentiating on numbers half as long, and recombining with the formula above. Since multiplication cost grows faster than linearly in operand length, the two half-size exponentiations together cost roughly a quarter of the full one — a speedup of about four, for free.

Exercises for §6.5 →

6.6RSA: Putting the Toolkit to Work

Everything so far assembles into one system. RSA is worth the last section not because a first-year student will implement it, but because it is the only place where each tool's cost is visibly what makes the scheme possible or impossible: key generation needs primality testing, decryption needs modular inverses and fast exponentiation, and security needs factoring to be slow.

Method 6.59 (RSA key generation, encryption and decryption).

Choose distinct large primes $p, q$ and set $n = pq$ and $φ (n) = (p - 1) (q - 1)$ .
Choose $e$ with $1 < e < φ (n)$ and $g cd (e, φ (n)) = 1$ ; compute $d \equiv e^{- 1} (mod φ (n))$ with extended Euclid.
Publish $(n, e)$ ; keep $d$ (and $p, q$ ) secret.
Encrypt a message $m$ with $0 \leq m < n$ as $c = m^{e} mod n$ ; decrypt as $m = c^{d} mod n$ , both by square-and-multiply.

Theorem 6.60 (Correctness of RSA decryption). Let $p \neq = q$ be primes, $n = pq$ , and let $e, d$ satisfy $e d \equiv 1 (mod φ (n))$ . Then for every integer $m$ with $0 \leq m < n$ ,

(m^{e})^{d} \equiv m (mod n) .

Proof. Write $e d = 1 + k φ (n) = 1 + k (p - 1) (q - 1)$ for some integer $k \geq 0$ , which is possible because $φ (n) ∣ e d - 1$ .

We show $m^{e d} \equiv m (mod p)$ , and the same argument with $q$ in place of $p$ gives $m^{e d} \equiv m (mod q)$ .

If $p ∣ m$ then both sides are $\equiv 0 (mod p)$ and the congruence holds. Otherwise $p ∤ m$ , so Fermat's little theorem applies and $m^{p - 1} \equiv 1 (mod p)$ . Then

m^{e d} = m^{1 + k (p - 1) (q - 1)} = m \cdot (m^{p - 1})^{k (q - 1)} \equiv m \cdot 1^{k (q - 1)} = m (mod p) .

Now $p$ and $q$ both divide $m^{e d} - m$ , and they are distinct primes, hence coprime; by the uniqueness half of the Chinese Remainder Theorem — or directly, since $lcm (p, q) = pq$ — we get $pq = n$ divides $m^{e d} - m$ , that is $m^{e d} \equiv m (mod n)$ .

Finally both $m$ and $m^{e d} mod n$ lie in $[0, n)$ , so the congruence is an equality of representatives and decryption returns exactly the message sent.∎

Notice which case made the proof delicate. The naive argument — " $m^{φ (n)} \equiv 1$ by Euler, so $m^{e d} = m \cdot (m^{φ (n)})^{k} \equiv m$ " — needs $g cd (m, n) = 1$ and therefore says nothing about messages that happen to be divisible by $p$ or by $q$ . Splitting into the two prime moduli and handling $p ∣ m$ separately is what upgrades the statement to every $m$ , which is what a correct decryption routine requires: a cryptosystem that fails on a one-in- $n$ set of messages is still broken.

Example 6.61 (A complete RSA round trip). Take $p = 11$ , $q = 13$ , $e = 7$ . Find $d$ , then encrypt $m = 9$ and decrypt the result.

Solution.

$n = 143$ and $φ (n) = 10 \cdot 12 = 120$ . Since $g cd (7, 120) = 1$ , the exponent $e = 7$ is legal.
Extended Euclid on $(7, 120)$ : $120 = 17 \cdot 7 + 1$ , so $1 = 120 - 17 \cdot 7$ , giving $7^{- 1} \equiv - 17 \equiv 103 (mod 120)$ . So $d = 103$ .
Encrypt: $9^{7} mod 143$ . By square-and-multiply with $7 = 11 1_{2}$ : $9^{1} = 9$ , then $9^{2} = 81$ , $81 \cdot 9 = 729 \equiv 14$ (as $729 = 5 \cdot 143 + 14$ ), then $1 4^{2} = 196 \equiv 53$ , $53 \cdot 9 = 477 \equiv 48$ . So $c = 48$ .
Decrypt: $4 8^{103} mod 143$ . Rather than grind, use the theorem Correctness of RSA decryption — $e d = 721 = 1 + 6 \cdot 120$ , so $4 8^{103} \equiv 9$ .
Check the theorem's hypothesis really is met: $g cd (9, 143) = 1$ here, but the proof did not need it.

□

Example 6.62 (Breaking a small key). The public key is $(n, e) = (3233, 17)$ . Recover $d$ .

Solution.

Factor $n$ by trial division: $3233 \approx 56.9$ , and testing primes finds $3233 = 53 \cdot 61$ .
Hence $φ (n) = 52 \cdot 60 = 3120$ .
Invert $e$ : extended Euclid on $(17, 3120)$ gives $17 \cdot 2753 = 46801 = 15 \cdot 3120 + 1$ , so $d = 2753$ .
The entire attack is three lines because $n$ has four digits. At $2048$ bits step 1 is the wall — the security of the scheme is exactly the statement that factoring stays on the wrong side of the $n$ versus $lo g n$ divide from the first section.

□

Pitfall. Textbook RSA as stated here is deterministic: the same message always encrypts to the same ciphertext, so an eavesdropper who suspects the plaintext can simply encrypt their guess and compare. Real deployments pad the message with randomness before exponentiating (OAEP). The mathematics of this section is correct and is not, by itself, a secure cryptosystem.

Exercises for §6.6 →

Common Mistakes

Treating $1$ as prime. It is a unit, and admitting it would destroy uniqueness of factorisation.
Believing Euclid's proof shows $p_{1} \dots p_{k} + 1$ is prime. It shows only that its prime factors are new; $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 59 \cdot 509$ .
Stopping trial division at $n /2$ instead of $n$ , or writing d <= sqrt(n) in floating point where d*d <= n is exact.
Confusing the statement $d ∣ a$ with the number $a / d$ . The bar is a relation, not an operation.
Calling the Euclidean algorithm fast because the numbers get small, then computing the gcd by factoring anyway. Factoring is the expensive step you were avoiding.
Quoting the running time as $O (lo g n)$ arithmetic operations and then claiming $O (lo g n)$ bit operations. Each division on $ℓ$ -bit numbers costs more than constant time.
Sign errors in the extended algorithm. Always check the final row against $a x + b y = g cd$ before using it.
Cancelling a common factor in a congruence without checking that it is coprime to the modulus.
Asserting that $a x \equiv b (mod n)$ always has a solution, or that it has only one when $g cd (a, n) > 1$ . It has $g cd (a, n)$ solutions, or none.
Reducing the exponent modulo $n$ rather than modulo $φ (n)$ (or $p - 1$ ) in a modular power. Bases reduce mod $n$ ; exponents do not.
Reporting a negative remainder from a language whose % follows the dividend's sign, instead of normalising into ${0, \dots, n - 1}$ .
Applying CRT to moduli that are not pairwise coprime, and being surprised by no solution or by solutions modulo the lcm rather than the product.
Choosing RSA exponents with $g cd (e, φ (n)) \neq = 1$ , which leaves $e$ non-invertible and the key pair unusable.
Computing $φ (n)$ as $n - 1$ for a composite $n$ . That formula is for primes; for $n = pq$ it is $(p - 1) (q - 1)$ .

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