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:
(2)
\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:
(3)
\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$