Modular arithmetic
If only the remainder matters, which parts of ordinary arithmetic still work, and what can that buy you?
Where you are 7 inside
What this area is about
Fix a positive integer modulus n. Two integers are congruent, a \equiv b \pmod{n}, when n \mid (a - b): they leave the same remainder on division by n. Congruence behaves like equality under addition, subtraction and multiplication, so large numbers can be swapped for small ones mid-calculation. Division is the exception, and much of this area is about when it can be repaired.
How these fit together
The language. Congruence modulo n and its arithmetic defines congruence and proves the rules for +, - and \times.
Procedures. Divisibility tests from congruences reads remainders off the decimal digits. Powers modulo n finds a^k \bmod n by reducing after each step and by repeated squaring. Modular inverses, for n \ge 2, finds a b with ab \equiv 1 \pmod{n}, which exists exactly when \gcd(a, n) = 1, and solves ax \equiv c \pmod{n}.
Results. Fermat’s little theorem: for a prime p with p \nmid a, a^{p-1} \equiv 1 \pmod{p}. The Chinese remainder theorem: for pairwise coprime moduli, every choice of remainders is met by a number, unique modulo the product of the moduli.
An application. RSA public-key encryption combines powers, Fermat and inverses.
A path through it
Congruence notation first: the divisibility tests, powers and inverses all need it. Powers come before Fermat’s little theorem. Inverses also need the extended Euclidean algorithm, and come before the Chinese remainder theorem. RSA comes last, after both Fermat and inverses.
Congruence also leads to equivalence classes, where \mathbb{Z}_n is built.