Chapter 22 — Key Takeaways
Number Theory Foundations: Divisibility, Primes, and the Fundamental Theorem of Arithmetic. A one-page reference. The single habit to keep: when you see $a \mid b$, rewrite it as $b = ak$.
Definitions at a glance
| Term | Definition | Notation / note |
|---|---|---|
| Divisibility | $a \mid b$ iff $\exists\,k\in\mathbb{Z}:\ b = ak$ (with $a\neq 0$) | A statement, not a number; $a\nmid b$ if no such $k$ |
| Prime | $p>1$ whose only positive divisors are $1$ and $p$ | $1$ is not prime |
| Composite | $n>1$ that is not prime: $n=ab$, $1| $1$ is not composite |
|
| gcd | Largest $d$ with $d\mid a$ and $d\mid b$ | $\gcd(0,0)=0$ by convention |
| Coprime | $\gcd(a,b)=1$ (share no prime factor) | a.k.a. relatively prime |
| Bézout coefficients | Integers $x,y$ with $ax+by=\gcd(a,b)$ | exist for any $a,b$ not both 0; usually signed |
| lcm | Smallest positive common multiple | $\operatorname{lcm}(a,b)=ab/\gcd(a,b)$ |
The theorems (and how each is proved)
| Theorem | Statement | Proof engine |
|---|---|---|
| Transitivity | $a\mid b \wedge b\mid c \Rightarrow a\mid c$ | direct: unpack–combine–repackage |
| Linear combination | $a\mid b \wedge a\mid c \Rightarrow a\mid(mb+nc)$ | direct: factor out $a$ |
| Infinitude of primes (Euclid) | infinitely many primes | contradiction: $N=p_1\cdots p_r+1$ has a new prime divisor |
| Division Algorithm | unique $q,r$: $a=dq+r$, $0\le r| well-ordering (exists) + difference-is-0 (unique) |
|
| Euclid key lemma | $\gcd(a,b)=\gcd(b,\,a\bmod b)$ | both pairs share all common divisors |
| Bézout's identity | $\exists x,y:\ ax+by=\gcd(a,b)$ | well-ordering: smallest positive $ax+by$ |
| Euclid's Lemma | $p$ prime, $p\mid ab \Rightarrow p\mid a$ or $p\mid b$ | Bézout + linear combination |
| FTA | unique prime factorization of $n>1$ | strong induction (exists) + Euclid's Lemma (unique) |
Formulas to memorize
$$a = dq + r,\quad 0 \le r < d \qquad\text{(Division Algorithm)}$$ $$\gcd(a,b) = \gcd(b,\, a \bmod b),\qquad \gcd(g,0)=g \qquad\text{(Euclid)}$$ $$ax + by = \gcd(a,b) \qquad\text{(Bézout)}$$ $$\gcd(a,b)=\prod_p p^{\min(a_p,b_p)},\quad \operatorname{lcm}(a,b)=\prod_p p^{\max(a_p,b_p)}$$ $$\boxed{\gcd(a,b)\cdot\operatorname{lcm}(a,b) = ab \quad (a,b>0)}$$
Extended Euclid back-substitution (returns $(g,x,y)$): base $\text{ext\_gcd}(a,0)=(a,1,0)$; recursive $$x = y',\qquad y = x' - \left\lfloor a/b\right\rfloor\,y' \quad\text{where } (g,x',y')=\text{ext\_gcd}(b,\,a\bmod b).$$
Algorithms & cost
| Need | Use | Cost |
|---|---|---|
| All primes $\le n$ | Sieve of Eratosthenes (cross from $p^2$) | $O(n\log\log n)$ |
| Test one huge number for primality | Not the sieve — Fermat/Miller–Rabin (Ch. 23) | — |
| $\gcd(a,b)$ | Euclidean algorithm | $O(\log\min(a,b))$ |
| $\gcd$ and Bézout $x,y$ | Extended Euclidean | $O(\log\min(a,b))$ |
| $\operatorname{lcm}(a,b)$ | $ab/\gcd(a,b)$ | gcd cost |
| Factor $n$ | Trial division to $\sqrt n$ | $O(\sqrt n)$ — slow on purpose (RSA security) |
Euclid's worst case = consecutive Fibonacci numbers (every quotient is 1).
Decision aid: "which tool?"
- Reduce a fraction / find common structure → gcd (Euclid, never factor).
- Need to undo a multiplication mod $n$ → you'll need a modular inverse → compute Bézout with extended Euclid, reduce the coefficient mod $n$ (Ch. 23).
- Asked "is this number prime?" for small numbers → sieve; for cryptographic sizes → probabilistic test (Ch. 23).
- "In how many ways does this factor?" → exactly one (FTA) — read off the prime fingerprint.
- lcm of two numbers → compute gcd first, then $ab/\gcd$.
Common pitfalls
| Pitfall | Fix |
|---|---|
| Reading $a\mid b$ as the fraction $a/b$ | $a\mid b$ is a true/false statement; $3\mid 12$ means 3 is a divisor |
| Thinking $p_1\cdots p_r+1$ is always prime | It has a new prime divisor; $2\cdot3\cdot5\cdot7\cdot11\cdot13+1=30031=59\cdot509$ |
Expecting -17 % 5 == -2 (the C/Java answer) |
Python gives 3 (canonical $0\le r |
| Panicking when a Bézout coefficient is negative | Expected — reduce mod $n$ later to land in $[0,n)$ |
| Treating 1 as prime | 1 is excluded so factorization is unique |
| Applying Euclid's Lemma with a composite | Fails: $4\mid 2\cdot6$ but $4\nmid 2$ and $4\nmid 6$ |
Toolkit additions — dmtoolkit/numbertheory.py
| Function | Signature | Returns |
|---|---|---|
gcd |
gcd(a, b) |
$\gcd(a,b)$ via Euclid; gcd(0,0)=0 |
ext_gcd |
ext_gcd(a, b) |
(g, x, y) with a*x + b*y == g |
sieve |
sieve(n) |
list of all primes $\le n$ |
Coming in Ch. 23: mod_inverse(a, m), mod_pow(b, e, m), crt(rs, ms) — ext_gcd becomes the
engine of mod_inverse, which becomes the RSA private key.