Chapter 22: Number Theory Foundations

"Mathematics is the queen of the sciences, and number theory is the queen of mathematics." — attributed to Carl Friedrich Gauss

Overview

Here is a fact that should feel impossible. Every time your browser opens a connection to your bank, two computers that have never met agree on a shared secret in public — an eavesdropper can record every byte they exchange and still cannot recover the secret. The mathematics that makes this possible is not some exotic 21st-century invention. It is the theory of how integers divide each other, a subject the ancient Greeks studied for its own beauty and that the number theorist G. H. Hardy, in 1940, proudly called useless. He was spectacularly wrong. The "useless" arithmetic of primes and remainders turned out to secure the entire internet.

This chapter is where that story begins. We will not reach RSA itself for three more chapters — first we have to build the machinery — but every tool we forge here is a part RSA needs. By the end you will be able to find the greatest common divisor of two thousand-digit numbers in a fraction of a second, prove that the primes never run out, and break any integer into its unique atomic factors. These are not separate party tricks. They are a single connected theory, and the connective tissue is one humble idea: divisibility.

Why does a programmer need this, beyond the cryptography payoff? Because divisibility and remainders are everywhere in code. Hash tables shrink a key into a bucket with key % table_size. A circular buffer wraps with modular arithmetic. You decide whether a year is a leap year by asking what divides it. You distribute work across $k$ threads by remainder. You generate the primes that size a hash table. Underneath all of it sits the arithmetic we make rigorous here — and once it is rigorous, you can reason about it instead of guessing.

In this chapter, you will learn to:

• Use the precise definition of divisibility to prove its fundamental properties.
• Generate all primes up to a bound with the Sieve of Eratosthenes, and prove there are infinitely many primes.
• Apply the Division Algorithm to get a unique quotient and remainder — and understand what Python's % actually computes.
• Compute greatest common divisors with the Euclidean algorithm, one of the oldest non-trivial algorithms still in daily use.
• Find Bézout coefficients with the extended Euclidean algorithm, the key that unlocks modular inverses in the next chapter.
• State and apply the Fundamental Theorem of Arithmetic: every integer above 1 factors into primes in exactly one way.

Learning Paths

🏃 Fast Track: If divisibility and gcd are old friends, skim 22.1–22.3, then concentrate on 22.5 (Bézout and the extended Euclidean algorithm) — it is the part most directly used by RSA and the part most people have not seen. Do the ⭐⭐ and ⭐⭐⭐ exercises.

📖 Standard Path: Read in order. Each section moves concrete example → definition → proof → code. Work every 🔄 Check Your Understanding before continuing, and try to write the gcd proof in 22.4 yourself before reading ours.

🔬 Deep Dive: After the chapter, prove that the Euclidean algorithm runs in $O(\log(\min(a,b)))$ steps (the worst case is consecutive Fibonacci numbers — a lovely callback to Chapter 6), and prove Euclid's lemma directly from Bézout. The exercise set's Part E sets this up.

22.1 Divisibility

Start with something you have done since grade school: checking whether one number goes evenly into another. Does 7 divide 91? Yes — $91 = 7 \times 13$, no remainder. Does 7 divide 90? No — you get 12 with 6 left over. That "no remainder" relationship is the foundation of everything in this chapter, and our first job is to state it with enough precision that we can prove things about it.

Notice what "7 divides 91" really claims: there exists a third integer (namely 13) that, multiplied by 7, gives 91. That existential phrasing is the key. It turns a vague notion ("goes evenly") into an equation we can manipulate.

Definition (divisibility). Let $a$ and $b$ be integers with $a \neq 0$. We say $a$ divides $b$, written $a \mid b$, if there exists an integer $k$ such that $b = ak$. When $a \mid b$ we call $a$ a divisor (or factor) of $b$, and $b$ a multiple of $a$. If no such integer exists we write $a \nmid b$.

You met this definition briefly back in Chapter 4, where it served as raw material for your first direct proofs about even and odd numbers. Now it takes center stage. The single most important habit in this entire chapter is this: the moment you see $a \mid b$, rewrite it as $b = ak$ for some integer $k$. The vertical bar is a claim about existence; the equation is something you can do algebra with.

⚠️ Common Pitfall: The notation $a \mid b$ is a statement (true or false), not a number. Do not confuse it with the fraction $a/b$ or the remainder operation $b \bmod a$. "$3 \mid 12$" is a true proposition; "$12 / 3$" is the number 4; "$12 \bmod 3$" is the number 0. Reading $a \mid b$ as "$a$ over $b$" is the most common beginner error, and it reverses the roles — $3 \mid 12$ means 3 is the smaller divisor, not $3/12$.

Let's immediately put the definition to work by proving a property you will use constantly.

A first proof: divisibility is transitive

Claim. For all integers $a, b, c$ (with $a, b \neq 0$): if $a \mid b$ and $b \mid c$, then $a \mid c$.

The strategy first. This is a direct proof, and the recipe is exactly the one Chapter 4 drilled: unpack each hypothesis into its equation, combine the equations, then repackage the result back into the definition of divisibility. We have two "exists" hypotheses, so we get two equations with two unknown integers. The whole proof is: substitute one into the other and read off the witness.

Proof. Assume $a \mid b$ and $b \mid c$. By the definition of divisibility, there exist integers $j$ and $k$ with $$b = aj \quad\text{and}\quad c = bk.$$ Substituting the first equation into the second, $$c = bk = (aj)k = a(jk).$$ Since $j$ and $k$ are integers, so is their product $jk$. Thus there exists an integer — namely $jk$ — that multiplies $a$ to give $c$. By the definition of divisibility, $a \mid c$. $\blacksquare$

That proof is short, but look at its shape, because every elementary divisibility proof has it: unpack, combine, repackage. The creativity is never in the logic; it is in seeing which equations to combine. Here is a second example that adds one small algebraic step.

Claim (divisibility respects linear combinations). If $a \mid b$ and $a \mid c$, then for all integers $m$ and $n$, $a \mid (mb + nc)$.

The strategy first. Same recipe. Unpack the two hypotheses, then factor out $a$ from the combination $mb + nc$. The phrase "linear combination" is just bookkeeping for "any integer multiple of $b$ plus any integer multiple of $c$" — which is exactly the kind of expression Bézout's identity will hand us in 22.5, so this little lemma is doing quiet setup.

