Product Distributes over Modulo Operation

From ProofWiki

Jump to: navigation, search

Theorem

Let $x, y, z \in \R$ be real numbers.

Let $x \,\bmod\, y$ denote the modulo operation.

Then:

$z \left({x \,\bmod\, y}\right) = \left({z x}\right) \bmod\, \left({z y}\right)$

Let $x \,\bmod\, y$.

From the definition of the modulo operation, we have:

$x \, \bmod \, y := \begin{cases} x - y \left \lfloor {\dfrac x y}\right \rfloor & : y \ne 0 \\ x & : y = 0 \end{cases}$

If $y = 0$ we have immediately that:

$z \left({x \,\bmod\, 0}\right) = z x = \left({z x}\right) \,\bmod\, \left({z 0}\right)$

If $y \ne 0$ we have that:

$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle z \left({x \,\bmod\, y}\right)$	$=$	$\displaystyle z x - z y \left \lfloor {\frac x y}\right \rfloor$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$=$	$\displaystyle z x - z y \left \lfloor {\frac {z x} {z y} }\right \rfloor$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$=$	$\displaystyle \left({z x}\right) \,\bmod\, \left({z y}\right)$	$\displaystyle $	$\displaystyle $	$\displaystyle $	by definition

$\blacksquare$

\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle z \left({x \,\bmod\, y}\right)\)	\(=\)	\(\displaystyle z x - z y \left \lfloor {\frac x y}\right \rfloor\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle z x - z y \left \lfloor {\frac {z x} {z y} }\right \rfloor\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({z x}\right) \,\bmod\, \left({z y}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by definition