Modulo Multiplication is Associative

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 1

\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \left({\left[\!\left[{x}\right]\!\right]_m \times_m \left[\!\left[{y}\right]\!\right]_m}\right) \times_m \left[\!\left[{z}\right]\!\right]_m\) \(=\) \(\displaystyle \) \(\) \(\displaystyle \) \(\displaystyle \left[\!\left[{x y}\right]\!\right]_m \times_m \left[\!\left[{z}\right]\!\right]_m\) \(\displaystyle \) \(\displaystyle \)          Definition of Multiplication Modulo $m$          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\) \(\displaystyle \) \(\displaystyle \left[\!\left[{\left({x y}\right) z}\right]\!\right]_m\) \(\displaystyle \) \(\displaystyle \)          Definition of Multiplication Modulo $m$          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\) \(\displaystyle \) \(\displaystyle \left[\!\left[{x \left({y z}\right)}\right]\!\right]_m\) \(\displaystyle \) \(\displaystyle \)          Integer Multiplication is Associative          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\) \(\displaystyle \) \(\displaystyle \left[\!\left[{x}\right]\!\right]_m \times_m \left[\!\left[{y z}\right]\!\right]_m\) \(\displaystyle \) \(\displaystyle \)          Definition of Multiplication Modulo $m$          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\) \(\displaystyle \) \(\displaystyle \left[\!\left[{x}\right]\!\right]_m \times_m \left({\left[\!\left[{y}\right]\!\right]_m \times_m \left[\!\left[{z}\right]\!\right]_m}\right)\) \(\displaystyle \) \(\displaystyle \)          Definition of Multiplication Modulo $m$          

$\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 \left({x y - j m}\right) z$

Let $q$ be the largest integer such that:

$q m \le x \left({y z - p m}\right)$

Then:

$\left({j z + k}\right) m \le \left({x y}\right) z$
$\left({q + x p}\right) m \le x \left({y z}\right)$

Thus:

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


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

$s m \le \left({x y}\right) z$

and:

$j z + k < s$

Then:

$\left({j z + k + 1}\right) m \le \left({x y}\right) z$

from which:

$\left({k + 1}\right) m \le \left({x y - j m}\right) z$

But this contradicts the definition of $k$.

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


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

From Integer Multiplication is Associative:

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

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

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

$\blacksquare$


Sources