Curriculum · Number Theory
Number Theory
Divisibility, congruences, and Diophantine equations — the oldest playground in mathematics and the sharpest section of every contest.
Divisibility & Primes
Divisibility & Prime Factorization
The fundamental theorem of arithmetic and everything it buys: divisor counts, gcd, lcm.
- Factor and count divisors
- Compute gcd and lcm structurally
- Use p-adic (exponent) thinking
GCD, LCM & the Euclidean Algorithm
The Euclidean algorithm, Bezout's identity, and gcd·lcm = product.
- Run the Euclidean algorithm
- Apply gcd·lcm = ab
- Use Bezout for existence arguments
prerequisite: divisibility-primes
Number Bases & Digits
Base-b representation, digit sums, and divisibility rules that fall out of them.
- Convert between bases
- Prove divisibility rules
- Solve digit puzzles
prerequisite: divisibility-primes
Congruences
Modular Arithmetic
Clock arithmetic made rigorous: congruences, cycles of powers, and the remainder questions contests love.
- Compute with congruences fluently
- Find cycles in powers mod n
- Solve linear congruences
prerequisite: divisibility-primes
Diophantine Equations
Integer-solution hunting: factoring tricks, bounding, and Simon's Favorite Factoring Trick.
- Factor to force integer constraints
- Bound solutions before searching
- Apply SFFT
prerequisite: modular-arithmetic
Euler's Theorem & CRT
The totient function, Euler's theorem, Fermat's little theorem, and the Chinese Remainder Theorem.
- Compute φ(n)
- Reduce huge exponents with Euler
- Solve simultaneous congruences with CRT
prerequisite: modular-arithmetic