Chapter 23: Modular Arithmetic

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

Overview

Every time you compute a hash bucket with h % table_size, wrap a clock from 23:00 to 01:00, or overflow a 32-bit integer and watch it silently roll over to a negative number, you are doing modular arithmetic — you just haven't been asked to prove anything about it yet. This chapter turns that everyday % operator into a complete arithmetic system: one with its own addition, multiplication, and — the surprising part — its own division. By the end you will be able to compute $a^{b} \bmod n$ for astronomically large exponents in a blink, solve equations like "find $x$ with $3x \equiv 4 \pmod{5}$," and reassemble a number from its remainders the way the Chinese Remainder Theorem has done for two thousand years.

This matters because modular arithmetic is the engine room of public-key cryptography. In Chapter 22 you built the number-theoretic scaffolding — divisibility, primes, the Euclidean algorithm, Bézout's identity. Here we assemble those parts into the machinery that makes RSA work: modular inverses (the private key), fast exponentiation (encryption and decryption), and Euler's theorem (the reason decryption undoes encryption). Two chapters from now you will type out a working RSA implementation; this chapter is where you learn every operation it performs.

There is a deeper reason a programmer needs this. Modular arithmetic is the first place most people meet a finite number system that is still rich enough to do real algebra in. A computer's integers are finite — they wrap. Understanding the arithmetic of a finite ring is understanding what your CPU actually does when it adds, and it is the gateway to the algebraic structures of Chapter 24 and the error-correcting codes of Chapter 26.

In this chapter, you will learn to:

• Decide when $a \equiv b \pmod{n}$ and work with residues and residue classes.
• Use the modular arithmetic rules to keep numbers small throughout a long computation.
• Solve linear congruences and compute modular inverses — and know exactly when an inverse exists.
• Reconstruct a number from its remainders with the Chinese Remainder Theorem.
• Raise a number to a huge power modulo $n$ in $O(\log e)$ multiplications.
• Apply Fermat's little theorem and Euler's theorem, the two results that make RSA decrypt correctly.

Learning Paths

🏃 Fast Track: If clock arithmetic is second nature, skim 23.1–23.2 for the notation, then study 23.3 (inverses), 23.5 (fast exponentiation), and 23.6 (Fermat/Euler) — those three are the parts RSA uses directly. Do the ⭐⭐ and ⭐⭐⭐ exercises.

📖 Standard Path: Read in order. Work every 🔄 Check Your Understanding before moving on, and hand-trace the square-and-multiply example in 23.5 yourself before reading our trace.

🔬 Deep Dive: Prove that congruence mod $n$ is an equivalence relation that respects addition and multiplication (a "congruence" in the algebraic sense), and prove the CRT isomorphism $\mathbb{Z}_{mn} \cong \mathbb{Z}_m \times \mathbb{Z}_n$ for coprime $m, n$. Chapter 24 will give these the vocabulary of rings; you can preview that structure now. See the exercise set, Part E.

23.1 Congruence mod n

