Modular arithmetic

Two integers are congruent modulo $n$, written a mod n, when they leave the same remainder upon division by $n$. Congruences behave like equations: you may add, subtract, and multiply both sides by the same integer, and replace any number by its remainder modulo $n$ at any time. For a prime $p$, Fermat's little theorem states a^{p-1} mod p = 1 whenever $p$ does not divide $a$. To solve ax mod n = b, multiply both sides by the inverse of $a$ modulo $n$, the number $a^{-1}$ satisfying a imes a^{-1} mod n = 1.