Modulo Addition is Well-Defined

From ProofWiki
Jump to: navigation, search


Let $m \in \Z$ be an integer.

Let $\Z_m$ be the set of integers modulo $m$.

The modulo addition operation on $\Z_m$, defined by the rule:

$\eqclass a m +_m \eqclass b m = \eqclass {a + b} 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$.


It follows that:

$\eqclass a m -_m \eqclass b m = \eqclass {a - b} m$

is a well-defined operation.

Real Modulus

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


$a \equiv b \pmod z$


$x \equiv y \pmod z$

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


$a + x \equiv b + y \pmod z$

Proof 1

We need to show that if:

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


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


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


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

it follows from the definition of set of integers modulo $m$ that:

$x \equiv x' \pmod m$


$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 = x' + k_1 m + y' + k_2 m = x' + y' + \left({k_1 + k_2}\right) m$

As $k_1 + k_2$ is an integer, it follows that, by definition:

$x + y \equiv \left({x' + y'}\right) \pmod m$

Therefore, by the definition of integers modulo $m$:

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


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 set of integers modulo $m$ 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\) $\quad$ $\quad$
\(\, \displaystyle \land \, \) \(\displaystyle c\) \(\equiv\) \(\displaystyle d\) \(\displaystyle \pmod m\) $\quad$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle a \bmod m\) \(=\) \(\displaystyle b \bmod m\) $\quad$ Definition of Congruence Modulo Integer $\quad$
\(\, \displaystyle \land \, \) \(\displaystyle c \bmod m\) \(=\) \(\displaystyle d \bmod m\) $\quad$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle a\) \(=\) \(\displaystyle b + k_1 m\) $\quad$ for some $k_1 \in \Z$ $\quad$
\(\, \displaystyle \land \, \) \(\displaystyle c\) \(=\) \(\displaystyle d + k_2 m\) $\quad$ for some $k_2 \in \Z$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle a + c\) \(=\) \(\displaystyle b + d + \paren {k_1 + k_2} m\) $\quad$ Definition of Integer Addition $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle a + c\) \(\equiv\) \(\displaystyle b + d\) \(\displaystyle \pmod m\) $\quad$ Definition of Modulo Addition $\quad$



Modulo Addition: $19 + 6 \equiv 11 + 2 \pmod 4$

We have:

\(\displaystyle 19\) \(\equiv\) \(\displaystyle 11\) \(\displaystyle \pmod 4\) $\quad$ $\quad$
\(\displaystyle 6\) \(\equiv\) \(\displaystyle 2\) \(\displaystyle \pmod 4\) $\quad$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle 19 + 6 = 25\) \(\equiv\) \(\displaystyle 11 + 2 = 13\) \(\displaystyle \pmod 4\) $\quad$ $\quad$