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)$ . (``cancellation 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   Which values of $x$ satisfy $4x\equiv 12 ({\rm mod} 5)$ ? Solution: Since $gcd(4,5)=1$ , we can use cancellation mod 5 to reduce the congruence to $x\equiv 3 ({\rm mod} 5)$ . So the solutions are $x=3+5k$ , for any integer $k$ .

Example 1.7.5   Which values of $x$ satisfy $16x\equiv 30 ({\rm mod} 17)$ ? Solution: Since $gcd(2,17)=1$ , we can use cancellation mod 17 to reduce the congruence to $8x\equiv 15 ({\rm mod} 17)$ . Until we learn how to compute the inverse of $8$ mod $17$ (see below), we cannot divide by $8$ . However, the following strategy works just as easily: add multiples of $17$ to $15$ until we can divide by $2$ again. For example, $8x\equiv 15 \equiv 32 ({\rm mod} 17)$ . As above, by the cancellation law, $x\equiv 4 ({\rm mod} 17)$ . So the solutions are $x=4+17k$ , for any integer $k$ .

Example 1.7.6   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.7   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.8   $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.11). 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.11 again, we must have $gcd(a,m)=1$ . $\Box$

More generally, we have the following result.

Proposition 1.7.9   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.