# Number Theory
Based on Jim Hefferon's Elementary Number Theory, licensed GFDL + CC BY-SA 2.5.
From divisibility to continued fractions. Each chapter builds one layer of the integers' hidden structure, with runnable code and diagrams.
| Chapter | |||
|---|---|---|---|
| 1. | Divisibility | The divides relation, division algorithm, GCD, and the Euclidean algorithm | # |
| 2. | Primes | Fundamental theorem of arithmetic, infinitude of primes, sieve of Eratosthenes | # |
| 3. | Congruences | Modular arithmetic, congruence classes, and solving linear congruences | # |
| 4. | Euler and Fermat | Euler's totient, Fermat's little theorem, and fast modular exponentiation | # |
| 5. | Chinese Remainder Theorem | Solving systems of congruences with a constructive algorithm | # |
| 6. | Quadratic Residues | Squares mod p, the Legendre symbol, and quadratic reciprocity | # |
| 7. | Primitive Roots | Generators of cyclic groups and the discrete logarithm problem | # |
| 8. | Continued Fractions | Best rational approximations, periodic expansions, and Pell's equation | # |
📺 Video lectures: MIT 18.781 Theory of Numbers
Neighbors
- 🔗 Abstract Algebra — modular arithmetic is integers mod n, a ring
- 🔐 Cryptography — RSA is Euler's theorem applied
- 🔢 Discrete Math — divisibility and primes are discrete-math territory
- ⚙ Algorithms — primality testing and GCD algorithms