Congruence Modulo Integer is Equivalence Relation

From ProofWiki
Jump to: navigation, search

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

\(\displaystyle x\) \(\equiv\) \(\displaystyle y \bmod z\) $\quad$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle x - y\) \(=\) \(\displaystyle k z\) $\quad$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle y - x\) \(=\) \(\displaystyle \paren {-k} z\) $\quad$ $\quad$
\(\displaystyle y\) \(\equiv\) \(\displaystyle x \bmod z\) $\quad$ $\quad$

So congruence modulo $z$ is symmetric.

$\Box$


Transitive

\(\displaystyle x_1\) \(\equiv\) \(\displaystyle x_2 \pmod z\) $\quad$ $\quad$
\(\, \displaystyle \land \, \) \(\displaystyle x_2\) \(\equiv\) \(\displaystyle x_3 \pmod z\) $\quad$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \paren {x_1 - x_2}\) \(=\) \(\displaystyle k_1 z\) $\quad$ $\quad$
\(\, \displaystyle \land \, \) \(\displaystyle \paren {x_2 - x_3}\) \(=\) \(\displaystyle k_2 z\) $\quad$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \paren {x_1 - x_2} + \paren {x_2 - x_3}\) \(=\) \(\displaystyle \paren {k_1 + k_2} z\) $\quad$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \paren {x_1 - x_3}\) \(=\) \(\displaystyle \paren {k_1 + k_2} z\) $\quad$ $\quad$
\(\displaystyle x_1\) \(\equiv\) \(\displaystyle x_3 \pmod z\) $\quad$ $\quad$

So congruence modulo $z$ is transitive.

$\Box$


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

$\blacksquare$


Sources