Congruence (Number Theory) is an Equivalence

From ProofWiki

Jump to: navigation, search

Theorem

Checking in turn each of the critera for equivalence:

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

so it follows that:

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

$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle x_1$	$\equiv$	$\displaystyle x_2 \bmod z$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle \land$	$\displaystyle $	$\displaystyle x_2$	$\equiv$	$\displaystyle x_3 \bmod z$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle \implies$	$\displaystyle $	$\displaystyle \left({x_1 - x_2}\right)$	$=$	$\displaystyle k_1 z$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle \land$	$\displaystyle $	$\displaystyle \left({x_2 - x_3}\right)$	$=$	$\displaystyle k_2 z$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle \implies$	$\displaystyle $	$\displaystyle \left({x_1 - x_2}\right) + \left({x_2 - x_3}\right)$	$=$	$\displaystyle \left({k_1 + k_2}\right) z$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle \implies$	$\displaystyle $	$\displaystyle \left({x_1 - x_3}\right)$	$=$	$\displaystyle \left({k_1 + k_2}\right) z$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle x_1$	$\equiv$	$\displaystyle x_3 \bmod z$	$\displaystyle $	$\displaystyle $	$\displaystyle $

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

$\blacksquare$

\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle x_1\)	\(\equiv\)	\(\displaystyle x_2 \bmod z\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \land\)	\(\displaystyle \)	\(\displaystyle x_2\)	\(\equiv\)	\(\displaystyle x_3 \bmod z\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \left({x_1 - x_2}\right)\)	\(=\)	\(\displaystyle k_1 z\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \land\)	\(\displaystyle \)	\(\displaystyle \left({x_2 - x_3}\right)\)	\(=\)	\(\displaystyle k_2 z\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \left({x_1 - x_2}\right) + \left({x_2 - x_3}\right)\)	\(=\)	\(\displaystyle \left({k_1 + k_2}\right) z\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \left({x_1 - x_3}\right)\)	\(=\)	\(\displaystyle \left({k_1 + k_2}\right) z\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle x_1\)	\(\equiv\)	\(\displaystyle x_3 \bmod z\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)