Appendix G: Number Theory Reference

The one-page (well, several-page) reference for Part IV — Number Theory and Cryptography (Chapters 22–25). Everything a programmer needs to size a keyspace, write numbertheory.py, or read the RSA paper is collected here: definitions, the algorithms in pseudocode, the named theorems, and short notes on why each fact is true and where the book derives it in full.

Throughout, lowercase letters $a, b, c, d, m, n$ are integers and $p, q$ are primes. The mod operator $a \bmod n$ returns the remainder in $\{0, 1, \dots, n-1\}$; the congruence $a \equiv b \pmod{n}$ means $n \mid (a - b)$. Recall the standing convention that $\mathbb{N}$ includes $0$ (Appendix A).

G.1 Divisibility (Chapter 4, revisited in 22)

Definition. $a \mid b$ ("$a$ divides $b$") means there is an integer $k$ with $b = ak$. Then $a$ is a divisor of $b$ and $b$ is a multiple of $a$. We write $a \nmid b$ when no such $k$ exists.

Core properties. For all integers $a, b, c$:

💡 Intuition: the linear-combination rule is the workhorse of this entire appendix. Almost every gcd fact reduces to "a common divisor of two numbers also divides their integer combinations."

The Division Theorem (a.k.a. the division algorithm). For any integer $a$ and any positive integer $n$, there exist unique integers $q$ (quotient) and $r$ (remainder) with

$$a = qn + r, \qquad 0 \le r < n.$$

Here $q = \lfloor a/n \rfloor$ and $r = a \bmod n$. This is what makes "$a \bmod n$" well defined and is the foundation the Euclidean algorithm stands on.

G.2 Greatest common divisor and least common multiple (Chapter 22)

Definition. $\gcd(a, b)$ is the largest integer dividing both $a$ and $b$ (with $\gcd(0, 0) = 0$ by convention). $\operatorname{lcm}(a, b)$ is the smallest positive common multiple.

Key facts.

Coprime / relatively prime. $a$ and $b$ are coprime when $\gcd(a, b) = 1$. This is the condition that makes modular inverses exist (§G.5) and the Chinese Remainder Theorem apply (§G.7).

🔗 Connection: the gcd–lcm identity lets you compute the lcm via the gcd — $\operatorname{lcm}(a,b) = \lvert ab\rvert / \gcd(a,b)$ — which is exactly how numbertheory.py avoids ever factoring the inputs.

G.3 The Euclidean algorithm (Chapter 22)

Idea. Repeatedly replace the larger number by the remainder. Because remainders strictly shrink and stay non-negative, the process must hit $0$; the last nonzero remainder is the gcd. The reduction rule $\gcd(a,b) = \gcd(b,\ a \bmod b)$ justifies every step.

Pseudocode.

gcd(a, b):
    a, b = |a|, |b|
    while b != 0:
        a, b = b, a mod b
    return a

Worked trace — $\gcd(252, 105)$.

Result: $\gcd(252, 105) = 21$.

