Congruence Modulo Real Number is Equivalence Relation

From ProofWiki
Jump to navigation Jump to search


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


Checking in turn each of the criteria for equivalence:


We have that Equal Numbers are Congruent:

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

so it follows that:

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

and so congruence modulo $z$ is reflexive.



\(\ds x\) \(\equiv\) \(\ds y \pmod z\)
\(\ds \leadsto \ \ \) \(\ds x - y\) \(=\) \(\ds k z\)
\(\ds \leadsto \ \ \) \(\ds y - x\) \(=\) \(\ds \paren {-k} z\)
\(\ds y\) \(\equiv\) \(\ds x \pmod z\)

So congruence modulo $z$ is symmetric.



\(\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\)

So congruence modulo $z$ is transitive.


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


Also see