Number theory

Divisibility and modular arithmetic

Euclid's algorithm finds $\gcd(a,b)$ by repeated division, and running it backwards writes the gcd as $ax+by$ (Bézout). In modular arithmetic we work with remainders: $a\equiv b\pmod n$ means $n\mid a-b$. Fermat: for prime $p\nmid a$, $a^{p-1}\equiv1\pmod p$.