Section 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}\text{,}\) define \(n\mathbb{Z}\) to be the set of all integers that are divisible by \(n\text{.}\) In set-builder notation, we have
\begin{equation*}
\tcboxmath{n\mathbb{Z} \coloneqq \{m \in \mathbb{Z} \mid m = nk \text{ for some } k \in \mathbb{Z}\}}\text{.}
\end{equation*}
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}\text{,}\) \(5 \mathbb{Z}\text{,}\) \(15 \mathbb{Z}\text{,}\) and \(20 \mathbb{Z}\text{.}\)
List at least five elements in each of the above sets.
Notice that \(3 \mathbb{Z} \cap5 \mathbb{Z} = n\mathbb{Z}\) for some \(n\in \mathbb{N}\text{.}\) What is \(n\text{?}\) Describe \(15\mathbb{Z}\cap 20 \mathbb{Z}\) in a similar way.
Draw a Venn diagram illustrating how the sets \(3\mathbb{Z}\text{,}\) \(5\mathbb{Z}\text{,}\) and \(15\mathbb{Z}\) intersect.
Draw a Venn diagram illustrating how the sets \(5\mathbb{Z}\text{,}\) \(15\mathbb{Z}\text{,}\) and \(20\mathbb{Z}\) intersect.
Theorem 7.78.
Let \(n\in \mathbb{N}\text{.}\) If \(a,b \in n\mathbb{Z}\text{,}\) then \(-a\text{,}\) \(a+b\text{,}\) and \(ab\) are also in \(n\mathbb{Z}\text{.}\)
Definition 7.79.
For each \(n\in \mathbb{N}\text{,}\) define the relation \(\tcboxmath{\equiv_n}\) on \(\mathbb{Z}\) via \(a\equiv_n b\) if \(a-b \in n\mathbb{Z}\text{.}\) We read \(a\equiv_n b\) as “\(a\) is congruent to \(b\) modulo \(n\text{.}\)”
Note that \(a-b \in n\mathbb{Z}\) if and only if \(n\) divides \(a-b\text{,}\) which implies that \(a\equiv_n b\) if and only if \(n\) divides \(a-b\text{.}\)
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{align*}
\rel(0) \amp = \{\ldots, -10, -5, 0, 5, 10,\ldots\}\\
\rel(1) \amp = \{\ldots, -9, -4, 1, 6, 11,\ldots\}\\
\rel(2) \amp = \{\ldots, -8, -3, 2, 7, 12,\ldots\}\\
\rel(3) \amp = \{\ldots, -7, -2, 3, 8, 13,\ldots\}\\
\rel(4) \amp = \{\ldots, -6, -1, 4, 9, 14,\ldots\}\text{.}
\end{align*}
Notice that this collection forms a partition of
\(\mathbb{Z}\text{.}\) By
Theorem 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
Theorem 7.74.
Theorem 7.81.
For \(n\in \mathbb{N}\text{,}\) the relation \(\equiv_n\) is an equivalence relation on \(\mathbb{Z}\text{.}\)
We have have special notation and terminology for the equivalence classes that correspond to \(\equiv_n\text{.}\)
Definition 7.82.
For
\(n\in \mathbb{N}\text{,}\) let
\(\tcboxmath{[a]_n}\) denote the equivalence class of
\(a\) with respect to
\(\equiv_n\) (see
Definition 7.17 and
Definition 7.44). The equivalence class
\([a]_n\) is called the congruence (or residue) class of
\(a\) modulo
\(n\text{.}\) The collection of all equivalence classes determined by
\(\equiv_n\) is denoted
\(\tcboxmath{\mathbb{Z}/n\mathbb{Z}}\text{,}\) which is read “
\(\mathbb{Z}\) modulo
\(n\mathbb{Z}\)”.
Example 7.83.
Let’s compute \([2]_7\text{.}\) Tracing back through the definitions, we see that
\begin{align*}
m \in [2]_7 \amp \logeq m \equiv_7 2\\
\amp \logeq m-2\in 7\mathbb{Z}\\
\amp \logeq m-2 = 7k \text{ for some \(k\in \mathbb{Z}\)}\\
\amp \logeq m = 7k+2 \text{ for some \(k\in \mathbb{Z}\)} \text{.}
\end{align*}
Since the multiples of \(7\) are \(7\mathbb{Z} = \{\ldots,-14,-7,0,7,14,\ldots\}\text{,}\) 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\}\text{.}\)
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\text{.}\)
\(\displaystyle [4]_7\)
\(\displaystyle [-3]_7\)
\(\displaystyle [7]_7\)
Problem 7.85.
Describe
\([0]_3\text{,}\) \([1]_3\text{,}\) \([2]_3\text{,}\) \([4]_3\text{,}\) and
\([-2]_3\) as lists of elements as in
Example 7.83. How many distinct congruence classes are in
\(\mathbb{Z}/3\mathbb{Z}\text{?}\) Theorem 7.43 might be helpful.
Theorem 7.86.
For \(n\in \mathbb{N}\) and \(a,b\in \mathbb{Z}\text{,}\) \([a]_n = [b]_n\) if and only if \(n\) divides \(a-b\text{.}\)
Corollary 7.87.
For \(n\in \mathbb{N}\) and \(a\in \mathbb{Z}\text{,}\) \([a]_n = [0]_n\) if and only if \(n\) divides \(a\text{.}\)
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}\text{,}\) \([a]_n = [b]_n\) if and only if \(a\) and \(b\) have the same remainder when divided by \(n\text{.}\)
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\text{.}\)
Theorem 7.89.
Let \(n\in \mathbb{N}\) and let \(a_1,a_2,b_1,b_2 \in \mathbb{Z}\text{.}\) If \([a_1]_n = [a_2]_n\) and \([b_1]_n = [b_2]_n\text{,}\) then
\([a_1+b_1]_n = [a_2+b_2]_n\text{,}\) and
\([a_1\cdot b_1]_n = [a_2\cdot b_2]_n\text{.}\)
The previous theorem allows us to define addition and multiplication in \(\mathbb{Z}/n\mathbb{Z}\text{.}\)
Definition 7.90.
Let \(n\in \mathbb{N}\text{.}\) We define the sum and product of congruence classes in \(\mathbb{Z}/n\mathbb{Z}\) via
\begin{equation*}
[a]_n + [b]_n\coloneqq [a+b]_n \text{ and } [a]_n \cdot [b]_n\coloneqq [a\cdot b]_n\text{.}
\end{equation*}
Example 7.91.
By
Definition 7.90,
\([2]_7+[6]_7 = [2+6]_7 = [8]_7\text{.}\) By
Theorem 7.86,
\([8]_7 = [1]_7\text{,}\) and so
\([2]_7+[6]_7 = [1]_7\text{.}\) Similarly,
\([2]_7\cdot[6]_7 = [2\cdot6]_7 = [12]_7 = [5]_7\text{.}\)
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\text{.}\)
Theorem 7.92.
If \(n\in \mathbb{N}\text{,}\) 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}\text{,}\) we have
\([a]_n + [b]_n = [b]_n + [a]_n\text{,}\) and
\(([a]_n + [b]_n) + [c]_n = [a]_n + ([b]_n + [c]_n)\text{.}\)
Theorem 7.93.
If \(n\in \mathbb{N}\text{,}\) 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}\text{,}\) we have
\([a]_n \cdot [b]_n = [b]_n \cdot [a]_n\text{,}\) and
\(([a]_n \cdot [b]_n) \cdot [c]_n = [a]_n \cdot ([b]_n \cdot [c]_n)\text{.}\)
Theorem 7.94.
Let \(n\in \mathbb{N}\text{.}\) For all \(k\in \mathbb{N}\text{,}\) if \([a_1]_n,[a_2]_n,\ldots, [a_k]_n \in \mathbb{Z}/n\mathbb{Z}\text{,}\) then
\([a_1]_n+[a_2]_n+\cdots+ [a_k]_n = [a_1 + a_2 +\cdots+ a_k]_n\text{,}\) and
\([a_1]_n [a_2]_n \cdots [a_k]_n = [a_1 a_2 \cdots a_k]_n\text{.}\)
Corollary 7.95.
Let \(n\in \mathbb{N}\text{.}\) If \(a\in\mathbb{Z}\) and \(k\in \mathbb{N}\text{,}\) then \(([a]_n)^k = [a^k]_n\text{.}\)
Example 7.96.
Let’s compute \([8^{179}]_7\text{.}\) We see that
\begin{align*}
[8^{179}]_7 \amp = ([8]_7)^{179} \amp (\knowl{./knowl/xref/cor_modular_power.html}{\text{Corollary 7.95}})\\
\amp = ([1]_7)^{179} \amp (\knowl{./knowl/xref/thm_cong_classes_equal.html}{\text{Theorem 7.86}})\\
\amp = [1^{179}]_7 \amp (\knowl{./knowl/xref/cor_modular_power.html}{\text{Corollary 7.95}})\\
\amp = [1]_7\text{.}
\end{align*}
For Part (a) in the next problem, use the fact that \([6]_7 = [-1]_7\text{.}\) For Part (b), use the fact that \([2^3]_7 = [1]_7\text{.}\)
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\text{.}\)
\(\displaystyle [6^{179}]_7\)
\(\displaystyle [2^{300}]_7\)
\(\displaystyle [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\text{.}\)
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\text{.}\)
Problem 7.100.
Notice that \(2x = 1\) has no solution in \(\mathbb{Z}\text{.}\) Show that \([2]_7[x]_7 = [1]_7\) does have a solution with \(x\) in \(\mathbb{Z}\text{.}\) What about \([14]_7[x]_7 = [1]_7\text{?}\)
Theorem 7.101.
If \(m\in \mathbb{N}\) such that
\begin{equation*}
m=a_k10^k + a_{k-1}10^{k-1} + \cdots + a_110 + a_0\text{,}
\end{equation*}
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
\begin{equation*}
[m]_3 = [a_k + a_{k-1} + \cdots + a_1 + a_0]_3\text{.}
\end{equation*}
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\text{.}\)
Let’s revisit
Theorem 4.21, which we originally proved by induction.
Problem 7.103.
Use
Corollary 7.87 to prove that for all integers
\(n \ge 0\text{,}\) \(3^{2n}-1\) is divisible by
\(8\text{.}\) 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.
Without change something sleeps inside us, and seldom awakens. The sleeper must awaken.
―Dune by Frank Herbert
