Modular Arithmetic

Definition: If $a, b, m \in \mathbb{Z}$ then we say that $a$ is Congruent to $b$ modulo $m$ denoted $a \equiv b \pmod m$ if $m \mid (a - b)$.

The congruence of two integers is an equivalence relation which we can describe in other words. We say that $a$ and $b$ are said to be congruent modulo $m$ if $a$ divided by $m$ leaves the same remaining as $b$ divided by $m$.

For example, $3 \equiv 7 \pmod 2$ since $2 \mid (3 - 7) = -4$. Notice also that when $3$ and $7$ are divided by $2$ they both leave the same remainder, $1$.

We can denote the remainder of an integer $a$ when divided by $m$ as simply $a \pmod m$. For example, $1 = 3 \pmod 2$ since the remaining of $3$ when divided by $2$ is $1$. We should note that from The Division Algorithm that the remainder $r$ when an integer $a$ is divided by $m$ satisfies the inequality $0 \leq r < m$. Therefore we note that for all nonnegative integers $a$ and positive integers $m$ that:

(1)

\begin{align} \quad 0 \leq a \pmod m < m \end{align}

In other words, for all nonnegative integers $a$ and positive integers $m$, the set of possible remainders when $a$ is divided by $m$ is $\{ 0, 1, 2, ..., m - 1 \}$.

Consequentially, we can define the set of odd integers and the set of even numbers in terms of these elements in the set of even integers being congruent to one another and elements in the set of odd numbers being congruent to one another.

Definition: An integer $z \in \mathbb{Z}$ is said to be Odd if $z \equiv 1 \pmod 2$ or Even if $z \equiv 0 \pmod 2$.

We will now look at some basic theorems regarding integer congruence modulo $m$.

Theorem 1: Let $a, b, c, d, m \in \mathbb{Z}$. Then: a) If $a \equiv b \pmod m$ then $b \equiv a \pmod m$. b) $a \equiv a \pmod m$. c) If $a \equiv b \pmod m$ and $b \equiv c \pmod m$ then $a \equiv c \pmod m$. d) If $a \equiv b \pmod m$ and $c \equiv d \pmod m$ then $(a + c) \equiv (b + d) \pmod m$. e) If $a \equiv b \pmod m$ and $c \equiv d \pmod m$ then $ac \equiv bd \pmod m$.

• Proof of a) Suppose that $a \equiv b \pmod m$. Then $m \mid (a - b)$ so there exists an integer $k$ such that:

(2)

\begin{align} \quad mk = a - b \\ \quad -mk = b - a \\ \quad m(-k) = b - a \end{align}

• Therefore $m \mid (b - a)$ so $b \equiv a \pmod m$. $\blacksquare$

• We have that $m \mid 0 = (a - a)$ for any integer $a$. Therefore $a \equiv a \pmod m$. $\blacksquare$

• Proof of c) Suppose that $a \equiv b \pmod m$ and $b \equiv c \pmod m$. Then $m \mid (a - b)$ and $m \mid (b - c)$ and there exists integers $k_1$ and $k_2$ such that:

(3)

\begin{align} \quad mk_1 = a - b \quad \mathrm{and} \quad mk_2 = b - c \end{align}

• From the second equation we have that $b = mk_2 + c$. Substituting this into the first equation gives us:

(4)

\begin{align} \quad mk_1 = a - (mk_2 + c) \\ \quad mk_1 + mk_2 = a - c \\ \quad m(k_1 + k_2) = a - c \end{align}

• Therefore $m \mid (a - c)$ so $a \equiv c \pmod m$. $\blacksquare$

• Proof of d): Suppose that $a \equiv b \pmod m$ and $c \equiv d \pmod m$. Then $m \mid (a - b)$ and $m \mid (c - d)$, so there exists integers $k_1$ and $k_2$ such that:

(5)

\begin{align} \quad mk_1 = a - b \quad \mathrm{and} \quad mk_2 = c - d \end{align}

• Adding these equations together gives us:

(6)

\begin{align} \quad mk_1 + mk_2 = (a - b) + (c - d) \\ \quad m(k_1 + k_2) = (a + c) - (b + d) \end{align}

• Therefore $m \mid (a + c) - (b + d)$ so $(a + c) \equiv (b + d) \pmod m$ $\blacksquare$

• Proof of e): Suppose that $a \equiv b \pmod m$ and $c \equiv d \pmod m$. Then $m \mid (a - b)$ and $m \mid (c - d)$, so there exists integers $k_1$ and $k_2$ such that:

(7)

\begin{align} \quad mk_1 = a - b \quad \mathrm{and} \quad mk_2 = c - d \\ \quad a = b + mk_1 \quad \mathrm{and} \quad c = d +mk_2 \end{align}

• Multiplying these equations together yields:

(8)

\begin{align} \quad ac = (b + mk_1)(d + mk_2) \\ \quad ac = bd + bmk_2 + dmk_1 + m^2k_1k_2 \\ \quad ac - bd = m(bk_2 + dk_1 + mk_1k_2) \end{align}

• Therefore $m \mid (ac - bd)$ so $ac \equiv bd \pmod m$. $\blacksquare$