7.4: Modular Arithmetic

In this section, we look at a particular family of equivalence relations on the integers and explore the way in which arithmetic interacts with them.

Definition 7.76. For each \(n\in \mathbb{N}\), define \(n\mathbb{Z}\) to be the set of all integers that are divisible by \(n\). In set-builder notation, we have \[n\mathbb{Z} := \{m \in \mathbb{Z} \mid m = nk \text{ for some } k \in \mathbb{Z}\}.\]

For example, \(5\mathbb{Z} = \{ \ldots,-10,-5,0,5,10,\ldots\}\) and \(2\mathbb{Z}\) is the set of even integers.

Problem 7.77. Consider the sets \(3 \mathbb{Z}\), \(5 \mathbb{Z}\), \(15 \mathbb{Z}\), and \(20 \mathbb{Z}\).

1. List at least five elements in each of the above sets.
2. Notice that \(3 \mathbb{Z} \cap5 \mathbb{Z} = n\mathbb{Z}\) for some \(n\in \mathbb{N}\). What is \(n\)? Describe \(15\mathbb{Z}\cap 20 \mathbb{Z}\) in a similar way.
3. Draw a Venn diagram illustrating how the sets \(3\mathbb{Z}\), \(5\mathbb{Z}\), and \(15\mathbb{Z}\) intersect.
4. Draw a Venn diagram illustrating how the sets \(5\mathbb{Z}\), \(15\mathbb{Z}\), and \(20\mathbb{Z}\) intersect.

Theorem 7.78. Let \(n\in \mathbb{N}\). If \(a,b \in n\mathbb{Z}\), then \(-a\), \(a+b\), and \(ab\) are also in \(n\mathbb{Z}\).

Definition 7.79. For each \(n\in \mathbb{N}\), define the relation \(\equiv_n\) on \(\mathbb{Z}\) via \(a\equiv_n b\) if \(a-b \in n\mathbb{Z}\). We read \(a\equiv_n b\) as “\(a\) is congruent to \(b\) modulo \(n\).”

Note that \(a-b \in n\mathbb{Z}\) if and only if \(n\) divides \(a-b\), which implies that \(a\equiv_n b\) if and only if \(n\) divides \(a-b\).

Example 7.80. We encountered \(\equiv_5\) in Problem 7.22 and discovered that there were five distinct sets of relatives. In particular, we have \[\begin{aligned} rel(0) & = \{\ldots, -10, -5, 0, 5, 10,\ldots\}\\ rel(1) & = \{\ldots, -9, -4, 1, 6, 11,\ldots\}\\ rel(2) & = \{\ldots, -8, -3, 2, 7, 12,\ldots\}\\ rel(3) & = \{\ldots, -7, -2, 3, 8, 13,\ldots\}\\ rel(4) & = \{\ldots, -6, -1, 4, 9, 14,\ldots\}.\end{aligned}\] Notice that this collection forms a partition of \(\mathbb{Z}\). By Corollary 7.74, the relation \(\equiv_5\) must be an equivalence relation.

The previous example generalizes as expected. You can prove the following theorem by either proving that \(\equiv_n\) is reflexive, symmetric, and transitive or by utilizing Corollary 7.74.

Theorem 7.81. For \(n\in \mathbb{N}\), the relation \(\equiv_n\) is an equivalence relation on \(\mathbb{Z}\).

We have have special notation and terminology for the equivalence classes that correspond to \(\equiv_n\).

Definition 7.82. For \(n\in \mathbb{N}\), let \([a]_n\) denote the equivalence class of \(a\) with respect to \(\equiv_n\) (see Definitions 7.17 and 7.44). The equivalence class \([a]_n\) is called the congruence (or residue) class of \(a\) modulo \(n\). The collection of all equivalence classes determined by \(\equiv_n\) is denoted \(\mathbb{Z}/n\mathbb{Z}\), which is read “\(\mathbb{Z}\) modulo \(n\mathbb{Z}\)".

