Curriculum
Every masterclass starts with Unit 1 and runs in order. The Foundation masterclass ends after Unit 8, the Advanced masterclass after Unit 12, and Advanced + Analytic Number Theory takes all 16.
The Integers
Proof, Induction, and the Integers
What a proof is, how induction works, and the toolkit every later unit uses
About this unitThe unit opens with an homage to number theory and then builds the toolkit of the whole program: the notation for the integers, sums, floors, and binomial coefficients; what a proof and a counterexample are, shown by Euler's factor of the fifth Fermat number; direct proof, contrapositive, and contradiction, with the irrationality of the square root of 2; induction in its weak and strong forms and the well-ordering principle; the pigeonhole principle; and the digit count of the largest known prime as a first lesson in how fast numbers grow.
- Proof and counterexample
- Induction
- Well-ordering
- Pigeonhole principle
- Growth and digit counts
Divisibility and the Euclidean Algorithm
Division with remainder, the greatest common divisor, and the oldest algorithm still in use
About this unitDivision with remainder is the first theorem of number theory, and this unit shows how much follows from it: positional notation in any base, Euclid's algorithm for the greatest common divisor with Lamé's bound on its running time, Bézout's identity and the extended algorithm that finds its coefficients, and the complete solution of the linear Diophantine equation ax + by = c. The same algorithm computes the inverses that every public-key cryptosystem needs.
- Divisibility
- Division with remainder
- Euclid's algorithm
- Bézout's identity
- Linear Diophantine equations
Prime Numbers and Unique Factorization
Why every integer factors into primes in exactly one way, and why the primes never end
Free sample unitRead the full unit online or as PDFEvery integer greater than 1 is a product of primes in exactly one way, and this unit proves it, from the smallest divisor of a number to Euclid's lemma. It shows how the sieve of Eratosthenes finds every prime below a bound, why Euclid's argument gives endlessly many primes without a formula for them, how the exponents of a factorization answer questions about divisors, square roots, and factorials, and why recognizing a prime is a far easier task than factoring a number.
- Primes and composites
- Fundamental theorem of arithmetic
- Euclid's theorem
- Sieve of Eratosthenes
- Legendre's formula
- Primality testing
Congruences and Modular Arithmetic
Arithmetic on a clock: residues, inverses, linear congruences, and the Chinese remainder theorem
About this unitGauss's congruence notation turns questions about divisibility into arithmetic with finitely many residues. This unit builds that arithmetic, shows when a factor may be cancelled and which residues have an inverse, solves linear congruences and systems of them with the Chinese remainder theorem, computes large powers by repeated squaring, and explains the divisibility tests and the check digits of book numbers and bank accounts.
- Congruences and residue classes
- Cancellation and inverses
- Linear congruences
- Chinese remainder theorem
- Repeated squaring
- Divisibility tests and check digits
The Theorems of Fermat, Euler, and Wilson
Three classical theorems about powers modulo a prime, and the cryptography built on them
About this unitFermat's little theorem with two proofs, Euler's totient function and Euler's theorem, the multiplicative order, and Wilson's theorem, which characterizes the primes by one congruence. The theorems are then put to work: the Fermat test and its refinement by Miller and Rabin tell composites from primes without factoring, and the RSA cryptosystem turns Euler's theorem into the lock behind the certificates of most secure connections on the internet.
- Fermat's little theorem
- Euler's totient function
- Multiplicative order
- Wilson's theorem
- Pseudoprimes and Carmichael numbers
- RSA
Arithmetic Functions and Perfect Numbers
Counting and adding divisors, multiplicative functions, Möbius inversion, and the perfect numbers
About this unitThe number of divisors of an integer, their sum, and Euler's totient can all be read off the factorization, because each of them is multiplicative. This unit proves that divisor sums preserve multiplicativity, introduces the Möbius function and the inversion formula that undoes a divisor sum, shows that the integers up to N have about ln N divisors on average, and proves the Euclid-Euler theorem that ties the even perfect numbers to the Mersenne primes. It ends with amicable numbers, aliquot sequences, and two questions open since antiquity.
- Divisor functions
- Multiplicative functions
- Möbius inversion
- Average number of divisors
- Perfect numbers
- Mersenne primes
Diophantine Equations
Whole-number solutions of equations: Pythagorean triples, descent, and Pell's equation
About this unitAn equation becomes Diophantine when its solutions must be integers, and then even a simple one can take centuries to settle. This unit teaches the three classical methods: the parametrization of all solutions, shown on the Pythagorean triples and the rational points of the circle; Fermat's method of descent, with the full proof that x to the 4 plus y to the 4 equals z squared has no solution; and congruence obstructions such as the one that rules out y squared equals x cubed plus 7. It ends with Pell's equation, whose infinitely many solutions all grow out of the smallest one, and with a first look at the curves of degree three that current research is about.
- Pythagorean triples
- Rational points on the circle
- Method of descent
- Congruence obstructions
- Pell's equation
- Curves of degree three
The Great Problems of Number Theory
Goldbach, twin primes, the Riemann hypothesis, and Fermat's Last Theorem: what is known and what is open
About this unitThe closing unit of the Foundation masterclass presents the statements that nobody has proved and the one that was proved in 1995 after 358 years. It explains why a verification to four billion billion cases settles nothing, states Goldbach's conjecture, the twin prime conjecture, the prime number theorem, and the Riemann hypothesis in a form that needs no complex numbers, proves Euler's product formula and the divergence of the sum of the reciprocals of the primes from unique factorization, and tells the story of Fermat's Last Theorem from the margin note to Wiles. It ends with Landau's problems, the Collatz problem, number theory in daily use, and the roads that lead on from here.
- Goldbach's conjecture
- Twin primes and bounded gaps
- Prime number theorem
- Euler product
- Riemann hypothesis
- Fermat's Last Theorem
Residues, Squares, and Primes
Primitive Roots and the Structure of Residues
The multiplicative group modulo n, its generators, indices, and the Diffie-Hellman key exchange
About this unitModulo every prime there is a residue whose powers run through all the others, and this unit proves it by counting the residues of each order, after Lagrange's theorem on polynomial congruences has limited how many roots a congruence can have. It works out which moduli have such a primitive root, turns multiplication into addition with Gauss's indices, explains why the digits of 1/7 repeat every six places, and ends with the Diffie-Hellman key exchange, the discrete logarithm problem behind it, and the attack of 2015 that broke it for shared 512-bit primes.
- Multiplicative order
- Cyclic groups
- Primitive roots
- Indices
- Decimal periods
- Diffie-Hellman
Quadratic Residues and Quadratic Reciprocity
Which numbers are squares modulo a prime, and Gauss's law that answers it
About this unitHalf of the non-zero residues modulo an odd prime are squares, and this unit shows how to tell which half. Euler's criterion decides it with one exponentiation, the two supplements settle the cases of minus 1 and 2, and the law of quadratic reciprocity ties the question for p and q together, with a complete proof by Eisenstein's count of lattice points. The Jacobi symbol turns the law into an algorithm that needs no factoring, and the closing section looks at the random-looking sequence of Legendre symbols, the Pólya-Vinogradov inequality, and the least non-residue.
- Quadratic residues
- Legendre symbol
- Euler's criterion
- Gauss's lemma
- Quadratic reciprocity
- Jacobi symbol
Sums of Squares and Quadratic Forms
Fermat's two squares, Lagrange's four squares, and the binary quadratic forms behind them
About this unitWhich integers are sums of two squares, of three, of four? This unit proves Fermat's theorem that every prime of the form 4k + 1 is a sum of two squares, finds the two squares with Euclid's algorithm, counts the representations with Jacobi's formula, and proves Lagrange's four-square theorem by descent. It then introduces the binary quadratic forms behind these results, reduces them, counts their classes, and shows how the two classes of discriminant minus 20 explain the two factorizations of 6, before the lattice picture leads to Gauss's circle problem and to the sphere packing in eight dimensions.
- Two-square theorem
- Four-square theorem
- Three squares
- Binary quadratic forms
- Class numbers
- Gauss's circle problem
The Distribution of the Primes
How the primes thin out: Chebyshev's bounds, Bertrand's postulate, Mertens' theorems, and the prime number theorem
About this unitThis unit measures how the primes thin out. It compares the counts of primes up to ten billion with the guesses of Gauss and Legendre, defines the O notation, and proves with one binomial coefficient and Legendre's formula that pi(x) lies between two fixed multiples of x/ln x and that a prime always lies between n and 2n. It introduces the Chebyshev functions, proves the first of Mertens' theorems on sums over primes, shows what a random model of the primes predicts and where arithmetic corrects it, and ends with two races: the primes 4k + 3 against the primes 4k + 1, and pi(x) against li(x), where the leader changes only beyond 10^316.
- Prime number theorem
- Chebyshev's bounds
- Bertrand's postulate
- Mertens' theorems
- Cramér's random model
- Prime races
Analytic Number Theory
The Riemann Zeta Function
Complex numbers, the zeta function and its continuation, its zeros, and the Riemann hypothesis
About this unitThe first unit of the analytic masterclass builds the complex numbers from scratch and follows Riemann's paper of 1859: the zeta function and its Euler product for complex s, the continuation past s = 1 by partial summation and the pole there, the functional equation with the trivial zeros and the values at 0 and at minus 1, the critical strip and the first zeros on the critical line, and the Riemann hypothesis. The explicit formula then writes the staircase of the prime powers as the line x minus one wave for every pair of zeros, the prime number theorem becomes the statement that no zero lies on the line of real part 1, and the unit ends with what is known: the proportion of zeros proved to lie on the critical line, the twelve trillion zeros verified by computer, the pair correlation of Montgomery and Dyson, and Robin's criterion.
- Complex numbers
- Zeta function
- Analytic continuation
- Critical strip
- Explicit formula
- Riemann hypothesis
Primes in Arithmetic Progressions
Dirichlet's theorem, with the characters and L-functions that prove it, and the progressions inside the primes
About this unitEuclid's trick proves that infinitely many primes end in 1 or 9 but cannot reach the primes ending in 3 or 7. Dirichlet's theorem of 1837 reaches every admissible progression, and this unit proves it in full: the characters of the residues modulo q and their orthogonality, the L-functions with their Euler products, and the key fact that no L-function vanishes at s = 1. The closing sections look at how evenly the primes are shared among the residue classes, at Chebyshev's bias, at Dirichlet's class number formula, and at the Green-Tao theorem on arithmetic progressions made of primes.
- Dirichlet's theorem
- Dirichlet characters
- L-functions
- Chebyshev's bias
- Class number formula
- Green-Tao theorem
Sieve Methods
From Eratosthenes to Brun, Selberg, and Chen: counting what has no small prime factor
About this unitA sieve counts the members of a set that have no small prime factor, and the twentieth century turned the sieve of Eratosthenes into one of the two great tools for questions about primes. This unit derives Legendre's exact formula and shows why it is useless, follows Brun to his theorem that the reciprocals of the twin primes have a finite sum, derives Selberg's optimal weights and the bounds they give, states the Bombieri-Vinogradov theorem that feeds every modern sieve, and explains the parity problem, the barrier at which Chen's theorem stops and which Friedlander and Iwaniec crossed in 1998.
- Sieve of Eratosthenes
- Brun's sieve
- Selberg's sieve
- Bombieri-Vinogradov theorem
- Parity problem
- Chen's theorem
Gaps Between Primes
Small gaps and large gaps, from the average ln p to the bounded gaps of Zhang and Maynard
About this unitThe closing unit of the masterclass studies the distances between consecutive primes. It derives their average ln p from the prime number theorem, reads the tables of record gaps against Cramér's conjecture, builds long runs of composite numbers and explains why they stay below the average, and states the theorems of Westzynthius, Rankin, and the two proofs of 2014 on large gaps. It then explains the method of Goldston, Pintz, and Yıldırım, admissible tuples, and the level of distribution, and tells how Zhang's 70 million became Maynard's 600 and the Polymath bound 246 within a year, and why the twin prime conjecture is still out of reach.
- Prime gaps
- Large gaps
- GPY method
- Bounded gaps
- Cramér's conjecture