Congruence by Product of Modulo

From ProofWiki

Jump to: navigation, search

Theorem

Let $a, b, z \in \R$.

Let $a \equiv b \left({\bmod\, z}\right)$ denote that $a$ is congruent to $b$ modulo $z$.

Then $\forall y \in \R, y \ne 0$:

$a \equiv b \left({\bmod\, z}\right) \iff y a \equiv y b \left({\bmod\, y z}\right)$

Let $y \in \R: y \ne 0$.

Then:

$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle a$	$\equiv$	$\displaystyle b$	$\displaystyle $	$\displaystyle \pmod z$	$\displaystyle $
$\displaystyle $	$\displaystyle \iff$	$\displaystyle $	$\displaystyle a \, \bmod \, z$	$=$	$\displaystyle b \, \bmod \, z$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Definition of congruence by Modulo operation
$\displaystyle $	$\displaystyle \iff$	$\displaystyle $	$\displaystyle y \left({a \,\bmod\, z}\right)$	$=$	$\displaystyle y \left({b \,\bmod\, z}\right)$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Left hand implication valid only when $y \ne 0$
$\displaystyle $	$\displaystyle \iff$	$\displaystyle $	$\displaystyle \left({y a}\right) \bmod\, \left({y z}\right)$	$=$	$\displaystyle \left({y b}\right) \bmod\, \left({y z}\right)$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Product Distributes over Modulo Operation
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle y a$	$\equiv$	$\displaystyle y b$	$\displaystyle $	$\displaystyle \pmod {y z}$	$\displaystyle $	Definition of congruence by Modulo operation

$\blacksquare$

Note the invalidity of the third step when $y = 0$.

\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a\)	\(\equiv\)	\(\displaystyle b\)	\(\displaystyle \)	\(\displaystyle \pmod z\)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \iff\)	\(\displaystyle \)	\(\displaystyle a \, \bmod \, z\)	\(=\)	\(\displaystyle b \, \bmod \, z\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of congruence by Modulo operation
\(\displaystyle \)	\(\displaystyle \iff\)	\(\displaystyle \)	\(\displaystyle y \left({a \,\bmod\, z}\right)\)	\(=\)	\(\displaystyle y \left({b \,\bmod\, z}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Left hand implication valid only when $y \ne 0$
\(\displaystyle \)	\(\displaystyle \iff\)	\(\displaystyle \)	\(\displaystyle \left({y a}\right) \bmod\, \left({y z}\right)\)	\(=\)	\(\displaystyle \left({y b}\right) \bmod\, \left({y z}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Product Distributes over Modulo Operation
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle y a\)	\(\equiv\)	\(\displaystyle y b\)	\(\displaystyle \)	\(\displaystyle \pmod {y z}\)	\(\displaystyle \)	Definition of congruence by Modulo operation