Number Theory: Primes & Modular Arithmetic
Divisibility, congruences, Euclidean algorithm, and Fermat's little theorem.
Working with $\mathbb Z$: $a \mid b$ means $b = a k$ for some integer $k$. The Euclidean algorithm computes $\gcd(a, b)$ by repeated remainders and yields, via back-substitution, integers $x, y$ with
$$ax + by = \gcd(a, b) \qquad \text{(Bézout's identity)}.$$The fundamental theorem of arithmetic: every integer $n > 1$ has a unique factorization into primes (up to ordering).
Modular arithmetic: $a \equiv b \pmod{n}$ iff $n \mid (a - b)$. The set $\mathbb Z/n\mathbb Z$ is a ring; it's a field iff $n$ is prime. Fermat's little theorem:
$$a^{p-1} \equiv 1 \pmod{p} \quad \text{when } \gcd(a, p) = 1.$$Generalizes to Euler's $a^{\varphi(n)} \equiv 1 \pmod n$ where $\varphi$ is Euler's totient. This is the basis of RSA public-key cryptography: choose $n = pq$, public exponent $e$, private $d$ with $ed \equiv 1 \pmod{\varphi(n)}$; encryption is $c = m^e \mod n$, decryption $m = c^d \mod n$.
Interactive: Euclidean algorithm
The algorithm reduces $\gcd(a, b)$ to $\gcd(b, a \bmod b)$ until the second argument is zero.