Modulo Multiplication is Well-Defined
Contents |
Theorem
The multiplication modulo $m$ operation on $\Z_m$, the set of integers modulo $m$, defined by the rule:
- $\left[\!\left[{x}\right]\!\right]_m \times_m \left[\!\left[{y}\right]\!\right]_m = \left[\!\left[{x y}\right]\!\right]_m$
is a well-defined operation.
Proof
We need to show that if:
- $\left[\!\left[{x'}\right]\!\right]_m = \left[\!\left[{x}\right]\!\right]_m$ and
- $\left[\!\left[{y'}\right]\!\right]_m = \left[\!\left[{y}\right]\!\right]_m$
then $\left[\!\left[{x' y'}\right]\!\right]_m = \left[\!\left[{x y}\right]\!\right]_m$.
Since $\left[\!\left[{x'}\right]\!\right]_m = \left[\!\left[{x}\right]\!\right]_m$ and $\left[\!\left[{y'}\right]\!\right]_m = \left[\!\left[{y}\right]\!\right]_m$, it follows from the definition of residue class modulo $m$ that $x \equiv x' \left({\bmod\, m}\right)$ and $y \equiv y' \left({\bmod\, m}\right)$.
By definition, we have:
- $x \equiv x' \left({\bmod\, m}\right) \implies \exists k_1 \in \Z: x = x' + k_1 m$
- $y \equiv y' \left({\bmod\, m}\right) \implies \exists k_2 \in \Z: y = y' + k_2 m$
which gives us $x y = \left({x' + k_1 m}\right) \left({y' + k_2 m}\right) = x' y' + \left({x' k_2 + y' k_1}\right) m + k_1 k_2 m^2$.
Thus by definition $x y \equiv \left({x' y'}\right) \left({\bmod\, m}\right)$.
Therefore, by the definition of residue class modulo $m$, $\left[\!\left[{x' y'}\right]\!\right]_m = \left[\!\left[{x y}\right]\!\right]_m$.
$\blacksquare$
Warning
This result does not hold when $x, y, m \notin \Z$.
We get to this stage in the above proof:
- $x y = \left({x' + k_1 m}\right) \left({y' + k_2 m}\right) = x' y' + \left({x' k_2 + y' k_1}\right) m + k_1 k_2 m^2$
and we note that:
- $\left({x' k_2 + y' k_1}\right) m + k_1 k_2 m^2$
is not necessarily an integer.
In fact, $\left({x' k_2 + y' k_1}\right) m + k_1 k_2 m^2$ can only be guaranteed to be an integer if each of $x', y', m \in \Z$.
Hence $x' y'$ is not necessarily congruent to $x y$.
Sources
- J.A. Green: Sets and Groups (1965)... (previous)... (next): $\S 2.6$
- Seth Warner: Modern Algebra (1965)... (previous)... (next): $\S 11$: Example $11.2$
- C.R.J. Clapham: Introduction to Abstract Algebra (1969)... (previous)... (next): $\S 1.6$: Theorem $4$
- B. Hartley and T.O. Hawkes: Rings, Modules and Linear Algebra (1970): $\S 1.2$: Ring Example $2$
- Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 34$
- Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): $\S 18.4$
- John F. Humphreys: A Course in Group Theory (1996): $\S 2$: Proposition $2.31$, Exercise $6$