Example 7.83. Let’s compute \([2]_7\). Tracing back through the definitions, we see that \[\begin{aligned} m \in [2]_7 & ⇐⇒ m \equiv_7 2\\ & ⇐⇒ m-2\in 7\mathbb{Z}\\ & ⇐⇒ m-2 = 7k \text{ for some $k\in \mathbb{Z}$}\\ & ⇐⇒ m = 7k+2 \text{ for some $k\in \mathbb{Z}$}.\end{aligned}\] Since the multiples of \(7\) are \(7\mathbb{Z} = \{\ldots,-14,-7,0,7,14,\ldots\}\), we can find \([2]_7\) by adding \(2\) to each element of \(7\mathbb{Z}\) to get \([2]_7 = \{\ldots,-12,-5,2,9,16,\ldots\}\).

Problem 7.84. For each of the following congruence classes, find five elements in the set such that at least one is greater than \(70\) and one is less than \(70\).

1. \([4]_7\)
2. \([-3]_7\)
3. \([7]_7\)

Problem 7.85. Describe \([0]_3\), \([1]_3\), \([2]_3\), \([4]_3\), and \([-2]_3\) as lists of elements as in Example 7.83. How many distinct congruence classes are in \(\mathbb{Z}/3\mathbb{Z}\)? Theorem 7.43 might be helpful.

Consider using Theorem 7.42 to prove the next theorem.

Theorem 7.86. For \(n\in \mathbb{N}\) and \(a,b\in \mathbb{Z}\), \([a]_n = [b]_n\) if and only if \(n\) divides \(a-b\).

Corollary 7.87. For \(n\in \mathbb{N}\) and \(a\in \mathbb{Z}\), \([a]_n = [0]_n\) if and only if \(n\) divides \(a\).

The next result provides a useful characterization for when two congruence classes are equal. The Division Algorithm will be useful when proving this theorem.

Theorem 7.88. For \(n\in \mathbb{N}\) and \(a,b\in \mathbb{Z}\), \([a]_n = [b]_n\) if and only if \(a\) and \(b\) have the same remainder when divided by \(n\).

When proving Part (a) of the next theorem, make use of Theorem 7.86. For Part (b), note that \(a_1b_1-a_2b_2 = a_1b_1 -a_2b_1 + a_2b_1-a_2b_2\).

Theorem 7.89. Let \(n\in \mathbb{N}\) and let \(a_1,a_2,b_1,b_2 \in \mathbb{Z}\). If \([a_1]_n = [a_2]_n\) and \([b_1]_n = [b_2]_n\), then

1. \([a_1+b_1]_n = [a_2+b_2]_n\), and
2. \([a_1\cdot b_1]_n = [a_2\cdot b_2]_n\).

The previous theorem allows us to define addition and multiplication in \(\mathbb{Z}/n\mathbb{Z}\).

Definition 7.90. Let \(n\in \mathbb{N}\). We define the sum and product of congruence classes in \(\mathbb{Z}/n\mathbb{Z}\) via \[[a]_n + [b]_n:= [a+b]_n \quad \text{and} \quad [a]_n \cdot [b]_n:= [a\cdot b]_n.\]

Example 7.91. By Definition 7.90, \([2]_7+[6]_7 = [2+6]_7 = [8]_7\). By Theorem 7.86, \([8]_7 = [1]_7\), and so \([2]_7+[6]_7 = [1]_7\). Similarly, \([2]_7\cdot[6]_7 = [2\cdot6]_7 = [12]_7 = [5]_7\).

Addition and multiplication for \(\mathbb{Z}/n\mathbb{Z}\) has many familiar—and some not so familiar—properties. For example, addition and multiplication of congruence classes are both associative and commutative. However, it is possible for \([a]_n\cdot[b]_n = [0]_n\) even when \([a]_n \neq [0]_n\) and \([b]_n \neq [0]_n\).

Theorem 7.92. If \(n\in \mathbb{N}\), then addition in \(\mathbb{Z}/n\mathbb{Z}\) is commutative and associative. That is, for all \([a]_n, [b]_n, [c]_n \in \mathbb{Z}/n\mathbb{Z}\), we have

1. \([a]_n + [b]_n = [b]_n + [a]_n\), and
2. [modular add assoc] \(([a]_n + [b]_n) + [c]_n = [a]_n + ([b]_n + [c]_n)\).

Theorem 7.93. If \(n\in \mathbb{N}\), then multiplication in \(\mathbb{Z}/n\mathbb{Z}\) is commutative and associative. That is, for all \([a]_n, [b]_n, [c]_n \in \mathbb{Z}/n\mathbb{Z}\), we have

