Congruences Modulo m
Congruences Modulo m
We will now look at a very important and useful type of equivalence relation called the congruence equivalence relation which tells us that two integers are congruent modulo another integer $m$ if they leave the same remainder upon division by $m$. We will begin with the precise, "mathy" statement.
Definition: Let $a, b, m \in \mathbb{Z}$. Then $a$ is said to be Congruent to $b$ modulo $m$ written $a \equiv b \pmod m$ if $m \mid (a - b)$. |
For example, $5$ is congruent to $2$ modulo $3$ because $3 \mid (5 - 2)$. We will now look at some simple results regarding congruences.
Theorem 1: Let $a, b, m \in \mathbb{Z}$. Then $a \equiv b \pmod m$ if and only if there exists a $k \in \mathbb{Z}$ such that $a = b + km$. |
- Proof: $\Rightarrow$ Suppose that $a \equiv b \pmod m$. Then $m \mid (a - b)$. So there exists a $k \in \mathbb{Z}$ such that $km = (a - b)$, thus:
\begin{align} \quad a = b + km \end{align}
- $\Leftarrow$ Conversely, suppose that there exists a $k \in \mathbb{Z}$ such that $a = b + km$. Then $km = a - b$, so $m \mid (a - b)$. Thus $a \equiv b \pmod m$. $\blacksquare$
Theorem 2: Let $a, m \in \mathbb{Z}$. Then $a \equiv b \pmod m$ for exactly one integer $b \in \{ 0, 1, ..., m - 1 \}$. |
- Proof: Recall that for any $a, m \in \mathbb{Z}$ that $a$ can be written as the form $a = b + km$ for some $k \in \mathbb{Z}$ and where $b$ is the remainder of $a$ upon division by $m$. Therefore $b \in \{ 0, 1, ..., m - 1 \}$ and moreover, $a \equiv b \pmod m$. $\blacksquare$
Theorem 3: Let $a, b, m \in \mathbb{Z}$. Then $a \equiv b \pmod m$ if and only if $a$ and $b$ have the same remainder upon division by $m$. |
- Proof: $\Rightarrow$ Suppose that $a \equiv b \pmod m$ and let $r_1$ be the remainder when $a$ is divided by $m$, and let $r_2$ be the remainder when $b$ is divided by $m$. Then there exists $k_1, k_2 \in \mathbb{Z}$ such that:
\begin{align} \quad a = r_1 + k_1m \quad \mathrm{and} \quad b = r_2 + k_2m \end{align}
- Since $m \mid (a - b)$ this means that:
\begin{align} \quad m & \mid ([r_1 + k_1m] - [r_2 + k_2m]) \\ \quad m & \mid ([r_1 - r_2] + [k_1 - k_2]m) \\ \quad m & \mid (r_1 - r_2) \end{align}
- But this implies that $r_1 \equiv r_2 \pmod m$. Since $r_1, r_2 \in \{ 0, 1, ..., m - 1 \}$ and by Theorem 2 we have that $r_1 = r_2$.
- $\Leftarrow$ Suppose that $a$ and $b$ have the same remainder when divided by $m$, call it $r \in \mathbb{Z}$. Then for some $k_1, k_2 \in \mathbb{Z}$ we have:
\begin{align} \quad a = r + k_1m \quad \mathrm{and} \quad b = r + k_2m \end{align}
- Now note that:
\begin{align} \quad b - a = (r + k_2m) - (r + k_1m) = (r - r) + (k_2 - k_1)m = (k_2 - k_1)m \end{align}
- Thus $m \mid (b - a)$, so $a \equiv b \pmod m$. $\blacksquare$