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$