Congruence Modulo n

Congruence modulo n is an equivalence relation defined on the set of integers ℤ. Two elements a and b in ℤ are said to be congruent modulo n if their difference is a multiple of n: $$ a\rho b \:\: (mod \: n) \Leftrightarrow a - b = k \cdot n,\ \text{where } k \in \mathbb{Z} $$

Example

Example 1

Let a = 10 and b = 4. To say that a is congruent to b modulo n = 2 means that the difference a − b is divisible by 2:

$$ a \equiv_n b $$

$$ 10 \equiv_2 4 \Leftrightarrow 10 - 4 = 6 = 3 \cdot 2 $$

The difference a − b = 6 is a multiple of 2, so the congruence holds.

Example 2

Now let a = 7 and b = 4. We check whether 7 is congruent to 4 modulo 2:

$$ a \equiv_n b $$

$$ 7 \equiv_2 4 \Leftrightarrow 7 - 4 = 3 = k \cdot 2 $$

But there is no integer k such that \( k \cdot 2 = 3 \), so the difference is not divisible by 2.

Therefore, 7 is not congruent to 4 modulo 2, and the congruence does not hold.