Congruence Modulo

Two positive integers $a$ and $b$ are said to be congruent modulo $m$ if they leave the same remainder when divided by $m$. Formally, $a$ and $b$ are congruent modulo $m$ when either of two equivalent conditions holds: the difference $(a - b)$ is exactly divisible by $m$, or $a \bmod m = b \bmod m$. This relationship is written using the congruence notation $a \equiv b \pmod{m}$, and it is a natural extension of the modulo operator you've just seen — instead of asking for the remainder of a single number, congruence modulo asks whether two different numbers land on the same remainder when both are divided by $m$.

Raising a congruence to a power

Congruences behave well under exponentiation, which is captured by Property 5:

This turns otherwise-heavy power calculations into one-line arguments. To find $5^6 \pmod 4$, note that $5 \equiv 1 \pmod 4$; raising both sides to the sixth power gives $5^6 \equiv 1^6 = 1 \pmod 4$.

Congruence as an equivalence relation

Fix a modulus $m$ and relate two integers whenever they are congruent modulo $m$. This relation is an equivalence relation, because it satisfies all three required properties:

• Reflexive: $m \mid (a - a) = 0$, so $a \equiv a \pmod m$ for every integer $a$.
• Symmetric: if $m \mid (a - b)$, then $m$ also divides $-(a - b) = (b - a)$, so $a \equiv b \pmod m$ forces $b \equiv a \pmod m$.
• Transitive: if $a \equiv b \pmod m$ and $b \equiv c \pmod m$, then $a - b$ and $b - c$ are both multiples of $m$, hence so is their sum $a - c$, giving $a \equiv c \pmod m$.

Equivalence classes

Because congruence modulo $m$ is an equivalence relation, it partitions the integers into disjoint groups. The equivalence class of an integer $X$ collects every integer that leaves the same remainder as $X$:

For $m = 3$, for instance, $[0] = \{0, \pm 3, \pm 6, \ldots\}$, $[1] = \{\ldots, -2, 1, 4, 7, \ldots\}$ and $[2] = \{\ldots, -1, 2, 5, 8, \ldots\}$; these classes never overlap and together cover all the integers. In general there are exactly $m$ equivalence classes modulo $m$, namely $[0], [1], [2], \ldots, [m-1]$ - one for each possible remainder.

Illustration 6. Take the two positive integers $262$ and $137$ and divide each by $5$:

Both leave the same remainder, 2. Subtracting (ii) from (i):

and $125 = 5 \times 25$ is a multiple of $5$.

Generalising: suppose $a$ and $b$ are two positive integers that leave the same remainder $r$ when divided by a positive integer $m$:

Subtracting (iv) from (iii) gives $a - b = m(s - t)$, so $m$ divides $a - b$, written $m \mid (a - b)$. Equivalently $a \bmod m = b \bmod m$, which we record with the congruence notation

read as "$a$ is congruent to $b$ modulo $m$." For our numbers, $262 \equiv 137 \pmod 5$.

---

Illustration 7. Complete Table 6 to verify Property 5: if $a \equiv b \pmod{m}$, then $a^{k} \equiv b^{k} \pmod{m}$ for every positive integer $k$.

Each row confirms the property: whenever $a$ and $b$ share the same remainder modulo $m$, their $k$-th powers also share the same remainder. (For the last row, even though $17$ and $32$ look unrelated, $17 \bmod 5 = 2$ and $32 \bmod 5 = 2$, so $17 \equiv 32 \pmod 5$ and the property applies.)

---

Activity — sorting the first 50 integers by their remainder $\bmod\ 6$. …