Proof. Assume $a \mid b$ and $a \mid c$. Then $b = aj$ and $c = ak$ for some integers $j, k$. For any integers $m, n$, $$mb + nc = m(aj) + n(ak) = a(mj + nk).$$ Since $mj + nk$ is an integer, $a \mid (mb + nc)$. $\blacksquare$

It helps to picture the multiples of $a$ as evenly spaced marks on the number line: $\dots, -2a, -a, 0, a, 2a, \dots$. The lemma says that set is closed under adding and scaling — combine any marks however you like and you land on another mark. That closure is the reason divisibility behaves so predictably, and it is the seed of the group and ring structure you will meet in Chapter 24.

A few small facts round out the basics; each follows directly from the definition (the exercises ask you to prove them):

• $a \mid 0$ for every nonzero $a$ (take $k = 0$, since $0 = a \cdot 0$).
• $1 \mid b$ for every $b$, and $a \mid a$ for every nonzero $a$.
• If $a \mid b$ and $b \neq 0$, then $\lvert a\rvert \le \lvert b\rvert$. (A nonzero multiple cannot be smaller in size than its divisor — a fact we will lean on to prove the Euclidean algorithm terminates.)

def divides(a, b):
    """Return True iff a divides b (a != 0)."""
    return b % a == 0

def divisors(n):
    """All positive divisors of a positive integer n."""
    return [d for d in range(1, n + 1) if n % d == 0]

print(divides(3, 12))    # 3 | 12 ?
print(divisors(12))
# Expected output:
# True
# [1, 2, 3, 4, 6, 12]

The divisors function is deliberately naive — it tries every candidate up to $n$. You could stop at $\sqrt{n}$ (divisors come in pairs $d$ and $n/d$), and the exercises ask you to. But notice the deeper point: to list the divisors of $n$ we are essentially asking which numbers go into it — and the most informative answer to that question is the prime factorization, which is where 22.2 and 22.6 are headed.

🔄 Check Your Understanding 1. Translate "$6 \mid n$" into an equation with an explicit integer witness. 2. True or false: if $a \mid b$ then $b \mid a$. Justify with the definition or a counterexample. 3. Using only the definition, why is it true that $a \mid 0$ for every nonzero $a$, but $0 \nmid b$ for every $b \neq 0$?

Answers

1. "$6 \mid n$" means $n = 6k$ for some integer $k$. 2. False. $3 \mid 12$ but $12 \nmid 3$ (there is no integer $k$ with $3 = 12k$). Divisibility is not symmetric. 3. $a \mid 0$ because $0 = a \cdot 0$ and $0$ is an integer, so $k=0$ is a witness. But $0 \nmid b$ for $b \neq 0$ because $b = 0 \cdot k = 0$ would be required, impossible when $b \neq 0$ — and this is exactly why the definition demands $a \neq 0$.

22.2 Primes and the Sieve of Eratosthenes

Some integers are indecomposable: you cannot write them as a product of two smaller positive integers. Seven is like this; its only divisors are 1 and 7. Twelve is not; it splits as $3 \times 4$. The indecomposable numbers are the atoms of multiplication, and they have a name.

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

That last sentence is not a footnote; it is a load-bearing decision. We will see in 22.6 that excluding 1 from the primes is exactly what makes prime factorization unique. 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 "factorizations," and the Fundamental Theorem would collapse. Definitions in mathematics are chosen to make the good theorems true. A useful mental image: the primes are the multiplicatively "unsplittable" integers — a prime workload cannot be divided evenly among any number of workers strictly between 1 and itself.

Finding all the primes up to $n$: the Sieve of Eratosthenes

How would you list every prime below 30? You could test each number for primality one at a time. But around 240 BCE, the Greek scholar Eratosthenes found something far cleverer, and it is still the fastest simple method today. The idea is to work by elimination rather than by testing: write down every number, then repeatedly cross out the multiples of each prime you find. Whatever survives is prime.

Concretely, to sieve up to 30:

1. List $2, 3, 4, \dots, 30$.
2. The first uncrossed number is 2 — it's prime. Cross out every later multiple of 2: $4, 6, 8, \dots, 30$.
3. The next uncrossed number is 3 — prime. Cross out $6, 9, 12, \dots$ (some already gone).
4. Next uncrossed is 5 — prime. Cross out $10, 15, 20, 25, 30$.
5. Next uncrossed is 7. But $7^2 = 49 > 30$, so we can stop crossing: every remaining composite below 30 has already been crossed by a smaller prime factor.

What remains uncrossed — $2, 3, 5, 7, 11, 13, 17, 19, 23, 29$ — are the ten primes below 30.

Why can we stop once the current prime's square exceeds $n$? Because if a number $m \le n$ is composite, it has a prime factor $p \le \sqrt{m} \le \sqrt{n}$ (we prove this fact, "every composite has a small prime factor," below). So every composite is crossed out by a prime at most $\sqrt{n}$; once we pass $\sqrt{n}$, nothing uncrossed is left to cross. This is why the inner loop starts at $p^2$, not $2p$: every smaller multiple of $p$ already carries a smaller prime factor and was crossed earlier.

def sieve(n):
    """Return all primes p with 2 <= p <= n."""
    if n < 2:
        return []
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p <= n:
        if is_prime[p]:
            for multiple in range(p * p, n + 1, p):
                is_prime[multiple] = False
        p += 1
    return [i for i in range(2, n + 1) if is_prime[i]]

print(sieve(30))
print(len(sieve(100)))
# Expected output:
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
# 25

