| | |
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.)