1. \([a]_n \cdot [b]_n = [b]_n \cdot [a]_n\), and
2. [modular mult assoc] \(([a]_n \cdot [b]_n) \cdot [c]_n = [a]_n \cdot ([b]_n \cdot [c]_n)\).

One consequence of Theorems 7.92(b) and 7.93(b) is that parentheses are not needed when adding or multiplying congruence classes. The next theorem follows from Definition 7.90 together with Theorems 7.92(b) and 7.93(b) and induction on \(k\).

Theorem 7.94. Let \(n\in \mathbb{N}\). For all \(k\in \mathbb{N}\), if \([a_1]_n,[a_2]_n,\ldots, [a_k]_n \in \mathbb{Z}/n\mathbb{Z}\), then

1. \([a_1]_n+[a_2]_n+\cdots+ [a_k]_n = [a_1 + a_2 +\cdots+ a_k]_n\), and
2. \([a_1]_n [a_2]_n \cdots [a_k]_n = [a_1 a_2 \cdots a_k]_n\).

The next result is a special case of Theorem 7.94(b).

Corollary 7.95. Let \(n\in \mathbb{N}\). If \(a\in\mathbb{Z}\) and \(k\in \mathbb{N}\), then \(([a]_n)^k = [a^k]_n\)

Example 7.96. Let’s compute \([8^{179}]_7\). We see that \[\begin{aligned} _7 & = ([8]_7)^{179} & (\text{Corollary 7.95})\\ & = ([1]_7)^{179} & (\text{Theorem 7.86})\\ & = [1^{179}]_7 & (\text{Corollary 7.95})\\ & = [1]_7.\end{aligned}\]

For Part (a) in the next problem, use the fact that \([6]_7 = [-1]_7\). For Part (b), use the fact that \([2^3]_7 = [1]_7\).

Problem 7.97. For each of the following, find a number \(a\) with \(0\le a \le 6\) such that the given quantity is equal to \([a]_7\).

1. \([6^{179}]_7\)
2. \([2^{300}]_7\)
3. \([2^{301} +5]_7\)

Problem 7.98. Find \(a\) and \(b\) such that \([a]_6\cdot[b]_6 = [0]_6\) but \([a]_6 \neq [0]_6\) and \([b]_6 \neq [0]_6\).

Theorem 7.99. If \(n\in \mathbb{N}\) such that \(n\) is not prime, then there exists \([a]_n, [b]_n \in \mathbb{Z}/n\mathbb{Z}\) such that \([a]_n\cdot[b]_n = [0]_n\) while \([a]_n \neq [0]_n\) and \([b]_n \neq [0]_n\).

Theorem 7.100. Notice that \(2x = 1\) has no solution in \(\mathbb{Z}\). Show that \([2]_7[x]_7 = [1]_7\) does have a solution with \(x\) in \(\mathbb{Z}\). What about \([14]_7[x]_7 = [1]_7\)?

Theorem 7.101. Make use of Theorem 7.94, Corollary 7.95, and Theorem 7.86 to prove the following theorem.

If \(m\in \mathbb{N}\) such that \[m=a_k10^k + a_{k-1}10^{k-1} + \cdots + a_110 + a_0,\] where \(a_k, a_{k-1}, \ldots, a_1, a_0\in \{0,1,\ldots, 9\}\) (i.e., \(a_k, a_{k-1}, \ldots, a_1, a_0\) are the digits of \(m\)), then \[[m]_3 = [a_k + a_{k-1} + \cdots + a_1 + a_0]_3.\]

You likely recognize the next result. Its proof follows quickly from Corollary 7.87 together with the previous theorem.

Theorem 7.102. An integer is divisible by \(3\) if and only if the sum of its digits is divisible by \(3\).

Let’s revisit Theorem 7.21, which we originally proved by induction.

Problem 7.103. Use Corollary 7.87 to prove that for all integers \(n \ge 0\), \(3^{2n}-1\) is divisible by \(8\). You will need to handle the case involving \(n=0\) separately.

We close this chapter with a fun problem.

Problem 7.104. Prove or provide a counterexample: No integer \(n\) exists such that \(4n+3\) is a perfect square.