# Modulo Addition is Well-Defined

Jump to: navigation, search

## Theorem

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:

$\left[\!\left[{a}\right]\!\right]_m +_m \left[\!\left[{b}\right]\!\right]_m = \left[\!\left[{a + b}\right]\!\right]_m$

That is:

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

### Corollary

It follows that:

$\left[\!\left[{a}\right]\!\right]_m -_m \left[\!\left[{b}\right]\!\right]_m = \left[\!\left[{a - b}\right]\!\right]_m$

### Real Modulus

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:

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

## Proof 1

We need to show that if:

$\left[\!\left[{x'}\right]\!\right]_m = \left[\!\left[{x}\right]\!\right]_m$
$\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 set of integers 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 = 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$:

$\left[\!\left[{x' + y'}\right]\!\right]_m = \left[\!\left[{x + y}\right]\!\right]_m$

$\blacksquare$

## Proof 2

The equivalence class $\left[\!\left[{a}\right]\!\right]_m$ is defined as:

$\left[\!\left[{a}\right]\!\right]_m = \left\{{x \in \Z: x = a + k m: k \in \Z}\right\}$

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 $\left[\!\left[{a}\right]\!\right]_m +_m \left[\!\left[{b}\right]\!\right]_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 + \left({k_1 + k_2}\right) 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$

$\blacksquare$