Congruence Modulo Integer is Equivalence Relation

From ProofWiki
Jump to navigation Jump to search


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


Checking in turn each of the critera for equivalence:


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.



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

So congruence modulo $z$ is symmetric.



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

So congruence modulo $z$ is transitive.


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