# Congruence Modulo Integer is Equivalence Relation

## Theorem

For all $z \in \Z$, congruence modulo $z$ is an equivalence relation.

## Proof

Checking in turn each of the critera for equivalence:

### Reflexive

We have that Equal Numbers are Congruent:

$\forall x, y, z \in \Z: x = y \implies x \equiv y \pmod z$

so it follows that:

$\forall x \in \Z: x \equiv x \pmod z$

and so congruence modulo $z$ is reflexive.

$\Box$

### Symmetric

 $\ds x$ $\equiv$ $\ds y \bmod z$ $\ds \leadsto \ \$ $\ds x - y$ $=$ $\ds k z$ $\ds \leadsto \ \$ $\ds y - x$ $=$ $\ds \paren {-k} z$ $\ds y$ $\equiv$ $\ds x \bmod z$

$\Box$

### Transitive

 $\ds x_1$ $\equiv$ $\ds x_2 \pmod z$ $\, \ds \land \,$ $\ds x_2$ $\equiv$ $\ds x_3 \pmod z$ $\ds \leadsto \ \$ $\ds \paren {x_1 - x_2}$ $=$ $\ds k_1 z$ $\, \ds \land \,$ $\ds \paren {x_2 - x_3}$ $=$ $\ds k_2 z$ $\ds \leadsto \ \$ $\ds \paren {x_1 - x_2} + \paren {x_2 - x_3}$ $=$ $\ds \paren {k_1 + k_2} z$ $\ds \leadsto \ \$ $\ds \paren {x_1 - x_3}$ $=$ $\ds \paren {k_1 + k_2} z$ $\ds x_1$ $\equiv$ $\ds x_3 \pmod z$

$\Box$

So we are justified in supposing that congruence, as we have defined it, is an equivalence.

$\blacksquare$