7.4: Modular Arithmetic

Suppose, as usual, that \(\sim\) is an equivalence relation on a set \(A\). Writing \(a \sim b\) means that \(a\) is “equivalent” to \(b\). In this case, we may want to think of \(a\) as being equal to \(b\). But that would not be right, because \(a\) and \(b\) are (probably) two different things. However, we have the following fundamental property of equivalence classes: \[a \sim b \quad \text { iff } \quad[a]=[b] .\]

Thus, by putting square brackets around \(a\) and \(b\), we can turn mere equivalence into true equality. That is what makes equivalence classes so important. A good example is provided by congruence modulo \(n\).

7.4A. The integers modulo 3.

For any \(n \in \mathbb{Z}\), we know that congruence modulo \(n\) is an equivalence relation (see Exercise \(5.1.18\)). As an example, let us consider the case where \(n = 3\). To emphasize the fact that \(n = 3\), we will include a subscript ₃ in the notation for an equivalence class: we write \([k]_{3}\), instead of \([k]\).

We all know that when an integer is divided by 3, the remainder must be either 0, 1, or 2, so Exercise \(5.1.22(1)\) tells us that every integer is congruent (modulo 3) to either 0, 1, or 2. Thus,

• for every \(k \in \mathbb{Z}\), the equivalence class \([k]_{3}\) must be either \([0]_{3}\), \([1]_{3}\), or \([2]_{3}\). On the other hand, it is easy to check that no two of 0, 1, and 2 are congruent (modulo 3), so
• \([0]_{3}\), \([1]_{3}\), and \([2]_{3}\) are three distinct equivalence classes.

Thus, we see that there are exactly three equivalence classes, namely, \([0]_{3}\), \([1]_{3}\), and \([2]_{3}\). The set of these equivalence classes is called the integers modulo 3. It is denoted \(\mathbb{Z}_{3}\).

Notation \(7.4.1\).

The notation \([k]_{3}\) (or even just \([k]\)) is rather cumbersome. For convenience, we may write \(\bar{k}\) for the equivalence class of \(k\). Thus, \[\mathbb{Z}_{3}=\{\overline{0}, \overline{1}, \overline{2}\} .\]

Definition \(7.4.2\).

We can do arithmetic (add, subtract, and multiply) on these equivalence classes, just as we do for ordinary integers. This is called arithmetic modulo 3. The rules are:

• \(\left.[a]_{3}+[b]_{3}=[a+b]_{3} \quad \text { (or } \bar{a}+\bar{b}=\overline{a+b}\right),\)
• \(\left.[a]_{3}-[b]_{3}=[a-b]_{3} \quad \text { (or } \bar{a}-\bar{b}=\overline{a-b}\right) \text {, and }\)
• \([a]_{3} \times[b]_{3}=[a b]_{3} \quad(\text { or } \bar{a} \times \bar{b}=\overline{a b}) .\)

(Actually, we should write \(+_{3}\), \(−_{3}\), and \(\times_{3}\), to indicate that the arithmetic is being done modulo 3, but we will usually not bother.)

Example \(7.4.3\).

We have \([1]_{3}+[2]_{3}=[1+2]_{3}=[3]_{3}\). However, since \(3 \equiv 0(\bmod 3)\), we have \([3]_{3} = [0]_{3}\), so the above equation can also be written as

Solution

\([1]_{3}+[2]_{3}=[0]_{3}\). Equivalently, \(\overline{1}+\overline{2}=\overline{0}\).

This is an example of the following general principle: \[\text { If } r \text { is the remainder when } a+b \text { is divided by } 3 \text {, then } \bar{a}+{ }_{3} \bar{b}=\bar{r} \text {. }\]

Example \(7.4.4\).

Here is a table that shows the results of addition modulo 3:

Solution

\[\begin{array}{c||c|c|c}
+_{3} & \overline{0} & \overline{1} & \overline{2} \\
\hline \hline \overline{0} & \overline{0} & \overline{1} & \overline{2} \\
\hline \overline{1} & \overline{1} & \overline{2} & \overline{0} \\
\hline \overline{2} & \overline{2} & \overline{0} & \overline{1}
\end{array}\]

Exercise \(7.4.5\).

Make a table that shows the results of:

1. subtraction modulo 3
2. multiplication modulo 3

(Write each of the entries of your table as either \(\overline{0}, \overline{1}\) or \(\overline{2}\).)

7.4B. The integers modulo \(n\).

The preceding discussion can be generalized to apply with any integer \(n\) in place of 3. This results in modular arithmetic.

Definition \(7.4.6\).

Fix some nonzero natural number \(n \in \mathbb{N}^{+}\).

1. For any integer \(k\), we use \([k]_{n}\) to denote the equivalence class of \(k\) under congruence modulo \(n\). When \(n\) is clear from the context, we may write \(\overline{k}\), instead of \([k]_{n}\).
2. The set of these equivalence classes is called the integers modulo \(n\). It is denoted \(\mathbb{Z}_{n}\).
3. Addition, subtraction, and multiplication modulo \(n\) are defined by:
   • \(\bar{a}+{ }_{n} \bar{b}=\overline{a+b}\),
   • \(\bar{a}-{ }_{n} \bar{b}=\overline{a-b}\), and
   • \(\bar{a} \times_{n} \bar{b}=\overline{a b}\).

(When \(n\) is clear from the context, we usually write \(+\), \(−\), and \(\times\), rather than \(+_{n}\), \(−_{n}\), and \(\times_{n}\).)

Note that \(\# \mathbb{Z}_{n}=n\). More precisely:

Proposition \(7.4.7\).

For any \(n \in \mathbb{N}^{+}\), we have \[\mathbb{Z}_{n}=\{\overline{0}, \overline{1}, \overline{2}, \ldots, \overline{n-1}\}\]

and \(\overline{0}, \overline{1}, \overline{2}, \ldots, \overline{n-1}\) are all distinct.

Example \(\PageIndex{1}\)

Simplify \((\overline{17}-\overline{5}) \times(\overline{21}+\overline{11})\) in \(\mathbb{Z}_{7}\).

Solution

We have \[\begin{aligned}
(\overline{17}-\overline{5}) \times(\overline{21}+\overline{11}) &=(\overline{3}-\overline{5}) \times(\overline{0}+\overline{4})=(3-5) \times(\overline{0+4}) \\
&=\overline{-2} \times \overline{4}=\overline{5} \times \overline{4}=\overline{5 \times 4}=\overline{20}=\overline{6} .
\end{aligned}\]

Exercise \(7.4.9\).

1. Simplify \((\overline{17}-\overline{5}) \times(\overline{21}+\overline{11})\) in \(\mathbb{Z}_{5}\).
2. Simplify \(\overline{32}+(\overline{23} \times \overline{16})\) in \(\mathbb{Z}_{9}\).
3. Simplify \((\overline{25} \times \overline{35})+(\overline{18}-\overline{12})\) in \(\mathbb{Z}_{12}\).
4. Make tables that show the results of:
   1. addition modulo 4.
   2. subtraction modulo 5.
   3. multiplication modulo 6.
5. Find \(x, y \in \mathbb{Z}_{12}\), such that \(x \neq \overline{0}\) and \(y \neq \overline{0}\), but \(x y=\overline{0}\).