Number Theory — Between the Lines
From divisibility and congruences to RSA cryptography. An eight-part series that answers the questions textbooks leave between the lines, building intuition for number theory.
What does it mean to "divide evenly"? Why number theory begins with mod
The modular reduction map is a projection that deliberately discards information. Clocks, days of the week, and the competitive-programming modulus 10^9+7 all share the same algebraic structure. From the definition of divisibility through congruences to the ring Z/nZ, we uncover the reason number theory starts where it does.
Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division
The recursion gcd(a,b) = gcd(b, a mod b) hides an invariant: the set of common divisors never changes. Starting from a naive subtraction-based method and upgrading to division, we derive Bezout's identity, the extended Euclidean algorithm, and modular inverses.
Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says
Unique prime factorization is not as obvious as it seems. Through a counterexample in Z[sqrt(-5)], we witness uniqueness break down, then prove both the existence and uniqueness parts of the Fundamental Theorem, and survey the Sieve of Eratosthenes and the linear sieve.
Fermat's little theorem and the hidden symmetry of remainders
From the group structure of (Z/pZ)* we derive Fermat's little theorem, explain why the set {a, 2a, ..., (p-1)a} is a permutation of {1, 2, ..., p-1}, show that a^{p-2} is the modular inverse, and generalize to Euler's theorem.
The Chinese Remainder Theorem: why simultaneous congruences can be merged
We view CRT as the number-theoretic incarnation of divide-and-conquer, prove the ring isomorphism Z/mnZ = Z/mZ x Z/nZ, and show how Garner's algorithm avoids overflow in practice.
Quadratic residues: why exactly half the nonzero elements mod p are squares
The squaring map x -> x^2 is 2-to-1, which forces exactly (p-1)/2 quadratic residues. We develop the Legendre symbol, Euler's criterion, the law of quadratic reciprocity, and the Tonelli-Shanks algorithm for extracting square roots modulo a prime.
Continued fractions: how to find the best rational approximation to any number
Continued fractions are the Euclidean algorithm in disguise. We develop convergents and the best-approximation property, compute the continued fraction of sqrt(2), connect it to Pell's equation, and sketch the Stern-Brocot tree.
Number theory meets cryptography: why RSA works and what makes it secure
Every theorem in this series -- Fermat, Euler, the extended Euclidean algorithm, CRT -- corresponds to a component of the RSA cryptosystem. We trace each connection, work through a concrete example, and discuss the factoring barrier that underpins RSA's security.