🔢 Number Theory

What you’ll learn

1. The Questions a Child Can AskCharacterise number theory by its signature asymmetry — questions statable to a ten-year-old whose answers take centuries or remain open — and set up the course's argument that its long-prized uselessness was temporary.Goldbach's 1742 conjecture, the twin prime conjecture, and Fermat's Last Theorem can each be stated in one sentence to a child, and each took centuries or is still open; this gap between the simplicity of the question and the depth of the answer is what defines the subject. G. H. Hardy celebrated number theory in 1940 precisely for having no practical use, and within four decades the field was securing the world's communications — the through-line this course follows to its end.
2. Divisibility Is the Whole SubjectState the divisibility relation precisely as an existence claim, and apply the division algorithm — the guarantee of a unique quotient and remainder — as the operation that generates almost everything downstream.The relation a | b means there exists an integer k with b = ak, an existence claim that unfolds into algebra exactly as the definition of 'even' does, and 'even' is simply the case a = 2. The division algorithm guarantees that for any a and any n > 0 there are unique q and r with a = qn + r and 0 ≤ r < n, and its uniqueness — not its existence — is what makes remainders into reliable objects, generating the Euclidean algorithm, modular arithmetic, and everything after.
3. The Atoms, and Why 1 Isn't OneExplain the Fundamental Theorem of Arithmetic and why excluding 1 from the primes is forced by uniqueness rather than chosen by convention, and reconstruct Euclid's proof that the primes are infinite.Every integer above 1 factors into primes in exactly one way, and that uniqueness is why 1 cannot be prime: admitting it would give every number infinitely many factorisations and destroy the theorem the whole subject rests on. Euclid's argument that the primes never run out takes any finite list, forms N = (their product) + 1, and observes that N's prime factor cannot be on the list — an argument that is constructive in spirit and does not, contrary to its usual presentation, require contradiction.
4. How the Primes Thin OutDescribe the distribution of primes quantitatively — the sieve of Eratosthenes, the counting function π(x), and the Prime Number Theorem's x/ln x — and explain why primes are simultaneously predictable in bulk and unpredictable individually.Counted exactly, the primes thin out on a schedule: π(10) = 4 but π(10¹⁰) = 455,052,511, a density falling from 40% to 4.5%, and the Prime Number Theorem says π(x) approaches x/ln x. Yet individually they remain erratic — arbitrarily long prime-free gaps exist and can be constructed trivially, while whether pairs two apart go on forever is still unknown, though Zhang's 2013 breakthrough bounded some gap at 70 million and the Polymath collaboration drove it to 246.
5. The Oldest Algorithm Still in UseExecute the Euclidean algorithm for gcd, explain why replacing (a, b) with (b, a mod b) preserves the gcd while forcing termination, and state Bézout's identity as the extra result the algorithm silently computes.Euclid's algorithm computes gcd by repeatedly replacing (a, b) with (b, a mod b), a move justified because any common divisor of a and b also divides a − qb, so the gcd is preserved while the numbers shrink and must terminate. It is fast for reasons the factorisation route is not — gcd(1,234,567, 7,654,321) takes a handful of steps where factoring both numbers would be hopeless at scale — and run backwards it yields Bézout's identity, the existence of x and y with ax + by = gcd(a, b), which is what makes modular inverses exist and RSA keys computable.
6. Clock ArithmeticCompute in modular arithmetic, justify why addition and multiplication are well defined on remainders while division is not, and recognise the everyday systems built on it.Working modulo n means keeping only remainders, and the reason this is a coherent arithmetic rather than a trick is that congruence respects addition and multiplication — a fact provable in two lines from the definition a ≡ b (mod n) ⟺ n | (a − b). Division is the exception: 2x ≡ 4 (mod 6) has multiple solutions because 2 shares a factor with 6, so inverses exist precisely when gcd(a, n) = 1. ISBN and IBAN check digits are modular arithmetic doing routine work, and modular exponentiation is where the asymmetry the course is building toward first appears.
7. Fermat's Little TheoremState and apply Fermat's little theorem, use it as a primality test, and understand why its failure cases — the Carmichael numbers — make it a test for compositeness rather than a proof of primality.For prime p and a not divisible by p, a^(p−1) ≡ 1 (mod p) — a result that turns exponentiation modulo a prime into a cycle and lets a 300-digit number be screened for primality in milliseconds. The test is one-sided: failing it proves compositeness outright with no factor exhibited, while passing it proves nothing, since Carmichael numbers such as 561 = 3 × 11 × 17 pass for every base coprime to them. Combined with fast modular exponentiation by repeated squaring, this is how the primes used in cryptography are actually found.
8. Euler's Generalisation, and the TrapdoorExtend Fermat's theorem to composite moduli via Euler's totient φ(n) and Euler's theorem, and identify the specific structural fact — that φ(pq) requires knowing p and q — which creates a trapdoor.Euler's totient φ(n) counts the integers below n coprime to it, and Euler's theorem generalises Fermat to a^φ(n) ≡ 1 (mod n) for any coprime a, with Fermat recovered as the prime case since φ(p) = p − 1. For a semiprime n = pq, φ(n) = (p−1)(q−1) is trivial to compute if you know the factors and appears to require factoring otherwise — so exponents chosen to be inverses modulo φ(n) undo each other, and knowledge of the factorisation becomes the secret that separates the person who can invert the operation from everyone else.
9. Hardy Was WrongClose the course's argument: explain how the difficulty of factoring became a product, calibrate that difficulty against the RSA-250 record, and articulate what the story of number theory's usefulness actually shows about pure mathematics.The RSA-250 factorisation in February 2020 took roughly 2,700 core-years for a 250-digit number, against the microseconds needed to multiply its factors — the asymmetry that Hardy's useless subject turned into infrastructure four decades after he celebrated its purity. The lesson is not that pure mathematics should be defended by its eventual applications but the reverse: nobody in the chain from Euclid to Euler was aiming at anything, and a subject selected for usefulness would never have produced the tools, because the useful thing was the difficulty itself.

Questions this course answers

Grounded in trusted sources

• G. H. Hardy & E. M. Wright, An Introduction to the Theory of Numbers (6th ed., Oxford University Press, 2008)
• G. H. Hardy, A Mathematician's Apology (Cambridge University Press, 1940)
• Kenneth Rosen, Elementary Number Theory and Its Applications (6th ed., Pearson)
• Tomás Oliveira e Silva, 'Tables of values of π(x) and of π₂(x)' — π(10^k) values fetched from https://sweet.ua.pt/tos/primes.html (data file primes/1d00.txt.gz)
• Yitang Zhang, 'Bounded gaps between primes' (Annals of Mathematics 179:3, 2014) — see also https://aimath.org/news/primegaps70m/
• D. H. J. Polymath, 'The bounded gaps between primes Polymath project — a retrospective' (2014), arXiv:1409.8361; final unconditional bound H = 246 per https://en.wikipedia.org/wiki/Polymath_Project
• R. L. Rivest, A. Shamir & L. Adleman, 'A Method for Obtaining Digital Signatures and Public-Key Cryptosystems' (CACM 21:2, 1978)
• F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé & P. Zimmermann, 'Factorization of RSA-250' (28 February 2020) — https://caramba.loria.fr/rsa250.txt

Every Wunder lesson is built from real, reputable sources — never invented.

Related Math courses