Everything about integers: divisibility, primes, residues, and the arithmetic you do modulo something.
Start here
General covers divisibility, GCD/LCM and the primitives everything else builds on. If you only learn three things, learn binary exponentiation, modular arithmetic, and the sieve.
Foundations
- General — divisibility, GCD/LCM, base conversion
- Binary Exponentiation
- Modular Arithmetic
- Modular Inverse
- Linear Congruence
- Linear Diophantine Equations
- Euclidean Algorithm · Extended Euclidean
- Chinese Remainder Theorem · Garner’s Algorithm
Primes & Factorisation
- Primality Testing
- Integer Factorization
- Sieve Techniques
- Sieve of Eratosthenes
- Miller-Rabin · Pollard’s Rho
- AKS · Lucas-Lehmer
Arithmetic Functions
Residues & Groups
- Primitive Root
- Discrete Logarithm
- Discrete Root
- Quadratic Residues — Legendre symbol, reciprocity
- Tonelli-Shanks · Cipolla
- Pohlig-Hellman
Theorems & Special Numbers
- Wilson’s Theorem
- Factorial Modulo p — Lucas and generalisations
- Pell’s Equation and continued fractions
- Fibonacci Numbers
- Linear Recurrences
- Gray Code
- Balanced Ternary