Modulo Multiplication is Associative

Theorem

$\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 1

 $\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$

Proof 2

Let $j$ be the largest integer such that:

$j m \le x y$

Let $p$ be the largest integer such that:

$p m \le y z$

By definition of multiplication modulo $m$:

$x \cdot_m y = x y - j m$
$y \cdot_m z = y z - p m$

Let $k$ be the largest integer such that:

$k m \le \paren {x y - j m} z$

Let $q$ be the largest integer such that:

$q m \le x \paren {y z - p m}$

Then:

$\paren {j z + k} m \le \paren {x y} z$
$\paren {q + x p} m \le x \paren {y z}$

Thus:

 $\displaystyle \paren {x \cdot_m y} \cdot_m z$ $=$ $\displaystyle \paren {x y - j m} z - k m$ Definition of Modulo Multiplication $\displaystyle x \cdot_m \paren {y \cdot_m z}$ $=$ $\displaystyle x \left({y z - p m}\right) - q m$ Definition of Modulo Multiplication

But suppose that there exists an integer $s$ such that:

$s m \le \paren {x y} z$

and:

$j z + k < s$

Then:

$\paren {j z + k + 1} m \le \paren {x y} z$

from which:

$\paren {k + 1} m \le \paren {x y - j m} z$

But this contradicts the definition of $k$.

Thus $j z + k$ is the largest of those integers $i$ such that $i m \le \paren {x y} z$.

Similarly, $q + x p$ is the largest of those integers $i$ such that $i m \le x \paren {y z}$.

$\paren {x y} z = x \paren {y z}$

Thus $j z + k = q + x p$ and so:

 $\displaystyle \paren {x \cdot_m y} \cdot_m z$ $=$ $\displaystyle \paren {x y - j m} z - k m$ Definition of Modulo Multiplication $\displaystyle$ $=$ $\displaystyle x y z - \paren {j z + k} m$ $\displaystyle$ $=$ $\displaystyle x y z - \paren {q + x p} m$ $\displaystyle$ $=$ $\displaystyle x \paren {y z - p m} - q m$ $\displaystyle$ $=$ $\displaystyle x \cdot_m \paren {y \cdot_m z}$ Definition of Modulo Multiplication

$\blacksquare$