Basic Properties of Congruences Modulo m
Basic Properties of Congruences Modulo m 1
Recall from the Congruences Modulo m page that if $a, b, m \in \mathbb{Z}$ then $a$ is said to be congruent to $b$ modulo $m$ written $a \equiv b \pmod m$ if:
(1)\begin{align} \quad m \mid (b - a) \end{align}
We noted that $a$ and $b$ are congruent modulo $m$ if and only if they have the same remainder upon division by $m$.
We will now look at some additional basic properties of congruences modulo $m$. More results can be found on the Basic Properties of Congruences Modulo m 2 page.
| Proposition 1: Let $a, m \in \mathbb{Z}$. Then $m \mid a$ if and only if $a \equiv 0 \pmod m$. |
- Proof: $\Rightarrow$ If $m \mid a$ then $m \mid (a - 0)$ so $a \equiv 0 \pmod m$.
- $\Leftarrow$ If $a \equiv 0 \pmod m$ then $m \mid (a - 0)$ so $m \mid a$. $\blacksquare$
| Proposition 2: Let $a, m \in \mathbb{Z}$. Then $a \equiv a \pmod m$. |
Proposition 2 is often referred to as the reflexivity property of congruences modulo $m$.
- Proof: Note that $m \mid 0$ for all $m \in \mathbb{Z}$, so $m \mid (a - a)$. Thus $a \equiv a \pmod m$. $\blacksquare$
| Proposition 3: Let $a, b, m \in \mathbb{Z}$. Then $a \equiv b \pmod m$ if and only if $b \equiv a \pmod m$. |
Proposition 3 is often referred to as the symmetry property of congruences modulo $m$.
- Proof: $\Rightarrow$ Suppose that $a \equiv b \pmod m$. Then there exists a $k \in \mathbb{Z}$ with $a = b + km$. So then:
\begin{align} \quad b = a + (-k)m \end{align}
- Let $k^* = -k$. Then there exists a $k^* \in \mathbb{Z}$ with $b = a + k^*m$, so $b \equiv a \pmod m$.
- $\Leftarrow$ Identical argument as above. $\blacksquare$
| Propositon 4: Let $a, b, c, m \in \mathbb{Z}$. If $a \equiv b \pmod m$ and $b \equiv c \pmod m$ then $a \equiv c \pmod m$. |
Proposition 4 is often referred to as the transitivity property of congruences modulo $m$.
- Proof: Suppose that $a \equiv b \pmod m$ and $b \equiv c \pmod m$. Then $m \mid (b - a)$ and $m \mid (c - b)$. Thus:
\begin{align} \quad m & \mid [(c - b) + (b - a)] \\ \quad m & \mid [c - b + b - a] \\ \quad m & \mid (c - a) \end{align}
- Hence $a \equiv c \pmod m$. $\blacksquare$