Chapter 23 — Key Takeaways
Modular Arithmetic: Clock Math, Congruences, and the Chinese Remainder Theorem. The reread-before-an-exam card. Everything here is proved in index.md.
Core definitions
| Term | Definition | Notation |
|---|---|---|
| Congruence | $a \equiv b \pmod n \iff n \mid (a - b) \iff a, b$ same remainder mod $n$ | \equiv ... \pmod{n} |
| Modulus | the $n$ in a congruence | $n$ |
| Residue | unique $r \in \{0,\dots,n-1\}$ with $a \equiv r$; computed by the operator $a \bmod n$ | \bmod |
| Residue class | the set of all integers congruent to $a$ mod $n$ | $[a]$ |
| $\mathbb{Z}_n$ | the set of residues $\{0, 1, \dots, n-1\}$ | $\mathbb{Z}_n$ |
| Modular inverse | $a^{-1}$ with $a \cdot a^{-1} \equiv 1 \pmod n$ (exists iff $\gcd(a,n)=1$) | $a^{-1}$ |
| Unit (mod $n$) | a residue that has an inverse (i.e. coprime to $n$) | — |
| Totient $\phi(n)$ | count of integers in $\{1,\dots,n\}$ coprime to $n$ = number of units | $\phi(n)$ |
Relation vs. operator:
≡ (mod n)is a true/false statement;mod n($\bmod$) is an operator yielding one number.17 ≡ 5 (mod 4)is true;17 mod 4 = 1. The math residue is non-negative (Python%agrees; C/Java do not for negatives).
The key theorems (one line each)
| # | Theorem | Statement |
|---|---|---|
| 23.1 | Congruence is an equivalence relation | reflexive + symmetric + transitive; classes = residue classes |
| 23.2 | Arithmetic well-defined | $a\equiv b,\, c\equiv d \Rightarrow a\pm c\equiv b\pm d$ and $ac \equiv bd \pmod n$ |
| 23.3 | Inverse existence | $a^{-1} \bmod n$ exists $\iff \gcd(a,n) = 1$; then $a^{-1} = s$ from $as + nt = 1$ |
| 23.4 | Linear congruence | $ax \equiv b \pmod n$ solvable $\iff g=\gcd(a,n)$ divides $b$; then exactly $g$ solutions |
| 23.5 | Chinese Remainder Theorem | pairwise-coprime $n_i$: $\{x \equiv a_i \pmod{n_i}\}$ has a unique solution mod $N=\prod n_i$ |
| 23.6 | Fermat's little theorem | $p$ prime, $p \nmid a \Rightarrow a^{p-1}\equiv 1\pmod p$; for all $a$: $a^p \equiv a$ |
| 23.7 | Euler's theorem | $\gcd(a,n)=1 \Rightarrow a^{\phi(n)}\equiv 1\pmod n$ |
Formulas to memorize
$$a^{-1} \bmod n: \quad as + nt = 1 \ \Rightarrow\ a^{-1} \equiv s \pmod n \quad (\text{extended Euclid})$$
$$\text{CRT: } x = \sum_{i} a_i N_i M_i \bmod N, \quad N_i = N/n_i, \quad M_i = N_i^{-1} \bmod n_i$$
$$b^e = \begin{cases} 1 & e=0 \\ (b^{e/2})^2 & e \text{ even} \\ b\cdot(b^{(e-1)/2})^2 & e \text{ odd}\end{cases} \quad \Rightarrow\ O(\log e) \text{ mults}$$
$$\phi(p) = p-1, \qquad \phi(pq) = (p-1)(q-1) \ (p \ne q \text{ prime}), \qquad \gcd(m,n)=1 \Rightarrow \phi(mn)=\phi(m)\phi(n)$$
$$\text{Euler exponent reduction: } \gcd(a,n)=1 \ \Rightarrow\ a^e \equiv a^{\,e \bmod \phi(n)} \pmod n$$
"When to use what" decision rules
| Goal | Do this |
|---|---|
| Test $a \equiv b \pmod n$ | check (a - b) % n == 0 |
| Keep numbers small in a $\pm,\times$ chain | reduce mod $n$ after every operation (Thm 23.2) |
| Divide by $a$ modulo $n$ | verify $\gcd(a,n)=1$, then multiply by mod_inverse(a, n) |
| Solve $ax \equiv b \pmod n$ | $g=\gcd(a,n)$: if $g \nmid b$ → no solution; else divide through by $g$, invert, get $g$ solutions |
| Compute $b^e \bmod n$ for huge $e$ | mod_pow(b, e, n) (square-and-multiply); never form $b^e$ |
| Shrink a large exponent (coprime base) | replace $e$ by $e \bmod \phi(n)$ (Euler), then exponentiate |
| Reassemble from remainders (coprime moduli) | crt(residues, moduli) |
| Speed up RSA decryption | CRT: work mod $p$ and mod $q$, then glue (~4× faster) |
RSA in one box (the payoff — full build is Ch. 25)
| Step | Operation | Tool used |
|---|---|---|
| Keygen | pick primes $p,q$; $n=pq$; $\phi(n)=(p-1)(q-1)$; pick $e$; $d = e^{-1} \bmod \phi(n)$ | mod_inverse |
| Encrypt | $c = m^e \bmod n$ | mod_pow |
| Decrypt | $m = c^d \bmod n$ | mod_pow |
| Why it works | $m^{ed} = m^{1+k\phi(n)} = m\cdot(m^{\phi(n)})^k \equiv m \pmod n$ | Euler's theorem |
| Why it's secure | recovering $d$ needs $\phi(n)$ needs factoring $n$ — believed infeasible (trapdoor) | hardness of factoring |
Common pitfalls
| Pitfall | Reality |
|---|---|
| "I can cancel any common factor" | No. Cancel only invertible factors. $2\cdot3\equiv2\cdot0\pmod6 \not\Rightarrow 3\equiv0$ |
Confusing \pmod and \bmod |
one is a relation (T/F), one is an operator (a number) |
| Forgetting negative-residue convention | math residue is non-negative; -7 % 3 = 2 in Python, but -1 in C/Java |
Computing $b^e$ then % n |
defeats the purpose; reduce inside the square-and-multiply loop |
| Reducing the exponent mod $n$ | wrong modulus — the exponent reduces mod $\phi(n)$ (Euler), not mod $n$ |
| Applying CRT to non-coprime moduli | requires pairwise coprime; otherwise inverses may not exist / solution not unique mod $\prod n_i$ |
| Using Euler when $\gcd(a,n)\ne1$ | Euler's theorem requires $a$ coprime to $n$ |
Toolkit additions (dmtoolkit/numbertheory.py)
| Function | Signature | Returns |
|---|---|---|
| Modular inverse | mod_inverse(a, m) |
$a^{-1} \bmod m$, or None if $\gcd(a,m)\ne1$ |
| Fast power | mod_pow(base, exp, mod) |
$\text{base}^{\text{exp}} \bmod \text{mod}$ in $O(\log \text{exp})$ |
| Chinese remainder | crt(residues, moduli) |
unique $x \in [0, N)$ solving the system; $N=\prod$ moduli |
Builds on Ch. 22's gcd, ext_gcd, sieve. Together they are the arithmetic engine for crypto.py (Ch. 25).
Worked-number quick reference (verify yourself)
| Computation | Result |
|---|---|
| $7^{-1} \bmod 26$ | $15$ (since $7\cdot15 = 105 \equiv 1$) |
| $3x \equiv 4 \pmod 5$ | $x \equiv 3$ |
| $6x \equiv 4 \pmod 8$ | $x \equiv 2, 6$ (two solutions) |
| $4x \equiv 3 \pmod 6$ | no solution ($\gcd=2 \nmid 3$) |
| CRT $(2 \bmod 3,\, 3 \bmod 5,\, 2 \bmod 7)$ | $x \equiv 23 \pmod{105}$ |
| $3^{13} \bmod 7$ | $3$ |
| $2^6 \bmod 7$ (Fermat) | $1$ |
| $\phi(10),\ \phi(12),\ \phi(33)$ | $4,\ 4,\ 20$ |
| $3^4 \bmod 10$ (Euler) | $1$ |
Next: Chapter 24 names the structures behind all of this — groups, rings, fields — making Fermat and Euler corollaries of Lagrange's theorem.