Modular Arithmetic

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.

🔗

Consider using Theorem 7.42 to prove the next theorem.

🔗

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{.}\)
🔗

🔗

🔗

One consequence of Theorem 7.92 Item b and Theorem 7.93 Item b is that parentheses are not needed when adding or multiplying congruence classes. The next theorem follows from Definition 7.90 together with Theorem 7.92 Item b and Theorem 7.93 Item b and induction on \(k\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{.}\)
🔗

🔗

🔗

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

🔗

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{?}\)

🔗

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

🔗

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
🔗

🔗

Prev Top Next