Congruence (Number Theory) is Congruence Relation

Theorem

Congruence modulo $m$ is a congruence relation on $\struct {\Z, +}$.

Proof

Suppose $a \equiv b \bmod m$ and $c \equiv d \bmod m$.

Then by the definition of congruence there exists $k, k' \in \Z$ such that:

$\paren {a - b} = k m$

$\paren {c - d} = k' m$

Hence:

$\paren {a - b} + \paren {c - d} = k m + k' m$

Using the properties of the integers:

$\paren {a + c} - \paren {b + d} = m \paren {k + k'}$

Hence $\paren {a + c} \equiv \paren {b + d} \bmod m$ and congruence modulo $m$ is a congruence relation.

$\blacksquare$

Sources

• 1974: Thomas W. Hungerford: Algebra ... (previous) ... (next): $\text{I}$: Groups: $\S 1$: Semigroups, Monoids and Groups