Congruence by Divisor of Modulus

Theorem

Let $z \in \R$ be a real number.

Let $a, b \in \R$ such that $a$ is congruent modulo $z$ to $b$, that is:

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

Let $m \in \R$ such that $z$ is an integral multiple of $m$:

$\exists k \in \Z: z = k m$.

(When $z$ is an integer, this can be expressed $m \backslash z$, i.e. $m$ divides $z$.)

Then $a \equiv b \ \left({\bmod\, m}\right)$.

Proof

We are given that $\exists k \in \Z: z = k m$.

Thus:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a\)	\(\equiv\)	\(\displaystyle b\)	\(\displaystyle \)	\(\displaystyle \pmod z\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \exists k' \in \Z: a\)	\(=\)	\(\displaystyle b + k' z\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of congruence
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle a\)	\(=\)	\(\displaystyle b + k' k m\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a\)	\(\equiv\)	\(\displaystyle b\)	\(\displaystyle \)	\(\displaystyle \pmod m\)	\(\displaystyle \)	Definition of congruence: $k' k$ is an integer

$\blacksquare$