Modular Arithmetic

Two integers are congruent modulo $m$, written $a \equiv b \pmod m$, if they leave the same remainder when divided by $m$ (equivalently, $m \mid (a-b)$). This relation is reflexive, symmetric, and transitive — it behaves like equality, which is what makes it so useful.

What you can and can’t do

Addition, subtraction, and multiplication are all safe under a fixed modulus: if $a \equiv b$and $c \equiv d \pmod m$, then $a+c \equiv b+d$, $a-c \equiv b-d$, and$ac \equiv bd \pmod m$, all still modulo $m$. Division is the exception —$a$ has a modular inverse mod $m$ (an element $a^{-1}$ with$a \cdot a^{-1} \equiv 1 \pmod m$) if and only if $\gcd(a,m)=1$.

Reducing large powers

For computing $a^n \bmod m$ with a huge exponent, look for the point where the powers of$a$ start repeating (the multiplicative cycle). Once you know the cycle length, reduce the exponent modulo that length before computing.

Practice problems