# Modulo Multiplication is Well-Defined/Proof 1

## Theorem

The multiplication modulo $m$ operation on $\Z_m$, the set of integers modulo $m$, defined by the rule:

$\eqclass x m \times_m \eqclass y m = \eqclass {x y} m$

That is:

If $a \equiv b \pmod m$ and $x \equiv y \pmod m$, then $a x \equiv b y \pmod m$.

## Proof

We need to show that if:

$\eqclass {x'} m = \eqclass x m$

and:

$\eqclass {y'} m = \eqclass y m$

then:

$\eqclass {x' y'} m = \eqclass {x y} m$

We have that:

$\eqclass {x'} m = \eqclass x m$

and:

$\eqclass {y'} m = \eqclass y m$

It follows from the definition of residue class modulo $m$ that:

$x \equiv x' \pmod m$

and:

$y \equiv y' \pmod m$

By definition, we have:

$x \equiv x' \pmod m \implies \exists k_1 \in \Z: x = x' + k_1 m$
$y \equiv y' \pmod m \implies \exists k_2 \in \Z: y = y' + k_2 m$

which gives us:

$x y = \paren {x' + k_1 m} \paren {y' + k_2 m} = x' y' + \paren {x' k_2 + y' k_1} m + k_1 k_2 m^2$

Thus by definition:

$x y \equiv \paren {x' y'} \pmod m$

Therefore, by the definition of residue class modulo $m$:

$\eqclass {x' y'} m = \eqclass {x y} m$

$\blacksquare$

## Examples

### Modulo Multiplication: $19 \times 6 \equiv 11 \times 2 \pmod 4$

 $\displaystyle 19$ $\equiv$ $\displaystyle 11$ $\displaystyle \pmod 4$ $\displaystyle 6$ $\equiv$ $\displaystyle 2$ $\displaystyle \pmod 4$ $\displaystyle \leadsto \ \$ $\displaystyle 19 \times 6 = 114$ $\equiv$ $\displaystyle 11 \times 2 = 22$ $\displaystyle \pmod 4$

### Modulo Multiplication: $2 \times 3 \equiv -6 \times 15 \pmod 4$

 $\displaystyle 2$ $\equiv$ $\displaystyle -6$ $\displaystyle \pmod 4$ Congruence Modulo $4$: $2 \equiv -6 \pmod 4$ $\displaystyle 3$ $\equiv$ $\displaystyle 15$ $\displaystyle \pmod 4$ Congruence Modulo $4$: $3 \equiv 15 \pmod 4$ $\displaystyle \leadsto \ \$ $\displaystyle 2 \times 3 = 6$ $\equiv$ $\displaystyle \paren {-6} \times 15 = -90$ $\displaystyle \pmod 4$