Number theory

Number theory starts from divisibility. We write m | a when a = m q for some integer q. The relation a ≡ b (mod m) means m | (a − b). It splits the integers into m residue classes, and both addition and multiplication descend to those classes. That is modular arithmetic: clocks are arithmetic modulo 12, and bit operations often live modulo 2.

Euclid’s lemma says that if a prime p divides ab, then p divides a or p divides b. Combined with existence of factorizations, it yields uniqueness: the fundamental theorem, already used in arithmetic, is really this lemma. The same circle of ideas produces the fact that there are infinitely many primes. Euclid’s proof still works: if p₁, …, pₖ were all of them, then N = p₁⋯pₖ + 1 would be divisible by none of them, so it would have a new prime factor.

Fermat’s little theorem: if p is prime and p does not divide a, then a^{p−1} ≡ 1 (mod p). Equivalently aᵖ ≡ a (mod p) for every integer a. The generalization is Euler’s theorem, a^{φ(n)} ≡ 1 (mod n) when a and n are coprime, where φ(n) counts integers from 1 to n that are coprime to n. These are the arithmetic engine inside the RSA cryptosystem, which is number theory that happens to encrypt.