Number Theory: Modular Arithmetic

$a\equiv b\pmod n$ means $n\mid(a-b)$. You may add, subtract, and multiply congruences.

In plain terms. Only the remainder matters, so replace big numbers by their remainders and do easy arithmetic.

Example. $3^{100}\bmod 5$: since $3^4 = 81\equiv 1$, $3^{100} = (3^4)^{25}\equiv 1$.

If $p$ is prime and $p\nmid a$, then $a^{p-1}\equiv 1\pmod p$.

In plain terms. Raising to the power $p-1$ resets you to $1$ modulo a prime, so huge exponents shrink fast.

Example. $2^{100}\bmod 7$: $2^6\equiv 1$, and $100 = 6\cdot 16 + 4$, so $2^{100}\equiv 2^4 = 16\equiv 2$.