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:

$\displaystyle \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.

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{displaymath} \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}\end{displaymath}

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{displaymath} \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}\end{displaymath}

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.


David Joyner 2007-09-03