The sieve runs in about $O(n \log \log n)$ time — very nearly linear — which is why it is the tool of choice when you need all primes up to a bound (sizing hash tables, precomputing for number-theoretic algorithms). When you instead need to test whether a single large number is prime — as RSA key generation does, with numbers hundreds of digits long — the sieve is hopeless and you need a different, probabilistic approach. We will meet that idea (via Fermat's little theorem) in Chapter 23.

🔗 Connection. The sieve foreshadows RSA's appetite for primes. To make a 2048-bit RSA key you need two random primes of about 1024 bits each. You cannot sieve up to a 1024-bit bound — there are more numbers there than atoms in the universe. The schedule of this book is exactly the schedule of solving that problem: Chapter 15 sized the keyspace; here we define primes and generate small ones; Chapter 23 gives a fast primality test; Chapter 25 puts it all together.

The first great theorem: there are infinitely many primes

We can list primes, but do they ever stop? Could there be a largest prime, beyond which every number is composite? Euclid answered this around 300 BCE with one of the most celebrated proofs in all of mathematics — and it is a proof by contradiction, the technique from Chapter 5.

Theorem (Euclid). There are infinitely many primes.

The strategy first. This is the signature shape from Chapter 5: assume the opposite and watch it collapse. Assume there are only finitely many primes, so we can list all of them. Then we manufacture a number that is too stubborn to be divisible by any prime on the list — yet every integer above 1 must have a prime divisor. That contradiction means the list could not have been complete. The clever construction is "multiply them all together and add 1."

We need one supporting fact, which is worth stating on its own because we also used it to justify the sieve.

Lemma (every integer above 1 has a prime divisor). Every integer $n > 1$ is divisible by some prime.

Proof of the lemma (by strong induction on $n$, from Chapter 6's family of techniques). If $n$ is prime, then $n \mid n$ and we are done ($n$ is its own prime divisor). If $n$ is composite, then $n = ab$ with $1 < a < n$. By the inductive hypothesis (the statement holds for all integers strictly between 1 and $n$), $a$ has a prime divisor $p$; so $p \mid a$ and $a \mid n$, hence $p \mid n$ by transitivity (22.1). Either way $n$ has a prime divisor. $\blacksquare$

Now the main event.

Proof of Euclid's theorem. Suppose, for contradiction, that there are only finitely many primes, and list them all: $p_1, p_2, \dots, p_r$. Consider the number $$N = p_1 p_2 \cdots p_r + 1.$$ Since $N > 1$, by the lemma it has some prime divisor $q$. Because our list is supposedly all the primes, $q$ must be one of them, say $q = p_i$. Then $q$ divides the product $p_1 p_2 \cdots p_r$ (it's one of the factors), and by assumption $q$ also divides $N$. By the linear-combination lemma of 22.1, $q$ divides their difference: $$q \mid \big(N - p_1 p_2 \cdots p_r\big) = 1.$$ But the only positive divisor of 1 is 1, and $q$ is a prime, so $q \ge 2$. A prime cannot divide 1 — contradiction. Therefore our assumption was false: there is no finite list of all primes, so there are infinitely many. $\blacksquare$

⚠️ Common Pitfall: A frequent misreading is that "$N = p_1 \cdots p_r + 1$ is always prime." It is not. For example, $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \times 509$. The proof never claims $N$ is prime — it claims $N$ has a prime divisor that isn't on the list. Euclid's number manufactures a new prime, not necessarily itself.

🔄 Check Your Understanding 1. Why is 1 excluded from the primes? Give the one-sentence reason in terms of factorization. 2. In the sieve, why does the inner loop start crossing out at $p^2$ rather than $2p$? 3. In Euclid's proof, we concluded $q \mid 1$. Which lemma from 22.1 let us deduce $q \mid (N - p_1\cdots p_r)$, and why is "$q \mid 1$" the contradiction?

Answers

1. So that prime factorization is unique; allowing 1 would let you insert any number of factors of 1. 2. Every composite multiple of $p$ below $p^2$ has a smaller prime factor and was already crossed out by that smaller prime, so starting at $p^2$ avoids redundant work. 3. The linear-combination lemma ($a \mid b$ and $a \mid c$ imply $a \mid (mb + nc)$, here with the combination $N - 1\cdot(p_1\cdots p_r)$). "$q \mid 1$" is a contradiction because a prime is at least 2, and no integer $\ge 2$ divides 1.

22.3 The Division Algorithm

Every divisibility question secretly asks "what is the remainder?" When $a \mid b$, the remainder is zero; otherwise it is something between. To reason about remainders rigorously — and to build the Euclidean algorithm — we need a theorem that pins them down exactly. Despite its name, the "Division Algorithm" is really a theorem about existence and uniqueness; it is the formal backbone of grade-school long division.

Theorem (the Division Algorithm). Let $a$ be an integer and $d$ a positive integer. Then there exist unique integers $q$ (the quotient) and $r$ (the remainder) such that $$a = dq + r \qquad\text{and}\qquad 0 \le r < d.$$

The conditions $0 \le r < d$ are what make $q$ and $r$ unique; without them you could shift the quotient up or down and absorb the change into the remainder. Let's prove both halves, because the proof teaches you how to use the theorem.

The strategy first. For existence we want the right remainder. The remainder is "what's left after we subtract off as many copies of $d$ as fit." So consider all the numbers $a - dq$ as $q$ ranges over the integers; among the non-negative ones, take the smallest. That smallest non-negative leftover is forced to be below $d$ (otherwise we could subtract one more $d$), and it is our $r$. The tool that guarantees a smallest non-negative value exists is the well-ordering principle from Chapter 6's circle of ideas. For uniqueness we use the standard move: suppose two representations exist and show they must coincide.

Proof. Existence. Consider the set $S = \{\, a - dq : q \in \mathbb{Z} \text{ and } a - dq \ge 0 \,\}$ of non-negative leftovers. This set is non-empty (choosing a sufficiently negative $q$ makes $a - dq$ as large and positive as we like). By the well-ordering principle, $S$ has a least element; call it $r = a - dq$ for the corresponding $q$. By construction $r \ge 0$. We claim $r < d$. If instead $r \ge d$, then $$a - d(q+1) = (a - dq) - d = r - d \ge 0,$$ so $r - d$ is also in $S$ — but $r - d < r$, contradicting that $r$ was the least element of $S$. Hence $0 \le r < d$, and $a = dq + r$ as required.

Uniqueness. Suppose $a = dq_1 + r_1 = dq_2 + r_2$ with $0 \le r_1, r_2 < d$. Subtracting, $$d(q_1 - q_2) = r_2 - r_1.$$ The left side is a multiple of $d$, so $d \mid (r_2 - r_1)$. But since $0 \le r_1, r_2 < d$, their difference satisfies $-d < r_2 - r_1 < d$. The only multiple of $d$ strictly between $-d$ and $d$ is $0$, so $r_2 - r_1 = 0$, giving $r_1 = r_2$. Then $d(q_1 - q_2) = 0$ and $d > 0$ force $q_1 = q_2$. The representation is unique. $\blacksquare$

This is the theorem behind two operators you use every day. In Python, a // d is $q$ and a % d is $r$, and — crucially — Python guarantees the canonical non-negative remainder even when $a$ is negative:

def divmod_check(a, d):
    q, r = a // d, a % d
    assert a == d * q + r and 0 <= r < d   # the theorem, asserted
    return q, r

for a, d in [(17, 5), (-17, 5), (42, 7)]:
    print(f"{a} = {d}*({a//d}) + {a % d}")
# Expected output:
# 17 = 5*(3) + 2
# -17 = 5*(-4) + 3
# 42 = 7*(6) + 0

⚠️ Common Pitfall: Not every language agrees on the remainder of a negative dividend! Python's % follows the Division Algorithm and always returns $r$ with $0 \le r < d$ (so -17 % 5 == 3). C, C++, and Java instead make the remainder take the sign of the dividend (so -17 % 5 == -2 there). Both satisfy a == d*q + r, but only Python's matches the theorem's $0 \le r < d$. When you port modular code between languages, this is a classic source of off-by-a-modulus bugs. When in doubt, normalize with ((a % d) + d) % d.

🔗 Connection. The Division Algorithm is the foundation of modular arithmetic, the entire subject of Chapter 23. "$a \bmod n$" is precisely the remainder $r$ this theorem guarantees, and "$a \equiv b \pmod n$" will mean $a$ and $b$ leave the same remainder. Everything in the next chapter — congruences, modular inverses, RSA's encryption step — is built on the unique $(q, r)$ we just established exists.

22.4 The Euclidean Algorithm

Now we reach the heart of the chapter. The greatest common divisor of two integers is the largest integer dividing both. It is everywhere: reducing a fraction $\frac{252}{198}$ to lowest terms means dividing out their gcd; tiling a $252 \times 198$ floor with the largest possible square tiles means using $\gcd(252,198)$-sized tiles; and — the reason it earns a place in Part IV — computing a modular inverse for RSA decryption requires it.

Definition (greatest common divisor). For integers $a$ and $b$, not both zero, the greatest common divisor $\gcd(a, b)$ is the largest integer $d$ such that $d \mid a$ and $d \mid b$. By convention $\gcd(0, 0) = 0$. Two integers are coprime (or relatively prime) if $\gcd(a, b) = 1$ — they share no prime factor.

How do you compute a gcd? The naive way is to factor both numbers and multiply the common prime powers (we will justify this in 22.6). But factoring large numbers is brutally slow — so slow that RSA's security depends on it. Fortunately, there is a way to find the gcd without factoring at all, and it is breathtakingly fast. It rests on one clean observation.

The key lemma. For integers $a$ and $b > 0$, if $a = bq + r$ (the Division Algorithm), then $$\gcd(a, b) = \gcd(b, r).$$

The strategy first. To prove two gcds are equal, the cleanest route is to show the two pairs have exactly the same set of common divisors — if every common divisor of $(a,b)$ is also a common divisor of $(b,r)$ and vice versa, then in particular their greatest common divisors match. So we prove the two divisibility implications, each a one-line application of the linear-combination lemma from 22.1.

Proof. We show $(a, b)$ and $(b, r)$ have the same common divisors. Let $c$ be any common divisor of $a$ and $b$. Since $r = a - bq$, the linear-combination lemma (22.1) gives $c \mid (a - bq) = r$; so $c$ is a common divisor of $b$ and $r$. Conversely, let $c$ be any common divisor of $b$ and $r$. Since $a = bq + r$, the same lemma gives $c \mid (bq + r) = a$; so $c$ divides $a$ and $b$. The two pairs share every common divisor, hence they share the greatest one: $\gcd(a, b) = \gcd(b, r)$. $\blacksquare$

This lemma is an engine. It says: to find $\gcd(a, b)$, replace $b$ by the smaller number $a \bmod b$ and repeat. The numbers shrink every step (the remainder is strictly smaller than the divisor), so eventually the remainder hits 0 — and $\gcd(g, 0) = g$, since every integer divides 0 and the largest divisor of $g$ is $g$ itself. That last nonzero remainder is the gcd. This is the Euclidean algorithm, written down by Euclid around 300 BCE and arguably the oldest algorithm still in everyday use.

Let's trace $\gcd(252, 198)$ by hand:

$$ \begin{aligned} \gcd(252, 198):\quad 252 &= 1 \cdot 198 + 54 \\ \gcd(198, 54):\quad 198 &= 3 \cdot 54 + 36 \\ \gcd(54, 36):\quad 54 &= 1 \cdot 36 + 18 \\ \gcd(36, 18):\quad 36 &= 2 \cdot 18 + 0 \end{aligned} $$

The last nonzero remainder is $18$, so $\gcd(252, 198) = 18$. Check: $252 = 18 \cdot 14$ and $198 = 18 \cdot 11$, and $\gcd(14, 11) = 1$, so 18 really is the greatest common divisor. Notice we never factored anything — we only divided, four times.

def gcd(a, b):
    a, b = abs(a), abs(b)
    while b != 0:
        a, b = b, a % b
    return a

print(gcd(252, 198))
print(gcd(17, 5))    # coprime
print(gcd(0, 5))     # gcd(0, b) = b
# Expected output:
# 18
# 1
# 5

Two things deserve a proof-level remark, because "it obviously works" is exactly the gap this book exists to close.

Why it terminates. Each iteration replaces the pair $(a, b)$ with $(b, a \bmod b)$, and by the Division Algorithm $0 \le (a \bmod b) < b$. So the second component is a strictly decreasing sequence of non-negative integers. A strictly decreasing sequence of non-negative integers cannot go on forever (well-ordering again, from Chapter 6's circle), so $b$ reaches 0 and the loop halts.

Why it's correct. Every iteration preserves the gcd, by the key lemma — $\gcd(a, b) = \gcd(b, a \bmod b)$ holds at each step. So the gcd of the original pair equals the gcd of the final pair $(g, 0)$, which is $g$. The value returned is exactly $\gcd$ of the inputs.

💡 Intuition: The Euclidean algorithm is "subtract the smaller from the larger, repeatedly" — sped up. If you literally subtracted $b$ from $a$ over and over until you dropped below $b$, you would be computing $a \bmod b$ the slow way. The modulo does all those subtractions in one step. That's why it's fast even on enormous inputs.

How fast? The number of steps is $O(\log(\min(a, b)))$ — logarithmic, so even thousand-digit inputs finish in a few thousand divisions. The provable worst case is strikingly beautiful: the inputs that force the most steps relative to their size are consecutive Fibonacci numbers, $\gcd(F_{n+1}, F_n)$, which takes $n-1$ steps. (Try $\gcd(13, 8)$: it runs $13 = 1\cdot8+5$, $8=1\cdot5+3$, $5=1\cdot3+2$, $3=1\cdot2+1$, $2=2\cdot1+0$ — five steps, with every quotient equal to 1.) This is the same Fibonacci sequence you proved facts about by induction in Chapter 6, resurfacing as the stress test of an algorithm — a small reminder that the threads of this book are tied together.

🔗 Connection. This logarithmic speed is why RSA is practical at all. RSA decryption needs a modular inverse, the modular inverse needs Bézout coefficients (next section), and Bézout coefficients come straight out of the Euclidean algorithm. If the only way to get a gcd were to factor, RSA's own decryption would be as hard as the attack it's supposed to resist. The Euclidean algorithm threads the needle: gcd is easy, factoring is hard, and the whole edifice of public-key crypto lives in that gap.

🔄 Check Your Understanding 1. Run the Euclidean algorithm by hand to find $\gcd(48, 18)$. Show each division step. 2. The algorithm returns the last nonzero remainder. Why is the final pair always of the form $(g, 0)$, and why is $\gcd(g, 0) = g$? 3. Without computing it, is $\gcd(F_{10}, F_{9})$ likely to take few or many steps relative to the size of the numbers? Why?

Answers

1. $48 = 2\cdot18 + 12$; $18 = 1\cdot12 + 6$; $12 = 2\cdot6 + 0$. Last nonzero remainder is $6$, so $\gcd(48,18)=6$. 2. The remainders strictly decrease and stay $\ge 0$, so they reach $0$; the step before reaching $0$ leaves $(g, 0)$. $\gcd(g, 0) = g$ because every integer divides $0$, so the common divisors of $g$ and $0$ are just the divisors of $g$, the greatest of which is $g$. 3. Many steps relative to size — consecutive Fibonacci numbers are the worst case for the Euclidean algorithm (every quotient is 1), so $\gcd(F_{10}, F_9)$ takes the maximum number of steps for numbers that size.

22.5 Bézout's Identity and the Extended Euclidean Algorithm

The Euclidean algorithm tells you what the gcd is. A small extension tells you something far more powerful: how to write the gcd as a combination of the two inputs. This is the single most important computational tool in the chapter, because it is exactly what modular inverses (and therefore RSA decryption) are built on.

Look again at the divisions for $\gcd(252, 198) = 18$. The claim of this section is that we can always find integers $x$ and $y$ — possibly negative — with $252x + 198y = 18$. And indeed $252 \cdot 4 + 198 \cdot (-5) = 1008 - 990 = 18$. That is no coincidence.

Theorem (Bézout's identity). For any integers $a$ and $b$, not both zero, there exist integers $x$ and $y$ such that $$ax + by = \gcd(a, b).$$ The integers $x, y$ are called Bézout coefficients. Equivalently: $\gcd(a, b)$ is the smallest positive integer expressible as an integer combination $ax + by$.

The strategy first. There is a slick existence proof using well-ordering: let $d$ be the smallest positive value of $ax + by$ over all integers $x, y$, and show (via the Division Algorithm) that $d$ divides both $a$ and $b$, hence $d = \gcd(a,b)$. We give that proof because it is beautiful and explains why the identity is true. But for computing the coefficients we use a constructive method — the extended Euclidean algorithm — because a programmer wants the actual $x$ and $y$, not just a promise they exist.

Proof (existence, via well-ordering). Consider the set $$S = \{\, ax + by : x, y \in \mathbb{Z} \text{ and } ax + by > 0 \,\}$$ of all positive integer combinations of $a$ and $b$. Since $a, b$ are not both zero, $S$ is non-empty (e.g. $a \cdot a + b \cdot b = a^2 + b^2 > 0$). By the well-ordering principle, $S$ has a least element $d = ax_0 + by_0$ for some integers $x_0, y_0$. We claim $d = \gcd(a, b)$.

First, $d \mid a$. By the Division Algorithm write $a = dq + r$ with $0 \le r < d$. Then $$r = a - dq = a - q(ax_0 + by_0) = a(1 - qx_0) + b(-qy_0),$$ so $r$ is itself an integer combination of $a$ and $b$. If $r > 0$, then $r \in S$ and $r < d$, contradicting minimality of $d$. So $r = 0$, meaning $d \mid a$. The identical argument shows $d \mid b$. Thus $d$ is a common divisor of $a$ and $b$, so $d \le \gcd(a, b)$.

Conversely, any common divisor $c$ of $a$ and $b$ divides the combination $ax_0 + by_0 = d$ (linear-combination lemma, 22.1), so $c \le d$; in particular $\gcd(a, b) \le d$. Combining, $d = \gcd(a, b)$. $\blacksquare$

🚪 Threshold Concept. Bézout's identity is the hinge on which all of public-key cryptography turns, and it is worth pausing on why. In Chapter 23 you will want to "divide" in modular arithmetic — to undo a multiplication mod $n$. There is no fraction available; instead you need a modular inverse of $a$ mod $n$, an integer $a^{-1}$ with $a \cdot a^{-1} \equiv 1 \pmod n$. Bézout says: if $\gcd(a, n) = 1$, there are integers $x, y$ with $ax + ny = 1$. Read that modulo $n$ and the $ny$ term vanishes: $ax \equiv 1 \pmod n$. So $x$ is the modular inverse. The existence of modular inverses — the operation that decrypts RSA — is literally Bézout's identity, viewed mod $n$. Once you see this, the rest of Part IV stops feeling like a pile of tricks and becomes one idea unfolding.

Computing the coefficients: the extended Euclidean algorithm

The existence proof doesn't hand us $x$ and $y$. To get them, we run the Euclidean algorithm and carry the coefficients along. The cleanest formulation is recursive, and it mirrors the gcd recursion exactly.

The base case is $\gcd(a, 0) = a$, witnessed by $a \cdot 1 + 0 \cdot 0 = a$ — so $(x, y) = (1, 0)$. For the recursive case, suppose we already have coefficients for the smaller problem $\gcd(b, a \bmod b)$: that is, integers $x', y'$ with $$b x' + (a \bmod b)\, y' = g.$$ Now substitute the Division Algorithm fact $a \bmod b = a - \lfloor a/b\rfloor\, b$: $$g = bx' + \left(a - \left\lfloor \tfrac{a}{b}\right\rfloor b\right) y' = a\,y' + b\left(x' - \left\lfloor \tfrac{a}{b}\right\rfloor y'\right).$$ Reading off the coefficients of $a$ and $b$, the answer for the original problem is $$x = y', \qquad y = x' - \left\lfloor \tfrac{a}{b}\right\rfloor y'.$$ That single back-substitution rule is the whole algorithm.

def ext_gcd(a, b):
    """Return (g, x, y) with g = gcd(a, b) and a*x + b*y = g."""
    if b == 0:
        return (a, 1, 0)
    g, x1, y1 = ext_gcd(b, a % b)
    return (g, y1, x1 - (a // b) * y1)

g, x, y = ext_gcd(252, 198)
print((g, x, y))
print(252 * x + 198 * y)     # verifies a*x + b*y == g
# Expected output:
# (18, 4, -5)
# 18

Let's confirm the trace produces $(18, 4, -5)$, because watching the coefficients propagate back up is the best way to trust the code. Going down the recursion mirrors the gcd divisions; coming back up, we apply $x = y'$, $y = x' - \lfloor a/b\rfloor y'$ at each level:

And the verification: $252 \cdot 4 + 198 \cdot (-5) = 1008 - 990 = 18 = \gcd(252, 198)$. The coefficients are not unique — adding $\frac{b}{g}$ to $x$ and subtracting $\frac{a}{g}$ from $y$ gives another valid pair — but the extended Euclidean algorithm always returns one concrete pair, which is all a modular-inverse computation needs.

⚠️ Common Pitfall: Bézout coefficients are almost always signed, and beginners panic when a coefficient comes out negative. That is expected and fine. For a modular inverse you then reduce the relevant coefficient modulo $n$ to land it in the range $[0, n)$ — e.g. a coefficient of $-5$ modulo $198$ becomes $193$. The negativity is a feature of working over the integers; the reduction back into range happens in Chapter 23.

One more consequence of Bézout deserves a name, because it is the crucial lemma behind the Fundamental Theorem of Arithmetic in the next section.

Euclid's Lemma. If $p$ is prime and $p \mid ab$, then $p \mid a$ or $p \mid b$.

The strategy first. Suppose $p$ does not divide $a$; we must show $p \mid b$. Since $p$ is prime and $p \nmid a$, the only common divisor of $p$ and $a$ is 1, so $\gcd(p, a) = 1$. Now Bézout hands us a combination equal to 1, and multiplying it by $b$ lets us show $p$ divides $b$. This is the payoff of Bézout: it converts "coprime" into a usable equation.

Proof. Assume $p \mid ab$ and $p \nmid a$. Since $p$ is prime, its only positive divisors are 1 and $p$; as $p \nmid a$, the gcd of $p$ and $a$ cannot be $p$, so $\gcd(p, a) = 1$. By Bézout's identity there are integers $x, y$ with $px + ay = 1$. Multiply both sides by $b$: $$pbx + aby = b.$$ Now $p \mid pbx$ (obviously) and $p \mid aby$ (because $p \mid ab$ by hypothesis, so $p \mid (ab)y$). By the linear-combination lemma, $p$ divides their sum, which is $b$. Hence $p \mid b$. $\blacksquare$

Euclid's Lemma is the property that makes primes behave like atoms. It generalizes immediately (by induction) to products of many factors: if a prime divides a product, it divides one of the factors. That is precisely what we need to prove factorizations are unique.

🔄 Check Your Understanding 1. Find Bézout coefficients for $\gcd(17, 5) = 1$ by extending the Euclidean trace. (Hint: $17 = 3\cdot5 + 2$, $5 = 2\cdot2 + 1$, $2 = 2\cdot1 + 0$.) 2. Using Bézout, explain in one sentence why $a$ has a modular inverse mod $n$ exactly when $\gcd(a, n) = 1$. 3. State Euclid's Lemma, then give a non-prime $m$ for which it fails (i.e. $m \mid ab$ but $m \nmid a$ and $m \nmid b$).

Answers

1. Back-substitute: $1 = 5 - 2\cdot 2 = 5 - 2(17 - 3\cdot 5) = 7\cdot 5 - 2\cdot 17$, so $x = -2$, $y = 7$: $17\cdot(-2) + 5\cdot 7 = -34 + 35 = 1$. 2. If $\gcd(a,n)=1$, Bézout gives $ax + ny = 1$, so $ax \equiv 1 \pmod n$ and $x$ is the inverse; if $\gcd(a,n) > 1$ no combination $ax+ny$ can equal 1, so no inverse exists. 3. Euclid's Lemma: if $p$ is prime and $p \mid ab$ then $p \mid a$ or $p \mid b$. It fails for the composite $m = 4$: $4 \mid (2 \cdot 6) = 12$, but $4 \nmid 2$ and $4 \nmid 6$.

22.6 The Fundamental Theorem of Arithmetic

We have been calling primes the "atoms" of multiplication. This section makes that metaphor a theorem: every integer above 1 is built from primes, and — the deep part — it is built from them in exactly one way. This is the Fundamental Theorem of Arithmetic (FTA), and it is the structural fact that justifies almost everything else we do with integers.

Theorem (Fundamental Theorem of Arithmetic). Every integer $n > 1$ can be written as a product of primes, $$n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k},$$ with $p_1 < p_2 < \cdots < p_k$ primes and each $a_i \ge 1$. Moreover this factorization is unique: the set of primes and their exponents is determined by $n$.

The theorem has two halves — existence (a factorization exists) and uniqueness (there is only one). The existence half is easy and you have essentially seen it. The uniqueness half is the subtle one, and it is exactly where Euclid's Lemma earns its keep.

The strategy first (existence). This is the strong-induction argument from Chapter 6's family. Either $n$ is already prime (done), or it splits as $n = ab$ with both factors smaller; by the inductive hypothesis each factor is a product of primes, and gluing those products together expresses $n$ as a product of primes.

Proof of existence (strong induction on $n$). Let $P(n)$ be "$n$ is a product of primes," for $n \ge 2$. Base case ($n = 2$): $2$ is prime, a product of one prime. Inductive step: fix $n > 2$ and assume every integer $m$ with $2 \le m < n$ is a product of primes. If $n$ is prime, it is trivially such a product and we are done. Otherwise $n$ is composite, so $n = ab$ with $1 < a < n$ and $1 < b < n$. By the inductive hypothesis, $a = q_1 \cdots q_s$ and $b = r_1 \cdots r_t$ are each products of primes. Then $n = ab = q_1 \cdots q_s\, r_1 \cdots r_t$ is a product of primes. By strong induction, $P(n)$ holds for all $n \ge 2$. $\blacksquare$

Now uniqueness. This is where many a careless treatment simply asserts the result; we will prove it, because the proof is the reason the theorem is true rather than merely plausible.

The strategy first (uniqueness). Suppose some number had two different prime factorizations. Among all such "bad" numbers there is a smallest one (well-ordering). Take a prime from the first factorization; by Euclid's Lemma it must appear in the second factorization too. Cancel that shared prime from both sides — and you get a smaller number with two different factorizations, contradicting that we chose the smallest. The contradiction kills the possibility of any bad number.

Proof of uniqueness. Suppose, for contradiction, that some integer greater than 1 has two distinct prime factorizations. By the well-ordering principle there is a smallest such integer $n$. Write its two factorizations as $$n = p_1 p_2 \cdots p_s = q_1 q_2 \cdots q_t,$$ listing primes with repetition (so exponents are encoded by repeats). Consider the prime $p_1$. It divides $n$, hence $p_1 \mid q_1 q_2 \cdots q_t$. By Euclid's Lemma (extended to several factors, 22.5), $p_1$ divides some $q_j$. But $q_j$ is prime, so its only divisors are 1 and $q_j$; since $p_1 \ne 1$, we must have $p_1 = q_j$. Reorder the $q$'s so that $q_j = q_1$. Now cancel this common prime from both sides: $$\frac{n}{p_1} = p_2 \cdots p_s = q_2 \cdots q_t.$$ This quotient is a positive integer smaller than $n$. If its two factorizations differed, $n/p_1$ would be a smaller counterexample than $n$ — contradicting the minimality of $n$. So the two factorizations of $n/p_1$ must be identical, which (re-attaching the cancelled $p_1 = q_1$) forces the two factorizations of $n$ to be identical too. That contradicts our assumption that they were distinct. Hence no integer has two distinct factorizations: the factorization is unique. $\blacksquare$

The FTA is why integers feel solid. It gives every number a fingerprint — its multiset of prime factors — that nothing else shares. The number $360$ is, and can only be, $2^3 \cdot 3^2 \cdot 5$. This fingerprint is so reliable that you can answer many questions by reading it off instead of computing directly, as we will now see.

Using unique factorization

Once you trust that the prime fingerprint is unique, gcd and lcm become almost trivial to describe (if not to compute for huge numbers). For each prime $p$, let $a_p$ and $b_p$ be its exponent in $a$ and $b$ (zero if absent). Then $$\gcd(a, b) = \prod_p p^{\min(a_p,\, b_p)}, \qquad \operatorname{lcm}(a, b) = \prod_p p^{\max(a_p,\, b_p)}.$$ The gcd takes the smaller power of each shared prime; the lcm takes the larger. For example, $a = 360 = 2^3 3^2 5$ and $b = 84 = 2^2 3 \cdot 7$ give $\gcd = 2^2 3 = 12$ and $\operatorname{lcm} = 2^3 3^2 5 \cdot 7 = 2520$. And because $\min(a_p, b_p) + \max(a_p, b_p) = a_p + b_p$, multiplying these gives the elegant identity $$\gcd(a, b)\cdot \operatorname{lcm}(a, b) = a \cdot b \qquad (a, b > 0),$$ which lets you compute an lcm using only the (fast) Euclidean gcd: $\operatorname{lcm}(a,b) = ab / \gcd(a,b)$. You never want to compute a gcd by factoring — factoring is slow, the Euclidean algorithm is fast — but the factorization picture is how you understand what gcd and lcm mean.

def factorize(n):
    """Prime factorization of n > 1 as [(prime, exponent), ...]."""
    factors, d = [], 2
    while d * d <= n:
        if n % d == 0:
            e = 0
            while n % d == 0:
                n //= d
                e += 1
            factors.append((d, e))
        d += 1
    if n > 1:
        factors.append((n, 1))   # a leftover prime > sqrt(original n)
    return factors

print(factorize(360))
print(factorize(97))
# Expected output:
# [(2, 3), (3, 2), (5, 1)]
# [(97, 1)]

🔗 Connection. This factorize is trial division, and its slowness is the whole point of cryptography. For a 100-digit number it would run essentially forever. RSA's security (Chapter 25) rests precisely on the gap the FTA opens: factorizations exist and are unique, but finding them is computationally hard, while multiplying primes together is easy. Public-key crypto lives in that asymmetry between an easy direction (multiply) and a hard inverse (factor). Hold that thought — it is the punchline of the whole of Part IV.

🔄 Check Your Understanding 1. Give the prime factorization of $504$, then use it to read off $\gcd(504, 360)$ and $\operatorname{lcm}(504, 360)$. (Recall $360 = 2^3 3^2 5$.) 2. Which lemma is the crucial ingredient in the uniqueness half of the FTA, and where exactly is it used? 3. Use $\gcd \cdot \operatorname{lcm} = ab$ to compute $\operatorname{lcm}(252, 198)$ given $\gcd(252,198) = 18$.

Answers

1. $504 = 2^3 \cdot 3^2 \cdot 7$. With $360 = 2^3 3^2 5$: $\gcd = 2^3 3^2 = 72$ (min of each shared prime; the prime 5 and prime 7 are not shared so contribute $\min = 0$); $\operatorname{lcm} = 2^3 3^2 5 \cdot 7 = 2520$. 2. Euclid's Lemma (if a prime divides a product it divides a factor); it is used to argue that $p_1$ must equal one of the $q_j$, enabling the cancellation. 3. $\operatorname{lcm}(252,198) = (252 \cdot 198)/18 = 49896/18 = 2772$.

Project Checkpoint: starting numbertheory.py

This chapter opens the Toolkit module that will carry us all the way to a working RSA implementation: dmtoolkit/numbertheory.py. The full module (built across this chapter and Chapter 23) will expose gcd, ext_gcd, sieve, mod_inverse, mod_pow, and crt. Today we contribute the three foundations — everything that does not require modular arithmetic yet: gcd, ext_gcd, and sieve. The signatures are frozen by the style guide so that next chapter's pieces snap in without changing ours.

Create dmtoolkit/numbertheory.py and add:

def gcd(a, b):
    """Greatest common divisor via the Euclidean algorithm. gcd(0, 0) = 0."""
    a, b = abs(a), abs(b)
    while b != 0:
        a, b = b, a % b
    return a

def ext_gcd(a, b):
    """Return (g, x, y) with g = gcd(a, b) and a*x + b*y = g (Bezout)."""
    if b == 0:
        return (a, 1, 0)
    g, x1, y1 = ext_gcd(b, a % b)
    return (g, y1, x1 - (a // b) * y1)

def sieve(n):
    """All primes p with 2 <= p <= n (Sieve of Eratosthenes)."""
    if n < 2:
        return []
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for p in range(2, int(n ** 0.5) + 1):
        if is_prime[p]:
            for m in range(p * p, n + 1, p):
                is_prime[m] = False
    return [i for i in range(2, n + 1) if is_prime[i]]

print(gcd(252, 198))
print(ext_gcd(252, 198))
print(sieve(30))
# Expected output:
# 18
# (18, 4, -5)
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Why this builds toward the capstone. Every one of these three functions is a direct dependency of RSA (capstone Track A). sieve gives you small primes to test ideas on; gcd checks that a candidate public exponent $e$ is coprime to $\phi(n)$ (so that a decryption key exists at all); and ext_gcd is the engine that computes the decryption key, because — as the Threshold Concept in 22.5 showed — the Bézout coefficient of $e$ modulo $\phi(n)$ is the private exponent $d$. In Chapter 23 you will wrap ext_gcd into mod_inverse and add mod_pow for fast encryption; by Chapter 25 these few lines will be quietly powering an encryption you can actually use.

Toolkit so far: logic.py (Ch. 1–3), sets.py (Ch. 8), relations.py (Ch. 12–13), combinatorics.py (Ch. 15–17), recurrences.py (Ch. 18–19), probability.py (Ch. 20–21), and now the start of numbertheory.py. The number-theory module is the gateway to crypto.py.

Summary

This chapter built the integer-arithmetic foundation for all of Part IV. The essential results, reference-grade:

Core definitions

Key theorems

Algorithms and complexity

Identities to keep handy

• $\gcd(a,b) = \prod_p p^{\min(a_p,b_p)}$, $\operatorname{lcm}(a,b) = \prod_p p^{\max(a_p,b_p)}$.
• $\gcd(a,b)\cdot\operatorname{lcm}(a,b) = ab$ for $a,b>0$ — so $\operatorname{lcm}(a,b) = ab/\gcd(a,b)$.
• Python's % returns the canonical $0 \le r < d$; C/C++/Java do not for negative dividends.

The one habit to keep: when you see $a \mid b$, rewrite it as $b = ak$. Every elementary proof here ran on unpack–combine–repackage.

Spaced Review

Retrieval strengthens memory. Answer from memory before expanding the solutions.

1. (Ch. 6) The existence half of the FTA and the "every $n>1$ has a prime divisor" lemma were both proved by strong induction rather than ordinary induction. What feature of these arguments forces strong induction instead of the one-step-back version from Chapter 6?
2. (Ch. 6) The Euclidean algorithm's worst case is consecutive Fibonacci numbers. Recall the Fibonacci recurrence from Chapter 6 and compute $\gcd(F_7, F_6) = \gcd(13, 8)$ step by step. How many division steps does it take?
3. (Ch. 5) Euclid's proof of the infinitude of primes is a proof by contradiction. State the assumption that gets contradicted, and name the contradiction reached.
4. (Ch. 5) We proved the uniqueness of $(q, r)$ in the Division Algorithm and of prime factorization. Both used the same "suppose two and show they coincide" move. Why is showing a difference must be 0 a legitimate way to prove uniqueness?

Answers

1. When $n = ab$ splits, the factors $a, b$ can be any size below $n$, not specifically $n-1$. Ordinary induction only lets you assume $P(n-1)$; you need to assume the statement for all smaller values to apply it to arbitrary $a, b < n$ — that is exactly strong induction. 2. $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$. Five steps, gcd $= 1$ (consecutive Fibonacci numbers are always coprime). 3. The assumption is "there are only finitely many primes" (so they can all be listed as $p_1,\dots,p_r$); the contradiction is that the constructed $N = p_1\cdots p_r + 1$ forces a prime $q$ dividing 1, impossible since every prime is $\ge 2$. 4. Two integers are equal if and only if their difference is 0. Deriving "the difference is a multiple of $d$ but lies strictly between $-d$ and $d$" pins the difference to the unique such multiple, 0 — so the two values must be the same.

What's Next

We have the integers' multiplicative skeleton: divisibility, primes, gcd, Bézout, and unique factorization. But notice how often the remainder — not the quotient — carried the meaning. The remainder is where hashing wraps, where clocks reset, and where cryptography does its real work. Chapter 23 promotes the remainder to a first-class citizen: we will define congruence mod $n$ ($a \equiv b \pmod n$ when $n \mid (a-b)$), build an arithmetic of remainders that adds and multiplies cleanly, and turn the extended Euclidean algorithm from this chapter into a modular inverse. From there it is a short step to fast modular exponentiation and to Fermat's and Euler's theorems — the precise machinery that makes RSA work. The tools are all in your hands now; next we learn to compute with them in the world of clock arithmetic.