Basic Properties of Congruences Modulo m 2

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 1 page.

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

• Proof: Let $a \equiv b \pmod m$ and $c \equiv d \pmod m$. Then $m \mid (b - a)$ and $m \mid (d - c)$. So:

(2)

\begin{align} \quad m & \mid [(b - a) + (d - c)] \\ \quad m & \mid [(b + d) - (a + c)] \end{align}

• Hence $(a + c) \equiv (b + d) \pmod m$. $\blacksquare$

Proposition 2: Let $a, b, c, d, m \in \mathbb{Z}$. If $a \equiv b \pmod m$ and $c \equiv d \pmod m$ then $ac \equiv bd \pmod m$.

• Proof: Let $a \equiv b \pmod m$ and $c \equiv d \pmod m$. Then $m \mid (b - a)$ and $m \mid (d - c)$. So there exists $k_1, k_2 \in \mathbb{Z}$ with $a = b + k_1m$ and $c = d + k_2m$. Multiplying these together gives us that:

(3)

\begin{align} \quad ac &= (b + k_1m)(d + k_2m) \\ \quad &= bd + k_2bm + k_1dm + k_1k_2m^2 \end{align}

• Hence:

(4)

\begin{align} \quad ac - bd = m(k_2b + k_1d + k_1k_2m) \end{align}

• So $m \mid (ac - bd)$, i.e., $ac \equiv bd \pmod m$. $\blacksquare$.

Proposition 3: Let $a, b, c, m \in \mathbb{Z}$ and let $(c, m) = 1$. If $ac \equiv bc \pmod m$ then $a \equiv b \pmod m$.

• Proof: If $ac \equiv bc \pmod m$ then $m \mid (bc - ac)$, so, $m \mid c(a - b)$. Since $(c, m) = 1$, we must have that $m \mid (b - a)$, so $a \equiv b \pmod m$. $\blacksquare$

Proposition 4: Let $a, b, c, d, m \in \mathbb{Z}$ and let $(c, m) = d$. If $ac \equiv bc \pmod m$ then $a \equiv b \pmod { \frac{m}{d}}$.

• Proof: If $ac \equiv bc \pmod m$ then $m \mid (bc - ac)$ so $m \mid c(b - a)$. Since $(c, m) = d$ we have that $d \mid m$ and $d \mid c$, so then:

(5)

\begin{align} \quad \frac{m}{d} \mid \frac{c}{d}(b - a) \end{align}

• Since $\left ( \frac{c}{d}, \frac{m}{d} \right ) = 1$ we have from the previous proposition that $\frac{m}{d} \mid b - a$. So $a \equiv b \pmod { \frac{m}{d}}$. $\blacksquare$