ISEGORIA / MATH ENCYCLOPEDIA
Number theory: patterns in the integers
Congruences, primes, and public-key ideas.
Before you begin: Algebra and proof
Predict, manipulate, then check your reasoning against the example and question. Graphs illustrate the mathematics; they do not replace a proof.
1. Modular clocks
Wind the integers onto a clock with n hours, one turn of the spiral for every n integers. Two integers are congruent modulo n exactly when they land on the same ray. On the right, multiplication becomes repeated addition: b steps of size a from 0 end on the hour a·b mod n, and replacing a by its residue does not change where you land.
Worked example. For n=12, 17 and 5 occupy the same residue class.
Watch out. A congruence is an equivalence relation, not ordinary equality.
Why does multiplication preserve congruence?
If n divides a − a′, it divides ab − a′b = (a − a′)b, so ab ≡ a′b. On the clock, steps of size a and of size a mod n reach the same hours.
2. Sieve of Eratosthenes
Write the numbers from 1 to the limit in rows of ten. Each prime p up to the square root of the limit crosses out its multiples, starting at p², in its own colour; whatever survives, apart from 1, is prime. Press Play to run the sieve prime by prime, and compare the prime count π(x) with x/ln x and the logarithmic integral li(x).
Worked example. Up to 30 there are ten primes; up to 100 there are twenty-five, while 100/ln 100 ≈ 21.7 and li(100) ≈ 30.1.
Watch out. π(x) is neither x/ln x nor li(x) for finite x; the prime number theorem only says the ratios tend to 1.
Why can crossing out stop at √x, and why start each prime at p²?
A composite number has a prime factor no larger than its square root, and any multiple kp with k < p has a smaller prime factor, so it was already crossed out.
3. RSA key intuition
Pick two different primes p and q. The public key is N = pq with an exponent e coprime to φ(N) = (p − 1)(q − 1), and the private exponent d is the inverse of e modulo φ(N). The left plot shows encryption for every message at once: it is a permutation of the residues. The right plot shows why decryption works: the powers of m repeat, and ed = 1 + t·φ(N) brings m back.
Worked example. For p = 5 and q = 11, N = 55 and φ(N) = 40. With e = 3, d = 27 because 3·27 = 81 ≡ 1 (mod 40); the message 7 encrypts to 7³ mod 55 = 13, and 13²⁷ mod 55 = 7.
Watch out. Toy keys are not secure; real RSA uses much larger primes and padding.
What makes the decryption exponent special?
It is an inverse of e modulo φ(N), so m^(ed) = m·(m^φ(N))^t ≡ m by Euler's theorem; for squarefree N this holds even when m shares a factor with N.