Start with a clock. A 12-hour clock face has the numbers $0$ through $11$ (let's put $0$ where $12$ usually sits). If it is $9$ o'clock and you wait $7$ hours, it is not $16$ o'clock — it is $4$ o'clock. You computed $9 + 7 = 16$, then wrapped: $16$ and $4$ are "the same" on this clock because they differ by a full lap of $12$. We write this $16 \equiv 4 \pmod{12}$ and say "$16$ is congruent to $4$ modulo $12$." The clock is the picture; here is the definition that powers everything.

Definition (congruence). Let $n$ be a positive integer. Two integers $a$ and $b$ are congruent modulo $n$, written $$a \equiv b \pmod{n},$$ if $n \mid (a - b)$ — that is, if $a$ and $b$ leave the same remainder when divided by $n$. The number $n$ is the modulus.

The two phrasings — "$n$ divides $a - b$" and "$a$ and $b$ have the same remainder" — are equivalent, and you will switch between them constantly. The divisibility phrasing is the one to prove with (it unpacks into an equation, exactly as Chapter 22 taught: $n \mid (a-b)$ means $a - b = nk$ for some integer $k$). The remainder phrasing is the one to compute with.

🔗 Connection. "$n \mid (a-b)$" is the divisibility relation from Chapter 22, §22.1 — the same relation, reused. Almost every proof in this chapter begins by translating a congruence into "$a - b = nk$ for some integer $k$" and ends by translating back. If that move feels familiar, it is the same "unpack the definition, do algebra, repackage" pattern from the divisibility proofs in Chapter 6.

A worked check, by hand:

• Is $17 \equiv 5 \pmod 4$? Compute $17 - 5 = 12$, and $4 \mid 12$. Yes. (Equivalently, $17 = 4\cdot4 + 1$ and $5 = 4\cdot1 + 1$ — both leave remainder $1$.)
• Is $17 \equiv 5 \pmod 6$? Compute $17 - 5 = 12$, and $6 \mid 12$. Yes.
• Is $17 \equiv 5 \pmod 7$? Compute $17 - 5 = 12$, and $7 \nmid 12$. No. ($17$ leaves remainder $3$, $5$ leaves remainder $5$.)

Notice that congruence sorts the integers into groups. Modulo $3$, every integer is congruent to exactly one of $0$, $1$, or $2$: $$\dots, -3, 0, 3, 6, \dots \equiv 0; \qquad \dots, -2, 1, 4, 7, \dots \equiv 1; \qquad \dots, -1, 2, 5, 8, \dots \equiv 2 \pmod 3.$$

Each group is a residue class, and the small standard representative — the remainder in $\{0, 1, \dots, n-1\}$ — is the residue.

Definition (residue). The residue of $a$ modulo $n$ is the unique integer $r$ with $0 \le r < n$ and $a \equiv r \pmod{n}$; we write $r = a \bmod n$. The set of all residues, ${0, 1, \dots, n-1}$, is denoted $\mathbb{Z}_n$. The **residue class** of $a$ is the set of all integers congruent to $a$ modulo $n$.

Two notations are doing different jobs, and confusing them is the most common early mistake.

⚠️ Common Pitfall: ≡ (mod n) is a relation; mod n is an operator. Write \pmod for the relation between two whole numbers — $a \equiv b \pmod{n}$ is a true/false statement. Write \bmod for the binary operator that produces a number — $a \bmod n$ is the single residue in ${0, \dots, n-1}$. So "$17 \equiv 5 \pmod 4$" is a true statement, while "$17 \bmod 4$" equals $1$. In Python, 17 % 4 is the operator and evaluates to 1.

A subtlety worth pinning down now, because it bites in code: the mathematical residue is always non-negative, but programming languages disagree about negative operands. Python's % matches the math (-7 % 3 == 2), but C and Java return -1 for -7 % 3. We will always mean the non-negative residue.

That residue classes partition the integers is not an accident — it is because congruence is an equivalence relation, a fact worth proving because the rest of the chapter rests on it.

The strategy first. "Equivalence relation" means reflexive, symmetric, and transitive (Chapter 12, §12.4). Each is a one-line consequence of the divisibility definition. The only idea we need is the algebra of "$n$ divides a difference": rewrite each congruence as an equation $a - b = nk$, then add or negate as needed.

Theorem 23.1. For a fixed positive integer $n$, congruence modulo $n$ is an equivalence relation on $\mathbb{Z}$.

Proof. Let $a, b, c$ be integers.

Reflexive: $a - a = 0 = n \cdot 0$, so $n \mid (a - a)$ and $a \equiv a \pmod n$.

Symmetric: suppose $a \equiv b \pmod n$, so $a - b = nk$ for some integer $k$. Then $b - a = n(-k)$, and since $-k$ is an integer, $n \mid (b - a)$, i.e. $b \equiv a \pmod n$.

Transitive: suppose $a \equiv b$ and $b \equiv c$, so $a - b = nk$ and $b - c = n\ell$ for integers $k, \ell$. Adding, $a - c = (a - b) + (b - c) = nk + n\ell = n(k + \ell)$. Since $k + \ell$ is an integer, $n \mid (a - c)$, i.e. $a \equiv c \pmod n$.

All three properties hold, so congruence modulo $n$ is an equivalence relation, and its equivalence classes are exactly the residue classes. $\blacksquare$

🔗 Connection. Theorem 23.1 says $\mathbb{Z}_n$ is a quotient of $\mathbb{Z}$ by an equivalence relation — the residue classes are the equivalence classes from Chapter 12. This is the first time the partition machinery of Part II pays a concrete dividend: it guarantees the $n$ residue classes are disjoint and cover every integer, so "reduce mod $n$" is a well-defined operation.

# example-01-congruence.py
def congruent(a, b, n):
    """True iff a is congruent to b modulo n (i.e. n divides a - b)."""
    return (a - b) % n == 0

print(congruent(17, 5, 4))   # 17 - 5 = 12, divisible by 4
print(congruent(17, 5, 7))   # 17 - 5 = 12, NOT divisible by 7
print((-7) % 3)              # Python's residue is non-negative
# Expected output:
# True
# False
# 2

🔄 Check Your Understanding 1. Is $100 \equiv 2 \pmod 7$? Show the divisibility check. 2. What is the residue $(-13) \bmod 5$? (Use the non-negative convention.) 3. List the residue class of $3$ modulo $4$ (a few elements in each direction).

Answers

1. $100 - 2 = 98 = 7 \cdot 14$, so $7 \mid 98$ and yes, $100 \equiv 2 \pmod 7$. 2. $-13 = 5\cdot(-3) + 2$, so $(-13) \bmod 5 = 2$. 3. ${\dots, -5, -1, 3, 7, 11, \dots}$ — every integer of the form $4k + 3$.

23.2 Modular arithmetic rules

Here is the property that turns congruence from a curiosity into a calculational tool: you can do arithmetic on residue classes. If you know $a \bmod n$ and $b \bmod n$, you can find $(a+b) \bmod n$ and $(ab) \bmod n$ without ever computing $a$ and $b$ in full. This is exactly why your CPU can multiply two 64-bit numbers and keep only the low 64 bits — it is computing modulo $2^{64}$.

Concretely: to find the last digit of $7^{100}$, you do not compute the 85-digit number $7^{100}$. You work modulo $10$ throughout, because the last digit is just $7^{100} \bmod 10$. The following theorem is the license to do that.

Theorem 23.2 (modular arithmetic is well-defined). If $a \equiv b \pmod n$ and $c \equiv d \pmod n$, then $$a + c \equiv b + d \pmod n, \qquad a - c \equiv b - d \pmod n, \qquad ac \equiv bd \pmod n.$$

The strategy first. Each line is the same move: write the two hypotheses as equations $a - b = nk$ and $c - d = n\ell$, then form the relevant combination ($+$, $-$, or $\times$) and factor an $n$ back out. Multiplication needs one extra algebraic flourish — add and subtract a cross term — but it is still just factoring.

Proof. Suppose $a \equiv b \pmod n$ and $c \equiv d \pmod n$, so there are integers $k, \ell$ with $a = b + nk$ and $c = d + n\ell$.

Sum: $a + c = (b + nk) + (d + n\ell) = (b + d) + n(k + \ell)$. Since $k + \ell$ is an integer, $n \mid \big((a+c) - (b+d)\big)$, so $a + c \equiv b + d \pmod n$. (Subtraction is identical with a minus sign.)

Product: multiply the two equations: $$ac = (b + nk)(d + n\ell) = bd + bn\ell + nkd + n^2 k\ell = bd + n\big(b\ell + kd + nk\ell\big).$$ The quantity $b\ell + kd + nk\ell$ is an integer, so $n \mid (ac - bd)$, i.e. $ac \equiv bd \pmod n$. $\blacksquare$

The practical reading of Theorem 23.2 is a rule you should internalize:

💡 Intuition: reduce early, reduce often. At any point in a chain of additions, subtractions, and multiplications, you may replace a number by its residue without changing the final answer mod $n$. The result is the same whether you reduce at the end or after every step — so reduce after every step and the numbers never grow large. This single habit is what makes modular exponentiation (§23.5) tractable.

Watch it work on $7^{100} \bmod 10$. We do not need fast exponentiation yet — just the rule and the pattern of powers of $7$ modulo $10$: $$7^1 \equiv 7, \quad 7^2 \equiv 49 \equiv 9, \quad 7^3 \equiv 7 \cdot 9 = 63 \equiv 3, \quad 7^4 \equiv 7 \cdot 3 = 21 \equiv 1 \pmod{10}.$$ The powers cycle with period $4$: $7, 9, 3, 1, 7, 9, 3, 1, \dots$. Since $100 = 4 \cdot 25$, we have $7^{100} = (7^4)^{25} \equiv 1^{25} = 1 \pmod{10}$. The last digit of $7^{100}$ is $\mathbf{1}$ — found with four small multiplications and no large numbers at all.

⚠️ Common Pitfall: you may NOT freely divide or cancel. Addition, subtraction, and multiplication transfer to residues cleanly. Division does not. From $6 \equiv 0 \pmod 6$ you cannot "cancel a $2$" to get $3 \equiv 0 \pmod 6$ (false). Likewise $2 \cdot 3 \equiv 2 \cdot 0 \pmod 6$ does **not** let you cancel the $2$ to conclude $3 \equiv 0 \pmod 6$. Cancellation works only when the factor you cancel is invertible modulo $n$ — which is the entire subject of §23.3. Exponentiation, too, has a special rule (§23.6): you reduce the base mod $n$, but the exponent obeys a different modulus.

# example-02-last-digit.py
def power_mod_naive(base, exp, n):
    """Compute base**exp mod n by reducing after every multiplication.
    Illustrates 'reduce early, reduce often' -- the value never exceeds n*base."""
    result = 1
    for _ in range(exp):
        result = (result * base) % n   # reduce at each step; numbers stay small
    return result

print(power_mod_naive(7, 100, 10))   # last digit of 7**100
print(power_mod_naive(2, 10, 1000))  # 2**10 = 1024, mod 1000
# Expected output:
# 1
# 24

🔄 Check Your Understanding 1. Use the rules to find $(123 + 456) \bmod 10$ by first reducing each summand. 2. What is $7^{102} \bmod 10$? (Use the period-$4$ cycle.) 3. Why is "$2 \cdot 3 \equiv 2 \cdot 0 \pmod 6$, therefore $3 \equiv 0 \pmod 6$" wrong?

Answers

1. $123 \equiv 3$, $456 \equiv 6$, so the sum $\equiv 3 + 6 = 9 \pmod{10}$. 2. $102 = 4\cdot25 + 2$, so $7^{102} \equiv 7^2 \equiv 9 \pmod{10}$. 3. Cancellation requires the cancelled factor to be invertible; $2$ is not invertible modulo $6$ (it shares the factor $2$ with $6$), so the step is illegal. Indeed $3 \not\equiv 0 \pmod 6$.

23.3 Linear congruences and modular inverses

In ordinary arithmetic, to solve $3x = 4$ you divide by $3$: $x = 4/3$. Modular arithmetic has no fractions, but it has something better for our purposes — a way to "divide" that stays inside the integers, when it exists. The question is: can we solve $$3x \equiv 4 \pmod 5$$ for an integer $x$? This is a linear congruence, and solving it is the modular analogue of dividing.

The key object is the modular inverse: the residue that plays the role of "$1/a$."

Definition (modular inverse). Let $a$ and $n$ be integers with $n > 1$. A modular inverse of $a$ modulo $n$ is an integer $a^{-1}$ such that $$a \cdot a^{-1} \equiv 1 \pmod{n}.$$ When it exists, $a^{-1}$ is unique modulo $n$. We also call $a$ a unit modulo $n$ when it has an inverse.

If you have $a^{-1}$, you can solve $ax \equiv b \pmod n$ instantly: multiply both sides by $a^{-1}$ to get $x \equiv a^{-1} b \pmod n$. So the whole problem reduces to: when does an inverse exist, and how do we find it? Both answers come straight from Chapter 22.

Theorem 23.3 (existence of inverses). The integer $a$ has an inverse modulo $n$ if and only if $\gcd(a, n) = 1$ (that is, $a$ and $n$ are coprime).

The strategy first. This is an "if and only if," so two directions. For the useful direction (coprime $\Rightarrow$ inverse exists), we don't just assert existence — we construct the inverse from Bézout's identity (Chapter 22, §22.5): coprimality gives integers $s, t$ with $as + nt = 1$, and reading that equation modulo $n$ makes $s$ the inverse. For the converse, an inverse forces a Bézout-style equation, which forces the gcd to divide $1$.

Proof. ($\Leftarrow$) Suppose $\gcd(a, n) = 1$. By Bézout's identity (Chapter 22), there exist integers $s, t$ with $$as + nt = 1.$$ Reduce this equation modulo $n$. The term $nt \equiv 0 \pmod n$, so $as \equiv 1 \pmod n$. Thus $s$ is an inverse of $a$ modulo $n$ — and the extended Euclidean algorithm (Chapter 22) computes exactly this $s$.

($\Rightarrow$) Suppose $a$ has an inverse, so $a a^{-1} \equiv 1 \pmod n$, meaning $a a^{-1} - 1 = nk$ for some integer $k$. Rearranged, $a \cdot a^{-1} - n \cdot k = 1$. Let $g = \gcd(a, n)$. Since $g \mid a$ and $g \mid n$, $g$ divides the left-hand side, so $g \mid 1$, forcing $g = 1$. Hence $a$ and $n$ are coprime. $\blacksquare$

🔗 Connection. The forward direction is the payoff of the extended Euclidean algorithm from Chapter 22, §22.5. There you learned to find $s, t$ with $as + nt = \gcd(a, n)$; you may have wondered what those coefficients were for. This is what: when $\gcd = 1$, the coefficient $s$ is the modular inverse — the private-key operation at the heart of RSA.

Worked example: compute $7^{-1} \bmod 26$. (This is the inverse you need to decrypt an affine cipher with multiplier $7$.) First, $\gcd(7, 26) = 1$, so an inverse exists. Run the extended Euclidean algorithm to write $1$ as a combination of $7$ and $26$. The descending steps: $$26 = 3 \cdot 7 + 5, \qquad 7 = 1 \cdot 5 + 2, \qquad 5 = 2 \cdot 2 + 1, \qquad 2 = 2 \cdot 1.$$ Now back-substitute: $$1 = 5 - 2\cdot 2 = 5 - 2(7 - 5) = 3\cdot 5 - 2\cdot 7 = 3(26 - 3\cdot 7) - 2\cdot 7 = 3\cdot 26 - 11\cdot 7.$$ So $-11 \cdot 7 + 3 \cdot 26 = 1$, giving $7 \cdot (-11) \equiv 1 \pmod{26}$. The residue of $-11$ modulo $26$ is $-11 + 26 = 15$. Check: $7 \cdot 15 = 105 = 4 \cdot 26 + 1$. So $7^{-1} \equiv \mathbf{15} \pmod{26}$.

Now back to the opening question, $3x \equiv 4 \pmod 5$. Since $\gcd(3, 5) = 1$, the inverse $3^{-1}$ exists; by inspection $3 \cdot 2 = 6 \equiv 1 \pmod 5$, so $3^{-1} \equiv 2$. Multiply both sides: $$x \equiv 2 \cdot 4 = 8 \equiv 3 \pmod 5.$$ Check: $3 \cdot 3 = 9 \equiv 4 \pmod 5$. The solution is $x \equiv 3 \pmod 5$.

What if $\gcd(a, n) \ne 1$? Then $ax \equiv b \pmod n$ may have no solution or several. The full rule completes the picture.

Theorem 23.4 (solvability of linear congruences). Let $g = \gcd(a, n)$. The congruence $ax \equiv b \pmod n$ has a solution **if and only if** $g \mid b$. When $g \mid b$, there are exactly $g$ solutions modulo $n$, and they form a single residue class modulo $n/g$.

The strategy first. A solution to $ax \equiv b \pmod n$ is exactly an integer pair $(x, y)$ with $ax - ny = b$ — a linear Diophantine equation. Chapter 22's Bézout theory says such an equation is solvable iff $\gcd(a,n) \mid b$. We sketch the count and refer the full Diophantine treatment to the exercises.

Proof (sketch). The congruence $ax \equiv b \pmod n$ holds iff $ax - b$ is a multiple of $n$, i.e. iff there is an integer $y$ with $ax - ny = b$. Every integer combination $ax - ny$ is a multiple of $g = \gcd(a, n)$, and conversely every multiple of $g$ is achievable (Bézout, Chapter 22). So a solution exists iff $g \mid b$. When it does, dividing through by $g$ yields $(a/g)x \equiv (b/g) \pmod{n/g}$ with $\gcd(a/g,\, n/g) = 1$, which has a *unique* solution modulo $n/g$ by Theorem 23.3; lifting back to modulus $n$ gives $g$ solutions, spaced $n/g$ apart. $\blacksquare$

A concrete contrast:

• $6x \equiv 4 \pmod 8$: here $g = \gcd(6, 8) = 2$ and $2 \mid 4$, so there are $2$ solutions. Divide by $2$: $3x \equiv 2 \pmod 4$; since $3^{-1} \equiv 3 \pmod 4$, $x \equiv 3 \cdot 2 = 6 \equiv 2 \pmod 4$. The two solutions modulo $8$ are $x \equiv 2$ and $x \equiv 6$. (Check $6 \cdot 2 = 12 \equiv 4$ and $6 \cdot 6 = 36 \equiv 4 \pmod 8$.)
• $4x \equiv 3 \pmod 6$: here $g = \gcd(4, 6) = 2$ and $2 \nmid 3$, so there is no solution.

# example-03-mod-inverse.py
def ext_gcd(a, b):
    """Return (g, s, t) with a*s + b*t = g = gcd(a, b). (From Chapter 22.)"""
    if b == 0:
        return (a, 1, 0)
    g, s1, t1 = ext_gcd(b, a % b)
    return (g, t1, s1 - (a // b) * t1)

def mod_inverse(a, m):
    """Return a^{-1} mod m, or None if gcd(a, m) != 1."""
    g, s, _ = ext_gcd(a % m, m)
    return s % m if g == 1 else None

print(mod_inverse(7, 26))   # 7 * 15 = 105 = 4*26 + 1
print(mod_inverse(3, 5))    # 3 * 2  = 6   = 1*5 + 1
print(mod_inverse(6, 8))    # gcd(6,8)=2, no inverse
# Expected output:
# 15
# 2
# None

🔄 Check Your Understanding 1. Does $5$ have an inverse modulo $12$? If so, find it. 2. How many solutions does $9x \equiv 6 \pmod{12}$ have? Find them. 3. Why does $2$ have no inverse modulo $10$, but $3$ does?

Answers

1. $\gcd(5, 12) = 1$, so yes. $5 \cdot 5 = 25 \equiv 1 \pmod{12}$, so $5^{-1} \equiv 5$. 2. $g = \gcd(9,12) = 3$ and $3 \mid 6$, so $3$ solutions. Divide by $3$: $3x \equiv 2 \pmod 4$, giving $x \equiv 2 \pmod 4$; the solutions modulo $12$ are $x \equiv 2, 6, 10$. 3. $\gcd(2,10)=2 \ne 1$ so $2$ is a zero divisor with no inverse; $\gcd(3,10)=1$ so $3$ is a unit ($3 \cdot 7 = 21 \equiv 1$).

23.4 The Chinese Remainder Theorem

Around the 3rd–5th century CE, the Chinese mathematician Sun Tzu posed a puzzle: there is a number; divided by $3$ the remainder is $2$, divided by $5$ the remainder is $3$, divided by $7$ the remainder is $2$. What is the number? In our notation, find $x$ with $$x \equiv 2 \pmod 3, \qquad x \equiv 3 \pmod 5, \qquad x \equiv 2 \pmod 7.$$ The remarkable claim of the Chinese Remainder Theorem (CRT) is that whenever the moduli are pairwise coprime, such a system has a solution, and the solution is unique modulo the product of the moduli. A number is completely determined by its remainders.

Theorem 23.5 (Chinese Remainder Theorem). Let $n_1, n_2, \dots, n_k$ be pairwise coprime positive integers (so $\gcd(n_i, n_j) = 1$ for $i \ne j$), and let $N = n_1 n_2 \cdots n_k$. For any integers $a_1, \dots, a_k$, the system $$x \equiv a_i \pmod{n_i} \quad (i = 1, \dots, k)$$ has a solution $x$, and that solution is unique modulo $N$.

The strategy first (existence is a construction). We don't merely prove a solution exists — we build it, because the construction is the algorithm. For each $i$, manufacture a number that is $\equiv 1$ modulo $n_i$ but $\equiv 0$ modulo every other $n_j$. Then $a_i$ times that number contributes exactly $a_i$ to the $i$-th congruence and $0$ to the others; summing over $i$ gives a solution. The "$\equiv 1$ here, $\equiv 0$ elsewhere" gadget is built from a modular inverse — which exists precisely because the moduli are coprime. Uniqueness is then a short divisibility argument.

Proof. For each $i$, let $N_i = N / n_i$ (the product of all the moduli except $n_i$). Because the $n_j$ are pairwise coprime, $n_i$ shares no factor with any $n_j$ ($j \ne i$), so $\gcd(N_i, n_i) = 1$. By Theorem 23.3, $N_i$ has an inverse modulo $n_i$; call it $M_i$, so $$N_i M_i \equiv 1 \pmod{n_i}.$$ Now define $$x = \sum_{i=1}^{k} a_i N_i M_i.$$ Fix a modulus $n_j$. Every term with $i \ne j$ contains the factor $N_i$, which is a multiple of $n_j$ (since $n_j$ is one of the factors of $N_i$ when $i \ne j$); so all those terms vanish modulo $n_j$. The surviving term is $a_j N_j M_j \equiv a_j \cdot 1 = a_j \pmod{n_j}$. Hence $x \equiv a_j \pmod{n_j}$ for every $j$ — a solution.

Uniqueness: suppose $x$ and $x'$ both solve the system. Then $x \equiv x' \pmod{n_i}$ for every $i$, so $n_i \mid (x - x')$ for every $i$. Because the $n_i$ are pairwise coprime, their product $N$ divides $x - x'$ (a fact that follows from unique factorization, Chapter 22). Therefore $x \equiv x' \pmod N$, so the solution is unique modulo $N$. $\blacksquare$

Solving Sun Tzu's puzzle by the construction. Here $n_1 = 3, n_2 = 5, n_3 = 7$, $N = 105$, and $a = (2, 3, 2)$.

Sum: $x = 140 + 63 + 30 = 233$. Reduce modulo $105$: $233 - 2\cdot 105 = 23$. So $x \equiv \mathbf{23} \pmod{105}$. Check all three: $23 = 7\cdot3 + 2$ (rem $2$ mod $3$ ✓), $23 = 4\cdot5 + 3$ (rem $3$ mod $5$ ✓), $23 = 3\cdot7 + 2$ (rem $2$ mod $7$ ✓). Sun Tzu's smallest answer is $23$.

💡 Intuition: CRT is a change of coordinates. Think of an integer modulo $105$ as a single "address." CRT says that address is equivalent to a triple of smaller addresses — its remainders mod $3$, mod $5$, and mod $7$. You can compute in the triple (component by component, with small numbers) and reassemble at the end. This is not just elegant; it is fast. Arithmetic on the components is cheaper than arithmetic on the big number, which is why CRT speeds up RSA decryption by roughly a factor of four — you decrypt modulo $p$ and modulo $q$ separately, then glue.

🚪 Threshold Concept: a number is its remainders. Before CRT, an integer feels atomic — a single indivisible thing. After CRT, you see that (for coprime moduli) an integer modulo $N$ is the same information as its tuple of residues — there is a perfect, reversible dictionary between them. This is your first encounter with an isomorphism: two structures that look different but are secretly identical, $\mathbb{Z}_{105} \leftrightarrow \mathbb{Z}_3 \times \mathbb{Z}_5 \times \mathbb{Z}_7$. Chapter 24 gives this idea its proper name and shows it is the organizing principle of modern algebra. Once you can move between an object and its coordinates, you can choose whichever representation makes a problem easy — a habit that recurs from CRT to the Fourier transform.

# example-04-crt.py
def ext_gcd(a, b):
    if b == 0:
        return (a, 1, 0)
    g, s1, t1 = ext_gcd(b, a % b)
    return (g, t1, s1 - (a // b) * t1)

def mod_inverse(a, m):
    g, s, _ = ext_gcd(a % m, m)
    return s % m if g == 1 else None

def crt(residues, moduli):
    """Solve x ≡ residues[i] (mod moduli[i]) for pairwise-coprime moduli.
    Returns the unique solution in [0, N) where N = product of moduli."""
    N = 1
    for m in moduli:
        N *= m
    x = 0
    for a_i, n_i in zip(residues, moduli):
        N_i = N // n_i
        x += a_i * N_i * mod_inverse(N_i, n_i)
    return x % N

print(crt([2, 3, 2], [3, 5, 7]))   # Sun Tzu's puzzle
# Expected output:
# 23

🔄 Check Your Understanding 1. Why does the construction require the moduli to be pairwise coprime — where exactly is it used? 2. Solve $x \equiv 1 \pmod 4$ and $x \equiv 2 \pmod 3$. (The answer is unique mod $12$.) 3. If you know $x \bmod 9$ and $x \bmod 4$, do you know $x \bmod 36$? What about knowing $x \bmod 6$ and $x \bmod 4$?

Answers

1. Coprimality guarantees each $N_i$ is invertible mod $n_i$ (Theorem 23.3) — without it, $M_i$ might not exist — and it is what lets the product $N$ divide $x - x'$ in the uniqueness argument. 2. Try $x = 5$: $5 \equiv 1 \pmod 4$ ✓ and $5 \equiv 2 \pmod 3$ ✓. So $x \equiv 5 \pmod{12}$. 3. Yes for $9$ and $4$ ($\gcd = 1$, so CRT applies and $9\cdot4 = 36$). No for $6$ and $4$: $\gcd(6,4) = 2 \ne 1$, the moduli aren't coprime, and $6\cdot4 = 24 \ne \operatorname{lcm}(6,4) = 12$ — the remainders can be inconsistent or fail to pin down $x$ mod $24$.

23.5 Fast modular exponentiation

RSA encryption is a single modular exponentiation: ciphertext $= m^{e} \bmod n$, where $e$ and $n$ are hundreds of digits long. The naive loop from §23.2 multiplies $e$ times — that is $10^{300}$ multiplications for a real key, which would not finish before the heat death of the universe. We need to compute $b^{e} \bmod n$ in time proportional to the number of digits of $e$, not its magnitude. The technique is modular exponentiation by squaring, also called square-and-multiply.

Definition (modular exponentiation). Modular exponentiation is the computation of $b^{e} \bmod n$ — the residue of $b$ raised to the power $e$, modulo $n$ — performed without ever forming the full integer $b^{e}$.

The idea is a divide-and-conquer recurrence on the exponent. To compute $b^e$:

$$b^{e} = \begin{cases} 1 & \text{if } e = 0, \\ \big(b^{e/2}\big)^2 & \text{if } e \text{ is even}, \\ b \cdot \big(b^{(e-1)/2}\big)^2 & \text{if } e \text{ is odd}. \end{cases}$$

Each step halves the exponent at the cost of one squaring (and, on odd steps, one extra multiplication). Halving $e$ down to $0$ takes about $\log_2 e$ steps, so the whole thing costs $O(\log e)$ multiplications — and by reducing modulo $n$ after every multiplication (§23.2), every intermediate value stays below $n^2$.

💡 Intuition: read the exponent in binary. Squaring repeatedly gives you $b^{1}, b^{2}, b^{4}, b^{8}, \dots$ — the powers of $b$ at the *bit positions* of the exponent. To assemble $b^{e}$, multiply together exactly those that correspond to $1$-bits in $e$. The exponent $13 = 1101_2$ has $1$-bits at positions $0, 2, 3$, so $b^{13} = b^{1} \cdot b^{4} \cdot b^{8}$.

Worked example: $3^{13} \bmod 7$ by square-and-multiply. Write $13 = 1101_2$. Build the square-and-multiply table, reducing mod $7$ at every step:

The running product after consuming all bits is $\mathbf{3}$, so $3^{13} \equiv 3 \pmod 7$. We did four squarings and three multiplications — seven small operations — instead of twelve. The savings explode with the size of $e$: a $2048$-bit exponent needs about $2048$ squarings, not $2^{2048}$ multiplications.

⚠️ Common Pitfall: reduce inside the loop, not at the end. The whole point is to keep numbers small. If you compute the full $b^{e}$ and only then take % n, you have gained nothing — the intermediate number is the very monster you were avoiding. Reduce after every squaring and every multiply. (Python's built-in pow(b, e, n) does exactly this; we implement it from scratch to see the mechanism, then you may use the built-in.)

Here is the iterative square-and-multiply, the version you will put in the Toolkit:

# example-05-mod-pow.py
def mod_pow(base, exp, mod):
    """Compute base**exp mod 'mod' in O(log exp) multiplications (square-and-multiply)."""
    result = 1
    base = base % mod
    while exp > 0:
        if exp & 1:                      # current low bit is 1: multiply it in
            result = (result * base) % mod
        base = (base * base) % mod       # square for the next bit position
        exp >>= 1                        # move to the next bit
    return result

print(mod_pow(3, 13, 7))                 # 3**13 mod 7
print(mod_pow(10, 100, 7))               # a googol mod 7 (Fermat: 10^6 ≡ 1)
print(mod_pow(7, 100, 10))               # last digit of 7**100, again
# Expected output:
# 3
# 4
# 1

🔗 Connection. This is a divide-and-conquer algorithm: it solves size-$e$ by reducing to size-$e/2$. Chapter 19 develops the general theory of such recurrences and the Master Theorem; the $O(\log e)$ cost here is the same logarithmic win you get from binary search and balanced trees. Halving the problem each step is the most important trick in algorithms, and modular exponentiation is where it makes cryptography physically possible.

🔄 Check Your Understanding 1. How many squarings does mod_pow perform for a $32$-bit exponent (roughly)? 2. Trace $2^{10} \bmod 1000$ with square-and-multiply ($10 = 1010_2$). What is the answer? 3. Why must the line base = base % mod come before the loop?

Answers

1. About $32$ — one squaring per bit of the exponent, so $O(\log_2 e)$. 2. $10 = 1010_2$: squares are $2^1=2$, $2^2=4$, $2^4=16$, $2^8=256$; the $1$-bits are at positions $1$ and $3$, so $2^{10} = 2^2 \cdot 2^8 = 4 \cdot 256 = 1024 \equiv 24 \pmod{1000}$. 3. So the base is reduced before the first squaring; otherwise a large base would make the first base*base needlessly huge (and for correctness the initial reduction guarantees every later product stays below $mod^2$).

23.6 Fermat's little theorem and Euler's theorem

We close with the two theorems that make RSA decrypt correctly. They answer a question the powers-of- $7$ table in §23.2 raised: why did the powers cycle back to $1$? Fermat and Euler tell you exactly when $a^{\text{something}} \equiv 1 \pmod n$, and that "something" is the secret to undoing encryption.

Start with the prime case, discovered by Pierre de Fermat in 1640.

Theorem 23.6 (Fermat's little theorem). If $p$ is prime and $p \nmid a$, then $$a^{p-1} \equiv 1 \pmod{p}.$$ Equivalently, for every integer $a$ (whether or not $p \mid a$), $a^{p} \equiv a \pmod{p}$.

The strategy first. The slick proof multiplies. Consider the $p-1$ nonzero residues $1, 2, \dots, p-1$. Multiply each by $a$. Because $a$ is invertible mod $p$ (it's coprime to the prime $p$), this just shuffles the nonzero residues — same set, different order. So the product of the original residues equals the product of the shuffled ones. Equate the two products, cancel the common $(p-1)!$ (legal, because each factor is invertible), and the leftover $a^{p-1}$ must be $1$.

Proof. Assume $p \nmid a$, so $\gcd(a, p) = 1$. Consider the set of nonzero residues $S = {1, 2, \dots, p-1}$ and the set $aS = {a\cdot 1, a\cdot 2, \dots, a\cdot(p-1)} \pmod p$.

Claim: $aS$ is a permutation of $S$. Each element $a \cdot i$ is nonzero mod $p$ (a product of two things coprime to $p$ is coprime to $p$, hence nonzero mod the prime $p$). And the map is injective: if $a i \equiv a j \pmod p$, then multiplying by $a^{-1}$ gives $i \equiv j$. An injective map from the finite set $S$ to itself is a bijection, so $aS$ contains exactly the same residues as $S$, reordered.

Therefore the products match: $$\prod_{i=1}^{p-1} (a i) \equiv \prod_{i=1}^{p-1} i \pmod p, \qquad \text{i.e.} \qquad a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod p.$$ Each of $1, 2, \dots, p-1$ is coprime to $p$, so $(p-1)!$ is invertible mod $p$; cancel it from both sides: $$a^{p-1} \equiv 1 \pmod p.$$ For the "every $a$" form, multiply by $a$: $a^{p} \equiv a \pmod p$, which also holds trivially when $p \mid a$ (both sides $\equiv 0$). $\blacksquare$

Check: $p = 7$, $a = 2$. Fermat predicts $2^{6} \equiv 1 \pmod 7$. Indeed $2^6 = 64 = 9\cdot 7 + 1 \equiv 1 \pmod 7$. ✓

Fermat needs the modulus to be prime. RSA uses a modulus $n = pq$ that is deliberately composite, so we need Euler's generalization. The bridge is a counting function.

Definition (Euler's totient). Euler's totient $\phi(n)$ counts the integers in ${1, 2, \dots, n}$ that are coprime to $n$ — equivalently, the number of *units* modulo $n$ (the residues that have an inverse, by Theorem 23.3).

Two facts about $\phi$ make it computable (the second is proved in the exercises via CRT):

• For a prime $p$: $\phi(p) = p - 1$ (every nonzero residue is coprime to a prime).
• $\phi$ is multiplicative for coprime arguments: if $\gcd(m, n) = 1$, then $\phi(mn) = \phi(m)\,\phi(n)$. In particular, for distinct primes $p, q$: $\phi(pq) = (p-1)(q-1)$.

That last identity is exactly the number RSA's key generation computes. With $\phi$ in hand, Euler's theorem (Leonhard Euler, 1763) generalizes Fermat from primes to all moduli.

Theorem 23.7 (Euler's theorem). If $\gcd(a, n) = 1$, then $$a^{\phi(n)} \equiv 1 \pmod{n}.$$

The strategy first. The same shuffling argument as Fermat, but on a smaller stage. Instead of all nonzero residues, use only the $\phi(n)$ units — the residues coprime to $n$. Multiplying them by $a$ (itself a unit) permutes the units, exactly as before. Equate the two products and cancel the (invertible) product of all units; the leftover $a^{\phi(n)}$ is forced to $1$. Fermat is the special case $n = p$, where every nonzero residue is a unit and $\phi(p) = p-1$.

Proof. Let $U = \{u_1, \dots, u_{\phi(n)}\}$ be the units modulo $n$ — the residues coprime to $n$. Since $\gcd(a, n) = 1$, $a$ is a unit, and the map $u \mapsto au \pmod n$ sends units to units (a product of units is a unit) and is injective (if $au_i \equiv au_j$, multiply by $a^{-1}$ to get $u_i \equiv u_j$). So multiplication by $a$ permutes $U$. Equating the product of $U$ with the product of $aU$: $$\prod_{i=1}^{\phi(n)} (a u_i) \equiv \prod_{i=1}^{\phi(n)} u_i \pmod n, \qquad \text{i.e.} \qquad a^{\phi(n)} \prod_i u_i \equiv \prod_i u_i \pmod n.$$ The product $\prod_i u_i$ is a product of units, hence itself a unit, so it cancels: $$a^{\phi(n)} \equiv 1 \pmod n. \qquad \blacksquare$$

Check: $n = 10$, $a = 3$. The units mod $10$ are $\{1, 3, 7, 9\}$, so $\phi(10) = 4$. Euler predicts $3^{4} \equiv 1 \pmod{10}$. Indeed $3^4 = 81 = 8\cdot 10 + 1 \equiv 1 \pmod{10}$. ✓ (This is why the last-digit cycles in §23.2 have length dividing $\phi(10) = 4$.)

Now the punchline — why RSA works, in one paragraph. RSA picks $n = pq$, a public exponent $e$, and a private exponent $d$ with $ed \equiv 1 \pmod{\phi(n)}$ — that is, $d = e^{-1} \bmod \phi(n)$, a modular inverse (§23.3). Encryption sends a message $m$ to $c = m^{e} \bmod n$ (a fast modular exponentiation, §23.5). Decryption computes $c^{d} \bmod n = m^{ed} \bmod n$. Because $ed = 1 + k\,\phi(n)$ for some integer $k$, $$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 for the middle step. Decryption recovers the message exactly because raising to the $\phi(n)$ power resets to $1$. Every ingredient — coprimality, the modular inverse, fast exponentiation, $\phi(pq) = (p-1)(q-1)$, Euler's theorem — is something you now own.

🚪 Threshold Concept: the trapdoor. Encryption and decryption are the same operation — modular exponentiation — with two different exponents that are inverses modulo $\phi(n)$. Anyone can encrypt (with the public $e$); only the holder of $d$ can decrypt. And here is the asymmetry that secures the internet: computing $d$ from $e$ requires $\phi(n) = (p-1)(q-1)$, which requires factoring $n$ into $p$ and $q$ — and factoring a $2048$-bit number is believed to be computationally infeasible. Easy forward, hard backward: a trapdoor. You will build the full machine in Chapter 25, and Chapter 24 will explain the group-theoretic reason it must work.

🔄 Check Your Understanding 1. Use Fermat's little theorem to find $2^{100} \bmod 7$ quickly. 2. Compute $\phi(12)$ by listing the units. Then verify Euler's theorem for $a = 5$. 3. In RSA with $p = 3$, $q = 11$, what is $\phi(n)$? If $e = 7$, what equation does $d$ satisfy?

Answers

1. $2^6 \equiv 1 \pmod 7$ (Fermat), and $100 = 6\cdot16 + 4$, so $2^{100} = (2^6)^{16}\cdot 2^4 \equiv 1\cdot 16 \equiv 2 \pmod 7$. 2. Units mod $12$ are ${1, 5, 7, 11}$, so $\phi(12) = 4$. Euler: $5^4 = 625 = 52\cdot 12 + 1 \equiv 1 \pmod{12}$ ✓. 3. $\phi(33) = (3-1)(11-1) = 20$; $d$ satisfies $7d \equiv 1 \pmod{20}$, so $d = 7^{-1} \bmod 20 = 3$ (since $7\cdot 3 = 21 \equiv 1$).

Project Checkpoint: the modular toolkit for numbertheory.py

Chapter 22 began dmtoolkit/numbertheory.py with gcd, ext_gcd, and sieve. This chapter adds the three functions that turn that module into a cryptography engine — exactly the routines RSA will call in Chapter 25: mod_inverse, mod_pow, and crt. Append to dmtoolkit/numbertheory.py:

def mod_inverse(a, m):
    """Return a^{-1} mod m (the unique x in [0,m) with a*x ≡ 1), or None if gcd(a,m) != 1.
    Uses ext_gcd from Chapter 22: if a*s + m*t = 1, then s is the inverse."""
    g, s, _ = ext_gcd(a % m, m)
    return s % m if g == 1 else None

def mod_pow(base, exp, mod):
    """Compute base**exp mod 'mod' in O(log exp) multiplications (square-and-multiply)."""
    result, base = 1, base % mod
    while exp > 0:
        if exp & 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exp >>= 1
    return result

def crt(residues, moduli):
    """Solve x ≡ residues[i] (mod moduli[i]) for pairwise-coprime moduli;
    return the unique solution in [0, N) where N is the product of the moduli."""
    N = 1
    for m in moduli:
        N *= m
    x = 0
    for a_i, n_i in zip(residues, moduli):
        N_i = N // n_i
        x += a_i * N_i * mod_inverse(N_i, n_i)
    return x % N

A quick self-test wiring the pieces together:

print(mod_inverse(7, 26))         # 15  (7*15 = 105 ≡ 1 mod 26)
print(mod_pow(3, 13, 7))          # 3   (square-and-multiply)
print(crt([2, 3, 2], [3, 5, 7]))  # 23  (Sun Tzu)
# Expected output:
# 15
# 3
# 23

These three are the operational core of RSA. mod_pow is encryption and decryption; mod_inverse computes the private exponent $d$ from the public $e$; crt is the standard speed-up that lets a real implementation decrypt modulo $p$ and $q$ separately and reassemble. In Chapter 24 the abstract structure behind them gets a name (groups, rings, fields), and in Chapter 25 you assemble them into crypto.py and watch a message encrypt and decrypt end to end. The Toolkit's numbertheory.py module is now feature-complete for cryptography.

Summary

Modular arithmetic is the arithmetic of residue classes — the finite number systems $\mathbb{Z}_n$ that underlie hashing, overflow, and cryptography. Reference table of results:

Decision aids.

• To divide by $a$ modulo $n$: check $\gcd(a, n) = 1$; if so, multiply by $a^{-1} = $ mod_inverse(a, n).
• To solve $ax \equiv b \pmod n$: let $g = \gcd(a, n)$. No solution if $g \nmid b$; otherwise $g$ solutions, found by dividing through by $g$ and inverting.
• To compute a huge power $b^e \bmod n$: use mod_pow (square-and-multiply); never form $b^e$.
• To simplify $a^e \bmod n$ when $\gcd(a, n) = 1$: reduce the exponent modulo $\phi(n)$ first (Euler), then exponentiate.
• To solve simultaneous congruences with coprime moduli: use crt.

Toolkit additions (numbertheory.py): mod_inverse(a, m), mod_pow(base, exp, mod), crt(residues, moduli) — joining Chapter 22's gcd, ext_gcd, sieve. The module is now the arithmetic engine for RSA.

Spaced Review

Retrieval keeps knowledge available. Answer from memory before checking.

1. (Ch. 22) State Bézout's identity. How does it guarantee that $a^{-1} \bmod n$ exists when $\gcd(a, n) = 1$ — and which Chapter 22 algorithm actually computes the inverse?
2. (Ch. 22) Use the extended Euclidean algorithm to find $\gcd(26, 7)$ and integers $s, t$ with $26s + 7t = \gcd$. (You computed this inside §23.3 — reproduce it.)
3. (Ch. 22) The CRT uniqueness proof claims "pairwise-coprime $n_i$ all dividing $x - x'$ forces their product to divide $x - x'$." Which Chapter 22 theorem underlies this, and why does it fail if the moduli share a factor?
4. (Ch. 6) The exercises ask you to prove $\phi$ is multiplicative and to prove Fermat's little theorem holds for all $n$ by induction on $a$ (using $a^p \equiv a$). Which proof technique from Chapter 6 would you reach for to prove "$a^p \equiv a \pmod p$ for all integers $a \ge 0$," and what is the inductive step's key algebraic fact?

Answers

1. Bézout: for any integers $a, n$ there exist integers $s, t$ with $as + nt = \gcd(a, n)$. When $\gcd(a,n) = 1$, that reads $as + nt = 1$; modulo $n$ it becomes $as \equiv 1$, so $s = a^{-1}$. The extended Euclidean algorithm computes $s$ and $t$. 2. $26 = 3\cdot7 + 5$, $7 = 1\cdot5 + 2$, $5 = 2\cdot2 + 1$; back-substitute to get $1 = 3\cdot26 - 11\cdot7$, so $\gcd = 1$, $s = 3$, $t = -11$.
2. The Fundamental Theorem of Arithmetic (unique prime factorization): pairwise-coprime numbers have disjoint prime factorizations, so their product's prime powers all appear in $x - x'$; if they shared a factor, the product would over-count that factor and need not divide $x - x'$ (use $\operatorname{lcm}$, not the product). 4. Mathematical induction on $a$: base $0^p \equiv 0$; inductive step uses the binomial theorem / "freshman's dream" $(a+1)^p \equiv a^p + 1 \pmod p$ (every middle binomial coefficient $\binom{p}{k}$ is divisible by the prime $p$), then the hypothesis $a^p \equiv a$ gives $(a+1)^p \equiv a + 1$.

What's Next

You now have the operations of modular arithmetic — congruence, inverses, the CRT, fast exponentiation, Fermat and Euler — and the Toolkit functions that implement them. But we have been quietly relying on structure: that the units modulo $n$ form a set closed under multiplication where every element has an inverse, that you can cancel invertible factors, that $\mathbb{Z}_n$ behaves like a number system. Chapter 24 names these structures — groups, rings, and fields — and proves the general theorems ($\mathbb{Z}_n$ is a ring; the units form a group; $\mathbb{Z}_p$ for prime $p$ is a field) that explain why every trick in this chapter had to work. With that vocabulary, Fermat and Euler become one-line corollaries of Lagrange's theorem, and the door opens to finite fields — the algebra behind both RSA (Chapter 25) and the error-correcting codes of Chapter 26.