Modulo Multiplication is Well-Defined

From ProofWiki
Jump to navigation Jump to search

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$

is a well-defined operation.


That is:

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


Proof 1

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$


Proof 2

The equivalence class $\eqclass a m$ is defined as:

$\eqclass a m = \set {x \in \Z: x = a + k m: k \in \Z}$

that is, the set of all integers which differ from $a$ by an integer multiple of $m$.

Thus the notation for addition of two residue classes modulo $z$ is not usually $\eqclass a m +_m \eqclass b m$.

What is more normally seen is:

$a b \pmod m$

Using this notation:

\(\displaystyle a\) \(\equiv\) \(\displaystyle b\) \(\displaystyle \pmod m\)
\(\, \displaystyle \land \, \) \(\displaystyle c\) \(\equiv\) \(\displaystyle d\) \(\displaystyle \pmod m\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle a \bmod m\) \(=\) \(\displaystyle b \bmod m\) Definition of Congruence Modulo Integer
\(\, \displaystyle \land \, \) \(\displaystyle c \bmod m\) \(=\) \(\displaystyle d \bmod m\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle a\) \(=\) \(\displaystyle b + k_1 m\) for some $k_1 \in \Z$
\(\, \displaystyle \land \, \) \(\displaystyle c\) \(=\) \(\displaystyle d + k_2 m\) for some $k_2 \in \Z$
\(\displaystyle \leadsto \ \ \) \(\displaystyle a c\) \(=\) \(\displaystyle \paren {b + k_1 m} \paren {d + k_2 m}\) Definition of Multiplication
\(\displaystyle \) \(=\) \(\displaystyle b d + b k_2 m + d k_1 m + k_1 k_2 m^2\) Integer Multiplication Distributes over Addition
\(\displaystyle \) \(=\) \(\displaystyle b d + \paren {b k_2 + d k_1 + k_1 k_2 m} m\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle a c\) \(\equiv\) \(\displaystyle b d\) \(\displaystyle \pmod m\) Definition of Modulo Multiplication

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


Warning

Let $z \in \R$ be a real number.

Let:

$a \equiv b \pmod z$

and:

$x \equiv y \pmod z$

where $a, b, x, y \in \R$.


Then it does not necessarily hold that:

$a x \equiv b y \pmod z$


Sources