## Congruences

The division algorithm guarantees that if we divide some integer $a$ by another, say $m$, there are unique integers $q$ and $r$ such that $$a = qm+r \quad \quad \text{with} \quad \quad 0 \le r \lt m$$
Recall, we referred to the unique $r$ above as the remainder resulting from the division of $a$ by $m$.

Let us now define $a \equiv b \pmod{m}$, read "*a* is congruent to *b* modulo *m*", to mean that $a$ and $b$ have the same remainder upon division by $m$.

Equivalently, $a \equiv b \pmod{m}$ then means that $m \mid b - a$.

As yet a third option for its definition, note that $a \equiv b \pmod{m}$ if and only if there exists some integer $k$ such that $a = b + mk$.

Also, let us refer to the smallest, non-negative integer congruent to *a* modulo *m* to be the **residue of ***a* modulo *m*, denoted either by $a$ MOD $b$, or alternatively $a\,\%\,b$. (*The latter notation is often found in computer science.*)