Modulo Multiplication is Associative/Proof 1

From ProofWiki
Jump to: navigation, search

Theorem

Multiplication modulo $m$ is associative:

$\forall \left[\!\left[{x}\right]\!\right]_m, \left[\!\left[{y}\right]\!\right]_m, \left[\!\left[{z}\right]\!\right]_m \in \Z_m: \left({\left[\!\left[{x}\right]\!\right]_m \times_m \left[\!\left[{y}\right]\!\right]_m}\right) \times_m \left[\!\left[{z}\right]\!\right]_m = \left[\!\left[{x}\right]\!\right]_m \times_m \left({\left[\!\left[{y}\right]\!\right]_m \times_m \left[\!\left[{z}\right]\!\right]_m}\right)$


That is:

$\forall x, y, z \in \Z_m: \left({x \cdot_m y}\right) \cdot_m z = x \cdot_m \left({y \cdot_m z}\right)$


Proof

\(\displaystyle \paren {\eqclass x m \times_m \eqclass y m} \times_m \eqclass z m\) \(=\) \(\displaystyle \eqclass {x y} m \times_m \eqclass z m\) Definition of Modulo Multiplication
\(\displaystyle \) \(=\) \(\displaystyle \eqclass {\paren {x y} z} m\) Definition of Modulo Multiplication
\(\displaystyle \) \(=\) \(\displaystyle \eqclass {x \paren {y z} } m\) Integer Multiplication is Associative
\(\displaystyle \) \(=\) \(\displaystyle \eqclass x m \times_m \eqclass {y z} m\) Definition of Modulo Multiplication
\(\displaystyle \) \(=\) \(\displaystyle \eqclass x m \times_m \paren {\eqclass y m \times_m \eqclass z m}\) Definition of Modulo Multiplication

$\blacksquare$


Sources