Complexity. $O(\log(\min(a, b)))$ division steps — the worst case is consecutive Fibonacci numbers (Lamé's theorem, Tier 2 — commonly attributed to Gabriel Lamé, 1844). This is why gcd is cheap even on cryptographic-sized integers.

🚪 Threshold Concept: Euclid's algorithm (c. 300 BCE) is the oldest nontrivial algorithm still in daily use. It also constructs the Bézout coefficients (next section), and those coefficients are the modular inverse, which is the trapdoor that makes RSA decryption possible. The whole of Part IV hangs on this one loop.

G.4 The extended Euclidean algorithm and Bézout's identity (Chapter 22)

Bézout's identity. For all integers $a, b$ (not both $0$) there exist integers $x, y$ with

$$ax + by = \gcd(a, b).$$

The extended algorithm returns the triple $(g, x, y)$ where $g = \gcd(a, b)$.

Pseudocode (iterative).

ext_gcd(a, b):
    old_r, r = a, b
    old_s, s = 1, 0
    old_t, t = 0, 1
    while r != 0:
        q = old_r div r
        old_r, r = r, old_r - q*r
        old_s, s = s, old_s - q*s
        old_t, t = t, old_t - q*t
    return (old_r, old_s, old_t)   # (gcd, x, y)

Invariant (why it works). At every step both pairs satisfy $a\cdot s + b\cdot t = r$ and $a\cdot(\text{old }s) + b\cdot(\text{old }t) = (\text{old }r)$. When $r$ reaches $0$, $(\text{old }r) = g$ and its coefficients are the Bézout pair. Proving this invariant by induction is a Chapter 22 exercise.

Worked result — $a = 240,\ b = 46$. The algorithm yields $g = 2$ with $x = -9,\ y = 47$, since

$$240\cdot(-9) + 46\cdot 47 = -2160 + 2162 = 2.$$

Why it matters: if $\gcd(a, m) = 1$, then $ax + my = 1$, so $ax \equiv 1 \pmod{m}$ — the coefficient $x$ is $a^{-1} \bmod m$. Extended Euclid is the standard way to compute modular inverses (§G.5).

G.5 Primes, factorization, and the sieve (Chapter 22)

Definition. A prime is an integer $p \ge 2$ whose only positive divisors are $1$ and $p$. An integer $\ge 2$ that is not prime is composite.

Fundamental Theorem of Arithmetic. Every integer $n \ge 2$ has a unique factorization into primes (up to order):

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

Existence is proved by strong induction (Chapter 7); uniqueness uses Euclid's lemma below.

Euclid's lemma. If $p$ is prime and $p \mid ab$, then $p \mid a$ or $p \mid b$. (This is exactly the property that distinguishes primes from general divisors — e.g., $6 \mid 4\cdot 9$ but $6 \nmid 4$ and $6 \nmid 9$.)

Infinitude of primes. There are infinitely many primes (Euclid's classic proof by contradiction — see Chapter 5: assume finitely many $p_1,\dots,p_k$, then $p_1\cdots p_k + 1$ has a prime factor not in the list).

Trial-division primality test. $n$ is prime iff no integer $d$ with $2 \le d \le \lfloor\sqrt{n}\rfloor$ divides it. The $\sqrt{n}$ bound holds because a composite $n = ab$ must have a factor $\le \sqrt{n}$.

Sieve of Eratosthenes — all primes up to $n$ in $O(n \log\log n)$ time.

sieve(n):
    is_prime = [True] * (n+1); is_prime[0] = is_prime[1] = False
    for i from 2 to floor(sqrt(n)):
        if is_prime[i]:
            for j from i*i to n step i:     # start at i*i; smaller multiples already marked
                is_prime[j] = False
    return [i for i in 0..n if is_prime[i]]

Primes below $30$: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29$.

⚠️ Common Pitfall: start the inner loop at $i \cdot i$, not $2i$. Every multiple of $i$ below $i^2$ has a smaller prime factor and was already crossed off, so starting at $2i$ just wastes work.

G.6 Modular arithmetic (Chapter 23)

Congruence. $a \equiv b \pmod{n}$ iff $n \mid (a - b)$ iff $a \bmod n = b \bmod n$. Congruence mod $n$ is an equivalence relation (Chapter 12), partitioning $\mathbb{Z}$ into the $n$ residue classes of $\mathbb{Z}_n = \{0, 1, \dots, n-1\}$.

Arithmetic respects congruence. If $a \equiv b \pmod n$ and $c \equiv d \pmod n$, then:

These let you reduce at every step, keeping numbers small: $(a \cdot b) \bmod n = \big((a \bmod n) \cdot (b \bmod n)\big) \bmod n$.

⚠️ Common Pitfall — no general division. You may not cancel a common factor freely: $ac \equiv bc \pmod n$ does not imply $a \equiv b \pmod n$. Cancellation is legal only when $\gcd(c, n) = 1$ (then $c$ has an inverse, §G.5/§G.5… see §G.7). For example $2\cdot 3 \equiv 2\cdot 0 \pmod 6$ but $3 \not\equiv 0 \pmod 6$.

Fast modular exponentiation (square-and-multiply). Compute $b^e \bmod m$ in $O(\log e)$ multiplications by scanning the bits of $e$:

mod_pow(b, e, m):
    result = 1; b = b mod m
    while e > 0:
        if e is odd: result = (result * b) mod m
        b = (b * b) mod m
        e = e div 2
    return result

Example: $3^{13} \bmod 7$. Since $13 = 1101_2$: $3^1\equiv3$, $3^2\equiv2$, $3^4\equiv4$, $3^8\equiv2\ (\bmod 7)$; multiply the bits set in $13$ ($8{+}4{+}1$): $2\cdot4\cdot3 = 24 \equiv 3 \pmod 7$. So $3^{13} \equiv 3 \pmod 7$. This routine is the computational core of RSA.

G.7 Modular inverses (Chapter 23)

Definition. A modular inverse of $a$ modulo $m$ is an integer $a^{-1}$ with $a \cdot a^{-1} \equiv 1 \pmod{m}$.

Existence theorem. $a^{-1} \bmod m$ exists iff $\gcd(a, m) = 1$. When it exists it is unique in $\{1, \dots, m-1\}$.

Two ways to compute it.

1. Extended Euclid (always works when coprime). Solve $ax + my = 1$; then $a^{-1} \equiv x \pmod m$. This is what mod_inverse(a, m) does.
2. Fermat shortcut (prime modulus only). If $p$ is prime and $p \nmid a$, then $a^{-1} \equiv a^{\,p-2} \pmod{p}$ (a direct corollary of §G.8). Compute it with mod_pow.

Worked example. $a = 3,\ m = 7$. Extended Euclid on $(3, 7)$ gives $3\cdot(-2) + 7\cdot 1 = 1$, so $3^{-1} \equiv -2 \equiv 5 \pmod 7$. Check: $3 \cdot 5 = 15 \equiv 1 \pmod 7$. ✓

G.8 Fermat's little theorem and Euler's theorem (Chapter 23)

Euler's totient function $\phi(n)$ counts the integers in $\{1, \dots, n\}$ that are coprime to $n$.

For RSA the key case is $n = pq$ with distinct primes, giving $\phi(n) = (p-1)(q-1)$.

Fermat's Little Theorem. If $p$ is prime and $p \nmid a$, then

$$a^{\,p-1} \equiv 1 \pmod{p}, \qquad\text{equivalently}\qquad a^{\,p} \equiv a \pmod{p}\ \text{for all } a.$$

Euler's Theorem (the generalization). If $\gcd(a, n) = 1$, then

$$a^{\,\phi(n)} \equiv 1 \pmod{n}.$$

Taking $n = p$ recovers Fermat, since $\phi(p) = p - 1$.

💡 Intuition: multiplying every coprime residue by a fixed coprime $a$ just permutes those residues mod $n$. Multiply them all together and the common factor $a^{\phi(n)}$ must cancel, leaving $1$. That permutation argument is the proof (Chapter 23).

Reducing exponents. A direct consequence: when $\gcd(a, n) = 1$, exponents may be taken mod $\phi(n)$ — $a^{e} \equiv a^{\,e \bmod \phi(n)} \pmod{n}$. This is precisely why RSA's keys are chosen mod $\phi(n)$.

🔗 Connection: Chapter 24 reframes all of this in the language of groups: the coprime residues form the group $(\mathbb{Z}/n\mathbb{Z})^{*}$ of order $\phi(n)$, and Euler's theorem is just Lagrange's theorem ("an element raised to the group order is the identity") in disguise.

G.9 The Chinese Remainder Theorem (Chapter 23)

Statement. Let $m_1, m_2, \dots, m_k$ be pairwise coprime positive integers with product $M = m_1 m_2 \cdots m_k$. Then for any residues $r_1, \dots, r_k$ the system

$$x \equiv r_1 \pmod{m_1}, \quad x \equiv r_2 \pmod{m_2}, \quad \dots, \quad x \equiv r_k \pmod{m_k}$$

has a unique solution $x$ modulo $M$.

Construction (two-congruence case, the building block). For $x \equiv r_1 \pmod{m_1}$ and $x \equiv r_2 \pmod{m_2}$ with $\gcd(m_1, m_2) = 1$:

1. Let $M_1 = m_2$ and $M_2 = m_1$ (each is "all the moduli except its own").
2. Compute $y_1 = M_1^{-1} \bmod m_1$ and $y_2 = M_2^{-1} \bmod m_2$ (via §G.5).
3. Then $x \equiv (r_1 M_1 y_1 + r_2 M_2 y_2) \bmod M$, where $M = m_1 m_2$.

The general $k$-congruence formula is $x = \sum_i r_i M_i y_i \bmod M$ with $M_i = M / m_i$ and $y_i = M_i^{-1} \bmod m_i$ — this is what crt(rs, ms) implements.

Worked example. $x \equiv 2 \pmod 3$ and $x \equiv 3 \pmod 5$, so $M = 15$. Candidates that are $2 \bmod 3$: $2, 5, 8, 11, 14$; of these the one that is $3 \bmod 5$ is $8$. So $x \equiv 8 \pmod{15}$. Check: $8 = 2\cdot3 + 2$ and $8 = 1\cdot5 + 3$. ✓

🔗 Connection: real RSA implementations decrypt with CRT — working mod $p$ and mod $q$ separately, then recombining — for a roughly 4× speedup, because each half uses much smaller numbers (Chapter 25).

G.10 RSA, end to end (Chapters 24–25)

RSA's security rests on a one-way asymmetry: multiplying two large primes is easy, but factoring their product is believed to be infeasible. Encryption uses the public product; decryption needs the secret factors. Here are the three procedures exactly as crypto.py builds them.

🚪 Threshold Concept: public-key cryptography. You can publish a key that lets anyone send you a secret, while keeping a separate key that only you can read with — no shared secret, no prior contact. This single idea (Diffie–Hellman 1976; RSA 1978) underwrites HTTPS, signatures, and secure messaging.

Key generation — rsa_keygen(bits)

1. Choose two distinct large primes $p$ and $q$ (roughly bits/2 each).
2. Compute the modulus $n = pq$ and the totient $\phi(n) = (p - 1)(q - 1)$.
3. Choose a public exponent $e$ with $1 < e < \phi(n)$ and $\gcd(e, \phi(n)) = 1$ (commonly $e = 65537$).
4. Compute the private exponent $d \equiv e^{-1} \pmod{\phi(n)}$ via extended Euclid (§G.5).
5. Public key $= (e, n)$. Private key $= (d, n)$. Destroy $p$, $q$, and $\phi(n)$.

Encryption — rsa_encrypt(m, pub)

For a message $m$ with $0 \le m < n$:

$$c = m^{e} \bmod n \qquad(\text{compute with } \texttt{mod\_pow}).$$

Decryption — rsa_decrypt(c, priv)

$$m = c^{d} \bmod n.$$

Why decryption inverts encryption

Because $ed \equiv 1 \pmod{\phi(n)}$, write $ed = 1 + k\,\phi(n)$. Then

$$c^{d} \equiv (m^{e})^{d} = m^{ed} = m^{\,1 + k\phi(n)} = m \cdot \big(m^{\phi(n)}\big)^{k} \equiv m \cdot 1^{k} = m \pmod{n},$$

using Euler's theorem (§G.8) when $\gcd(m, n) = 1$; the remaining cases are handled by applying Fermat mod $p$ and mod $q$ separately and recombining with the CRT (§G.9). Full details are in Chapter 25.

Tiny worked instance (toy numbers, for tracing only — never use small primes in practice): take $p = 11,\ q = 13$, so $n = 143$ and $\phi(n) = 10 \cdot 12 = 120$. Pick $e = 7$ (and $\gcd(7, 120) = 1$). Then $d = 7^{-1} \bmod 120 = 103$, since $7 \cdot 103 = 721 = 6\cdot120 + 1$. Encrypt $m = 9$: $c = 9^{7} \bmod 143 = 48$. Decrypt: $48^{103} \bmod 143 = 9$. ✓

⚠️ Common Pitfall: "textbook RSA" as shown here is deterministic and therefore insecure for real use — identical messages encrypt to identical ciphertexts, and it is malleable. Production systems add randomized padding (OAEP) and use RSA only to wrap a symmetric key. Treat the version above as a learning model, not a deployable cipher.

G.11 At-a-glance summary

Toolkit cross-map. numbertheory.py: gcd, ext_gcd, sieve, mod_inverse, mod_pow, crt (Chapters 22–23). crypto.py: rsa_keygen, rsa_encrypt, rsa_decrypt (Chapters 24–25). The full assembled source lives in Appendix I.

One thread runs through this whole appendix: the Euclidean algorithm computes a gcd, the gcd test decides when an inverse exists, the extended algorithm builds that inverse, the inverse is RSA's private key, and Euler's theorem is the reason the key works. Learn the loop in §G.3 and the rest falls into place.