Properties of $\equiv \ ({\rm mod}\ m)$

If the equivalence relation is congruence modulo $m$, $\equiv \ ({\rm mod}\ m)$, then equivalence classes are more often called residue classes. The element $i$ of a residue class $[a]$ mod $m$ with $0\leq i<m$ is called the remainder of $a$ mod $m$. Moreover, a residue class is sometimes denoted by a bar rather than by square brackets:

$$\overline{a}=\{b\in \mathbb{Z}\ \vert\ a\equiv b\ ({\rm mod}\ m)\} =a+m\mathbb{Z}.$$

(Of course, $\overline{a}$ depends implicitly on $m$.) In this case, the total possible number of distinct residue classes is finite (in fact, there are exactly $n$ such classes), $\overline{0}, \overline{1}, ..., \overline{m-1}$.

Example 1.7.2   Let $m=100$ and $a=37$, $b=63$. Note that $\overline{a}=\overline{37}=37+100\mathbb{Z}$, $\overline{-a}=\overline{-37}=-37+100\mathbb{Z} =-37+100+100\mathbb{Z}=\overline{63}=\overline{b}$. Also, $\overline{37}=\overline{137}=\overline{237}=...$ and $\overline{37}=\overline{-63}=\overline{-163}=...$.

Lemma 1.7.3   Fix an integral modulus $m>1$ and let $a,b,c,d$ be integers.

• If $a\equiv c\ ({\rm mod}\ m)$ and $b\equiv d\ ({\rm mod}\ m)$ then
  $$\begin{array}{c} a+b\equiv c+d\ ({\rm mod}\ m)\\ a-b\equiv ... ...d\ ({\rm mod}\ m)\\ a^2\equiv c^2\ ({\rm mod}\ m). \end{array}$$

• If $a+c\equiv b+c\ ({\rm mod}\ m)$ then $a\equiv b\ ({\rm mod}\ m)$.
• If $ac\equiv bc\ ({\rm mod}\ m)$ and $gcd(c,m)=1$ then $a\equiv b\ ({\rm mod}\ m)$.

proof: All of these are left as an exercise, except for the last one.

Assume $ac\equiv bc\ ({\rm mod}\ m)$ and $gcd(c,m)=1$. Then $m\vert(ac-bc)=c(a-b)$. By Proposition 1.2.16(3), $m\vert(a-b)$. $\Box$

Example 1.7.4   We shall now verify the divisibilty criteria for the cases $7\vert a$ and $8\vert a$ that were stated in §1.3.1, and leave the others as exercises.

We have $1001=7\cdot 11\cdot 13$, so $1000\equiv -1\ ({\rm mod}\ 7)$. Substituting, we obtain

$$\begin{array}{c} a_0+a_1 10 + a_2 100+ a_3 1000 + a_4 10^4 +... ...a_4 10 - a_5 100 +a_6 + a_7 10 +...\ ({\rm mod}\ 7) \end{array}$$

from which the divisibilty result for $7$ follows.

We have $1000=8\cdot 125$, so $1000\equiv 0\ ({\rm mod}\ 8)$. Substituting, we obtain

$$\begin{array}{c} a_0+a_1 10 + a_2 100+ a_3 1000 + a_4 10^4 +... ..... \\ \equiv a_0+a_1 10 + a_2 100 \ ({\rm mod}\ 8) \end{array}$$

from which the divisibilty result for $8$ follows.

The following result, which will be used later, is a consequence of the Euclidean algorithm.

Lemma 1.7.5   Let $a>0$ and $m>1$ be integers. $a$ is relatively prime to $m$ if and only if there is an integer $x$ such that $ax \equiv 1\ ({\rm mod}\ m)$.

The integer $x$ in the above lemma is called the inverse of $a$ modulo $m$.

Example 1.7.6   $5$ is the inverse of itself modulo $6$ since $5\cdot 5 = 25 \equiv 1\ ({\rm mod}\ 6)$.

proof: (only if) Assume $gcd(a,m)=1$. There are integers $x,y$ such that $ax+my=1$, by the Euclidean algorithm (more precisely, by Corollary 1.4.8). Thus $m\vert(ax-1)$.

(if) Assume $ax \equiv 1\ ({\rm mod}\ m)$. There is an integer $y$ such that $ax-1=my$. By Corollary 1.4.8 again, we must have $gcd(a,m)=1$. $\Box$

More generally, we have the following result.

Proposition 1.7.7   Let $a>0, b>0$ and $m>1$ be integers. $gcd(a,m)\vert b$ if and only if there is an integer $x$ such that $ax \equiv b\ ({\rm mod}\ m)$.

The result above tells us exactly when we can solve the ``modulo $m$ analogs'' of the equation $ax=b$ studied in elementary school. The proof (which requires the previous lemma and Proposition 1.2.16) is left as a good exercise.