Number Theory
Discrete and Data
The integers from the ground up: divisibility, primes, gcd and the Euclidean algorithm, modular arithmetic, bases, Diophantine equations, Fermat and Euler, arithmetic functions, the Chinese remainder theorem, and orders.
Start here
Who Divides Whom
Unit 1 · Divisibility
0 of 11 units complete
- 1Unit 1Divisibility5 parts · about 11 min
Who Divides Whom
Every division leaves a quotient and a remainder, even for negative numbers. Combine divisibility facts like a detective, colour the hundred chart by remainders, and find out why the digit tricks for 3, 9 and 11 work.
- 2Unit 2Primes and Factorization5 parts · about 12 min
Primes
Sieve the primes out of the first hundred numbers by hand, factor anything uniquely, prove there are infinitely many primes the way Euclid did, and count the zeros at the end of 100! without computing it.
- 3Unit 3GCD, LCM and the Euclidean Algorithm5 parts · about 12 min
The Euclidean Algorithm
The oldest algorithm still in daily use: cut squares off a rectangle until it tiles perfectly. Find greatest common divisors fast, write them as combinations (Bézout), and measure exactly 4 litres with a 3-litre and a 5-litre jug.
- 4Unit 4Modular Arithmetic5 parts · about 11 min
Clock Arithmetic
Arithmetic where numbers wrap around like hours on a clock. Find days of the week centuries ahead, last digits of giant powers, prove that some numbers are never sums of two squares, and divide when you are only allowed to multiply.
- 5Unit 5Digits and Bases5 parts · about 12 min
Other Bases
Ten is just the number of fingers we happen to have. Count in binary like a computer, read hexadecimal colours, see why "divisible by 9" becomes "divisible by b − 1" in any base, and crack digit-reversal puzzles.
- 6Unit 6Diophantine Equations5 parts · about 12 min
Whole-Number Equations
Equations where only whole-number answers count. Find every integer point on a line, buy exactly 43 chicken nuggets (or not), factor your way to solutions, and use remainders to prove there are none at all.
- 7Unit 7Fermat, Euler and Wilson5 parts · about 12 min
Fermat, Euler and Wilson
Raise any number to the power p − 1 and, mod p, you always get 1. Watch powers cycle on a clock, compute last digits of towering powers, meet Euler's φ, and see how all of this keeps your online shopping secret.
- 8Unit 8Arithmetic Functions5 parts · about 11 min
Counting Divisors
How many divisors does a number have, and what do they add up to? Arrange dots into rectangles, hunt for perfect numbers, solve the 100 lockers puzzle, and discover why these functions multiply so nicely.
- 9Unit 9The Chinese Remainder Theorem5 parts · about 12 min
The Chinese Remainder Theorem
Know a number's remainders mod 3 and mod 5 and you know it mod 15. Walk diagonally around a torus to see why, count soldiers like a 4th-century general, and find out what goes wrong when the moduli share a factor.
- 10Unit 10Orders and Primitive Roots5 parts · about 13 min
Orders and Primitive Roots
How long until a power comes back to 1? Find numbers whose powers visit everything, see why 1/7 repeats every six digits, and sort numbers mod p into squares and non-squares.
- 11Unit 11Hard Number Theory5 parts · about 13 min
Hard Number Theory
Olympiad problems need a plan: try small cases, pick the right modulus, factor, bound. Practise each move on real competition-style problems, then count lattice points to evaluate a floor sum with one picture.