What does $c \equiv a \mod N$ mean, and what are equivalence classes mod N?

$c \equiv a \mod N$ means that when you divide c by N, the remainder is a. The mod N operation partitions all integers into N equivalence classes.

* The integers split into 5 residue classes mod 5 — every integer lands in exactly one, giving the finite set ℤ₅ = {0,1,2,3,4}. *

Definition: $c \equiv a \mod N$ iff $N$ divides $(c - a)$, i.e., $c = a + k \cdot N$ for some integer $k$.

Properties:

• The result is always in $\{0, 1, 2, ..., N-1\}$
• Equivalently: $c \mod N = (a + k \cdot N) \mod N$ for any integer $k$

Equivalence classes mod 5:

• $[0] = \{..., -10, -5, 0, 5, 10, 15, ...\}$
• $[1] = \{..., -9, -4, 1, 6, 11, 16, ...\}$
• $[2] = \{..., -8, -3, 2, 7, 12, 17, ...\}$

The set of equivalence classes mod N is written as $\mathbb{Z}_N = \{0, 1, 2, ..., N-1\}$.

Handling negative numbers: Add multiples of N until positive, then reduce. Example: $-55 \mod 9 = (-55 + 7 \times 9) \mod 9 = 8 \mod 9 = 8$

Go deeper:

• Modular arithmetic (Wikipedia) — congruence, residue classes and ℤ_N in one place.