Modulo Multiplication Distributes over Modulo Addition

From ProofWiki
Jump to navigation Jump to search

Theorem

Multiplication modulo $m$ is distributive over addition modulo $m$:

$\forall \eqclass x m, \eqclass y m, \eqclass z m \in \Z_m$:
$\eqclass x m \times_m \paren {\eqclass y m +_m \eqclass z m} = \paren {\eqclass x m \times_m \eqclass y m} +_m \paren {\eqclass x m \times_m \eqclass z m}$
$\paren {\eqclass x m +_m \eqclass y m} \times_m \eqclass z m = \paren {\eqclass x m \times_m \eqclass z m} +_m \paren {\eqclass y m \times_m \eqclass z m}$

where $\Z_m$ is the set of integers modulo $m$.


That is, $\forall x, y, z, m \in \Z$:

$x \paren {y + z} \equiv x y + x z \pmod m$
$\paren {x + y} z \equiv x z + y z \pmod m$


Proof

Follows directly from the definition of multiplication modulo $m$ and addition modulo $m$:

\(\displaystyle \eqclass x m \times_m \paren {\eqclass y m +_m \eqclass z m}\) \(=\) \(\displaystyle \eqclass x m \times_m \eqclass {y + z} m\)
\(\displaystyle \) \(=\) \(\displaystyle \eqclass {x \paren {y + z} } m\)
\(\displaystyle \) \(=\) \(\displaystyle \eqclass {\paren {x y} + \paren {x z} } m\)
\(\displaystyle \) \(=\) \(\displaystyle \eqclass {x y} m +_m \eqclass {x z} m\)
\(\displaystyle \) \(=\) \(\displaystyle \paren {\eqclass x m \times_m \eqclass y m} +_m \paren {\eqclass x m \times_m \eqclass z m}\)


And the second is like it, namely this:

\(\displaystyle \paren {\eqclass x m +_m \eqclass y m} \times_m \eqclass z m\) \(=\) \(\displaystyle \eqclass {x + y} m \times_m \eqclass z m\)
\(\displaystyle \) \(=\) \(\displaystyle \eqclass {\paren {x + y} z} m\)
\(\displaystyle \) \(=\) \(\displaystyle \eqclass {\paren {x z} + \paren {y z} } m\)
\(\displaystyle \) \(=\) \(\displaystyle \eqclass {x z} m +_m \eqclass {y z} m\)
\(\displaystyle \) \(=\) \(\displaystyle \paren {\eqclass x m \times_m \eqclass z m} +_m \paren {\eqclass y m \times_m \eqclass z m}\)

$\blacksquare$


Sources