4.1. Divisibility and Modular Arithmetic

Throughout this chapter we will be exploring the properties of the integers::

\[ \ldots, -4, -3, -2, -1, 0, 1, 2, 3, 4, \ldots \]

In so-called ring theory the integers are an integral domain. The key property of integral domain is the cancellation property.

\[ \text{If } a \neq 0 \text{ and } ab = ac \text{, then } b = c. \]

This property suggests a natural setting for the study of a divisibility.

4.1.1. Divisibility

Definition (divisible)

If \(a\) and \(b\) are integers, with \(a \neq 0\), we say \(a\) divides \(b\) if there exists an integer \(q\) such that \(b = aq\). When \(a\) divides \(b\) we write \(a \,|\, b\). When \(a\) does not divide \(b\) we write \(a \,\nmid\, b\).

From these definition we get special names for \(a\), \(b\), \(q\). When we have \(b = aq\),

• \(a\) is the divisor or factor of \(b\)

• \(b\) is the dividend or multiple of \(a\)

• \(q\) is the quotient

Divisibility

The following hold.

\[ 3 \mid 9 \qquad\qquad 3 \nmid 17 \qquad\qquad 3 \mid 315 \]

The property of divisibility leads to many combinations and later results. We have the following theorem.

Theorem

Let \(a\), \(b\), and \(c\) be integers with \(a \neq 0\).

1. If \(a \mid b\) and \(a \mid c\) then \(a \mid (b+c)\)

2. If \(a \mid b\) then \(a \mid bc\)

3. If \(a \mid b\) and \(b \mid c\) then \(a \mid c\).

Let us prove the first statement.

Suppose \(a \mid b\) and \(a \mid c\). Then there exists integers \(q_1\) and \(q_2\) such that \(b = aq_1\) and \(c = aq_2\). Hence, \(b + c = aq_1 + a q_2\). Therefore, we have \(b+c = a(q_1 + q_2)\). Since \(q_1 + q_2\) is an integer, \(a \mid (b+c)\).

Checkpoint

Divisibility Proofs

Prove the second and third statement of the previous theorem.

Solution

Divisibility Proofs

1. Let \(a \mid b\). Therefore, an integer \(q\) exists such that \(b = aq\). Then, for any choice of integer \(c\), we have \(bc = aqc = a(qc)\). Letting \(q' = qc\), we have \(bc = aq'\) and surely \(a \mid bc\).

2. Let \(a \mid b\) and \(b \mid c\). Therefore we have integers \(q_1\) and \(q_2\) such that \(b = aq_1\) and \(c = bq_2\). Substituting, we have \(c = aq_1q_2\). Therefore, \(a \mid c\).

\(\blacksquare\)

---

4.1.2. Division with remainder

Division with remainder is also called Euclidean division. It is both an algorithm and a theorem for computing quotients and remainders.

We saw previously that when a number divides another number “perfectly” then we get a quotient and an equation of the form \(b = aq\). However, it is often the case that division cannot be performed exactly. This is the role of the remainder.

For example, \(3 \nmid 14\), but \(14 = 3\cdot 4 + 2\). We say that \(3\) divides \(14\) four times, with a remainder of \(2\).

Here is a formal definition.

Theorem (Euclidean division)

Let \(a, b\) be integers with \(a \neq 0\). There exists unique integers \(q\) and \(r\) such that:

\[ b = aq + r, \quad \text{and} \quad 0 \leq r < a. \]

Proof

First, notice that we can always re-write a division with remainder relation in terms of positive integers. Indeed, if \(a < 0\) then \(b = aq + r\) can be re-written as \(b = a'q' + r\) with \(a' = -a\) and \(q' = -q\). The case for \(b < 0\) is similar and left to the reader.

Therefore, we only have to consider the case where \(a,b,q,r\) are all non-negative integers.

Now we prove existence of quotient and remainder. We will show \(q = \lfloor \frac{b}{a} \rfloor\). By definition we have that \(0 \leq r < a\) and \(b = aq + r\). Therefore:

\[\begin{split} \begin{align} aq &\leq aq + r < a(q + 1) \\ aq &\leq b < a(q + 1) \\ q &\leq \frac{b}{a} < q + 1 \\ q &= \lfloor \frac{b}{a}\rfloor \end{align} \end{split}\]

Since \(a, b, q, r\) are integers with \(a \neq 0\) and \(0 \leq r < b\), \(r\) can uniquely be determined from \(a\), \(b\), and \(q\).

Next we prove that the quotient and remainder are unique. Let \(b = aq_1 + r_1 = aq_2 + r_2\) such that \(a,b,q,r\) are non-negative integers and \(0 \leq r_1 < a\) and \(0 \leq r_2 < a\). Proceed by contradiction and assume \(r_1 \neq r_2\). W.l.o.g. assume \(r_2 > r_1\). Then,

\[\begin{split} \begin{align} aq_1 - aq_2 = r_2 - r_1 \\ a(q_1 - q_2) = r_2 - r_1\\ \end{align} \end{split}\]

From \(a(q_1 - q_2) = r_2 - r_1\), we have that \(a \mid r_2 - r_1\).

However, since \(0 \leq r_1 < a\) and \(0 \leq r_2 < a\), and \(r_2 > r_1\), it must be that \(0 < (r_2 - r_1) < a\).

Yet, the multiples of \(a\) are \(0, \pm a, \pm 2a, \pm 3a, \ldots\). Since \(r_2 - r_1 < a\), it must be that \(r_2 - r_1 = 0\) and hence \(r_2 = r_1\). A contradiction.

Since \(r_2 = r_1\), it follows that \(q_2 = q_1\) from \(a \neq 0\) and:

\[\begin{split} \begin{align} aq_1 + r_1 &= aq_2 + r_2 \\ aq_1 &= aq_2 \\ a(q_1 - q_2) &= 0 \rightarrow q_1 - q_2 = 0 \end{align} \end{split}\]

From Euclidean division we get two sub-operations: div and mod. div refers to the quotient and mod to the remainder.

• \(b\) div \(a = q\), and

• \(b\) mod \(a = r\).

---

4.1.3. Congruence Relations

Congruence relations or congruencies are special kinds of equivalencies. We have already seen equivalence classes as a generalization of equality. Congruence is very similar; they are special kinds of equivalences with respect to a modulus.

Definition (congruent)

Two integers \(a\) and \(b\) are congruent modulo a positive integer \(m\) if \(m\) divides \(a - b\).

Congruencies are all about remainders. Modulo \(m\), two integers \(a\) and \(b\) are congruent if:

\[ a \textbf{ mod } m = b \textbf{ mod } m. \]

When two numbers are congruent modulo \(m\) we write \(a \equiv b \bmod m\) and we say “\(a\) is congruent to \(b\) modulo \(m\)”. In this case, the relation \(a \equiv b\) is a congruence and \(m\) is the modulus.

A first congruence

Modulo \(6\) we have:

\[ 17 \equiv 5 \bmod 6 \]

since \(17 - 5 = 12\) and \(6 \mid 12\).

However,

\[ 24 \not\equiv 14 \bmod 6 \]

since \(24 - 14 = 10\) and \(6 \nmid 10\).

---

Modulo as “removing multiples”

One way to think of modulo is as an operation which removes all multiples of the modulus from an expression. It is a “simplification”.

Removing multiples

Consider \(26\) mod \(5\). It is easy to see that \(26 = 5\cdot 5 + 1\). By Euclidean division, this implies that the remainder of \(26\) when divided by \(5\) is \(1\). Hence, \(26 \equiv 1 \bmod 5\).

More generally, we have the following theorem which shows the relation between congruent integers.

Theorem

Let \(m\) be a positive integer. The integers \(a\) and \(b\) are congruent modulo \(m\) if and only if there exists an integer \(k\) such that \(a = b + km\).

Proof:

If \(a \equiv b \bmod m\) then, by definition, \(m \mid a -b\). Hence, there must exist an integer \(k\) such that \(a - b = km\). Thus, \(a = b + km\).

Conversely, if there exists an integer \(k\) such that \(a = b + km\), then we of course have \(km = a -b\) and thus \(m \mid a - b\) and \(a \equiv b \bmod m\). \(\blacksquare\)

---

mod versus \(\bmod\)

Note that mod and \(\bmod\) are not exactly the same thing. Although they are highly related. The former is a function. \(a\) mod \(b = r\) is a function taking \(a\) and \(b\) are arguments and outputting the remainder \(r\) of \(a\) divided by \(b\).

On the other hand, \(\bmod\) is a binary relation. In fact, it defines an equivalence relation, as we will see in a later section. Let us consider that relation.

Theorem

Let \(a\), \(b\) be integers and \(m\) be a positive integer. \(a \equiv b \bmod m\) if and only if \(a\) mod \(m\) \(=\) \(b\) mod \(m\).

Proof

Via Euclidean division we have the following equations:

\[\begin{split} a = q_am + r_a \\[1em] b = q_bm + r_b \end{split}\]

where \(0 \leq r_a < m\) and \(0 \leq r_b < m\).

\(\rightarrow\). We will prove \(a \equiv b \bmod m\) implies that \(r_a = r_b\). By definition, \(a \equiv b \bmod m\) means \(m \mid a - b\). Therefore, there exists an integer \(k\) such that \(mk = a - b\). Then we have:

\[\begin{split} a - b = km = (q_a - q_b)m + r_a - r_b \\[1em] (k - q_a - q_b)m = r_a - r_b. \end{split}\]

This tells us that \(m \mid (r_a - r_b)\). Meanwhile, \(0 \leq r_a < m\) and \(0 \leq r_b < m\) implies that \(-m < r_a - r_b < m\). The only multiple of \(m\) satisfying those constraints is \(0\). Therefore, \(r_a - r_b = 0\) and \(r_a = r_b\).

\(\leftarrow\). We will prove that \(r_a = r_b\) implies \(a \equiv b \bmod m\). By Euclidean division we have:

\[\begin{split} a = q_am + r_a \\[1em] b = q_bm + r_b \\[1em] a - b = m(q_a - q_b) \end{split}\]

Therefore, \(m\) divides \(a-b\) and, by definition, \(a \equiv b \bmod m\). \(\blacksquare\)

---

Congruence, sums, and products

Congruence relations allow for interesting algebraic manipulation. Consider first addition.

Theorem

Let \(a,b,c,d\) be integers, and let \(m\) be a positive integer. If \(a \equiv b \bmod m\) and \(c \equiv d \bmod m\), then:

\[ a + c \equiv b + d \bmod m \]

Proof: By a previous theorem, we have that the congruences imply the existence of integers \(k,\ell\) and the equations:

\[ b = a + km, \qquad\text{and}\qquad c = d + \ell m \]

From those equations we have:

\[ b + d = (a + km) + (c + \ell m) = (a + c) + (k + \ell)m \]

Therefore, \(b + d \equiv a + c \bmod m\). \(\blacksquare\)

More generally, we can perform algebraic manipulations on several equations while “working modulo \(m\)”. As a consequence of the previous theorem, if we multiply both sides of a congruence by the same integer, the congruence still holds. For any integer \(c\) we have:

\[ a \equiv b \bmod m \quad\rightarrow\quad c\cdot a \equiv c \cdot b \bmod m. \]

Adding an integer to both sides of a congruence also maintains the congruence. For any integer \(d\) we have:

\[ a \equiv b \bmod m \quad\rightarrow\quad d + a \equiv d + b \bmod m. \]

Caution

Division does not always maintain congruences. Notice that \(14 \equiv 8 \bmod 6\). However, \(\frac{14}{2} \not\equiv \frac{8}{2} \bmod 6\).

Indeed, \(\frac{14}{2} = 7\), \(\frac{8}{2} = 4\) and \(7 \not\equiv 4 \bmod 6\).

---

4.1.4. Arithmetic modulo \(m\)

All of these previous theorems imply an interesting structure on the “integers modulo \(m\)”.

Indeed, the previous theorems lead to the following properties:

1. \((a+b)\) mod \(m\) \(=\) \(((a\) mod \(m) + (b\) mod \(m))\) mod \(m\)

2. \((a\cdot b)\) mod \(m\) \(=\) \(((a\) mod \(m) \cdot (b\) mod \(m))\) mod \(m\)

These equations have a very important consequence. They tell us that we can either perform arithmetic first, and then take remainders, or, we can take remainders first and then perform arithmetic. (This is one kind of isomorphism.)

Let \(\mathbb{Z}_m = \{0,1, 2, \ldots, m-1\}\) be the set of non-negative integers less than \(m\).

On this set, we can define a special kind of addition and multiplication using the previous equations. These addition and multiplication operations act on elements of \(\mathbb{Z}_m\) and always return another element of \(\mathbb{Z}_m\).

Addition modulo \(m\)

Let \(+_m\) be addition on the set of numbers \(\mathbb{Z}_m\) defined as:

\[ a +_m b = (a + b) \textbf{ mod } m \]

Multiplication modulo \(m\)

Let \(\times_m\) be multiplication on the set of numbers \(\mathbb{Z}_m\) defined as:

\[ a \times_m b = (a \times b) \textbf{ mod } m \]

Using \(+_m\) and \(\times_m\) rather than the normal addition and subtraction of the integers is said to “working modulo \(m\)” or “doing arithmetic modulo \(m\)”.

Working modulo \(11\).

Let \(\mathbb{Z}_{11}\) be the set of integers \(\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}\).

We have the following arithmetic equations.

\[\begin{split} 7 +_{11} 9 = (7 + 9) \textbf{ mod } 11 = 16 \textbf{ mod } 11 = 5 \\[1em] 7 \times_{11} 9 = (7 \times 9) \textbf{ mod } 11 = 63 \textbf{ mod } 11 = 8 \\[1em] \end{split}\]

Checkpoint

Modular arithmetic

1. Let \(m\) = 17. Compute \(16 +_{17} 13\).

2. Let \(m\) = 103. Compute \(45 \times_{103} 77\).

3. Let \(m\) = 32. Compute \(4 \times_{32} 8\).

4. Let \(m\) = 25. Compute \(-103 +_{25} 79\).

Solution

Divisibility Proofs

1. \(12\)

2. \(66\)

3. \(0\)

4. \(1\). This one is a little tricky. Notice that \(-103 \equiv 22 \bmod 25\) since \(-103 = -5\cdot 25 + 22\). Then, \(22 + 79 \equiv 101 \equiv 1 \bmod 25\).

---

Properties of arithmetic modulo \(m\)

As stated previously, the operations \(+_m\) and \(\times_m\) on the set \(\mathbb{Z}_m\) act very similar to the normal addition and multiplcation of the integers. In fact, these operations define a commutative ring.

In this course we will not define rings formally or consider so-called ring theory. However, we will observe some useful properties of these arithmetic operations on \(\mathbb{Z}_m\)

1. Closure. If \(a, b \in \mathbb{Z}_m\), then \(a +_m b \in \mathbb{Z}_m\) and \(a \times_m b \in \mathbb{Z}_m\).

   \[\]

2. Associativity. If \(a, b, c \in \mathbb{Z}\) then \((a +_m b) +_m c = a +_m (b +_m c)\) and \(a \times_m (b \times_m c) = (a \times_m b) \times_m c\).

   \[\]

3. Commutativity. If \(a, b \in \mathbb{Z}\) then \(a +_m b = b +_m a\) and \(a \times_m b = b \times_m a\).

   \[\]

4. Identity. The elements \(0\) and \(1\) are identities of addition and multiplication. \(a +_m 0 = a\) and \(a \times_m 1 = a\).

   \[\]

5. Additive inverses. If \(a \neq 0 \in \mathbb{Z}_m\) then \(m-a\) is the additive inverse of \(a\) such that \(a +_m (m-a) = 0\).

   \[\]

6. Distributivity. If \(a, b, c \in \mathbb{Z}_m\) then \(a \times_m (b +_m c) = (a \times_m b) +_m (a \times_m c)\).

---

Congruence as equivalence relations

Over the integers, congruence modulo \(m\) induces an equivalence relation on \(\mathbb{Z}\).

As a binary relation on \(\mathbb{Z}\), congruence modulo \(m\) is reflexive, symmetric and transitive.

1. Reflexive. For any \(a \in \mathbb{Z}\), \(a \equiv a \bmod m\) since \(m \mid a - a\).

   \[\]

2. Symmetric. For \(a, b \in \mathbb{Z}\), \(a \equiv b \bmod m\) implies \(b \equiv a \bmod m\) since \(m \mid a - b\) also implies that \(m \mid b - a\).

   \[\]

3. Transitive. If \(a, b, c \in \mathbb{Z}\) with \(a \equiv b \bmod m\) and \(b \equiv c \bmod m\) then \(a \equiv c \bmod m\). Indeed, we have \(m \mid (b-a)\) and \(m \mid (b-c)\), thus \(\exists k,\ell \in \mathbb{Z}\) such that:

   \[\begin{split} \begin{align} \ \\[1em] b-a = mk \quad\text{ and }\quad c-b = m\ell \quad \rightarrow\quad & c-m\ell - a = mk \\[1em] & c - a = m(\ell +k) \\[1em] \end{align} \end{split}\]

   Hence \(m \mid c-a\) and \(a \equiv c \bmod m\).

Since congruence is an equivalence relation, it also implies the existence of equivalence classes. These are special equivalence classes that we call congruence classes.

Definition (congruence class)

The congruence class modulo \(m\) of an integer \(x\) is the set of all integers congruent to \(x\) modulo \(m\).

We denote congruence classes as \(\overline{x}\). You can also use the typical equivalence class notation of \([x]\). The set $\overline{x} is:

\[ \overline{x} = \{a \in \mathbb{Z} \ |\ x \equiv a \bmod m\} \]

Notice that modulo itself is does not define a congruence relation or congruence classes. We need to work modulo a specific modulus. The set of all congruence classes, and the members of each congruence class, changes with the choice of modulus.

Congruence classes

Let \(m = 5\). The set of all equivalence classes modulo \(m\) are:

\[ \{\overline{0}, \overline{1}, \overline{2}, \overline{3}, \overline{4}\} \]

Notice that this set is very similar to \(\mathbb{Z}_5 = \{0, 1, 2, 3, 4\}\). Indeed, the set of congruence classes modulo \(5\) and \(\mathbb{Z}_5\) are “essentially the same”; they are isomorphic.

More generally, we have the following proposition.

Proposition

An integer is congruent modulo \(m\) to its remainder on division by \(m\). There are \(m\) congruence classes modulo \(m\), each corresponding to the \(m\) possible remainders.

Let \(m\mathbb{Z}\) represent all integer multiples of \(m\). That is, the set \(\{\ldots, -2m, -m, 0, m, 2m, \ldots\}\). Then, the set of congruence classes modulo \(m\) are:

\[\begin{split} \begin{align} \overline{0} &= m\mathbb{Z} \\[0.75em] \overline{1} &= m\mathbb{Z} + 1 \\[0.75em] \overline{2} &= m\mathbb{Z} + 2 \\[0.75em] \vdots \\[0.75em] \overline{m-1} &= m\mathbb{Z} + (m-1) \\[0.75em] \end{align} \end{split}\]

4.1.5. Exercises

Exercise 4.1

Prove the following theorem.

Theorem

Let \(a,b,c,d\) be integers and \(m\) be a positive integer. If \(a \equiv b \bmod m\) and \(c \equiv d \bmod m\), then \(ac \equiv bd \bmod m\).

Exercise 4.2

Prove that an integer is congruent modulo \(m\) to its remainder on division by \(m\).

Solution to Exercise 4.2

Let \(x\) be an integer. By Euclidean division \(\exists q, r \in \mathbb{Z}\) such that

\[ x = mq + r \]

Then, we have \(mq = x -r\). Hence, \(m \mid x - r\). By definition, \(x \equiv r \bmod m\). \(\blacksquare\)

Exercise 4.3

Compute the following values.

1. The quotient of \(54\) divided by \(6\).

2. The remainder of \(54\) divided by \(6\).

3. The quotient of \(1235\) divided by \(12\).

4. \(144\) mod \(7\)

5. \(123\) div \(7\)

6. \(-17\) mod \(3\)

7. \(-101\) mod \(13\)

Solution to Exercise 4.3

1. \(9\)

2. \(0\)

3. \(102\)

4. \(4\)

5. \(17\)

6. \(1\)

7. \(3\)

Exercise 4.4

Consider an analog clock which shows the numbers 1 through 12.

What time does the clock show:

1. 48 hours after it shows 5:00?

2. 17 hours after it shows 11:00?

3. 103 hours after it shows 4:00?

Solution to Exercise 4.4

1. 5:00

2. 4:00

3. 11:00

Exercise 4.5

Find an integer \(x\) satisfying the following:

1. \(x \equiv 43 \bmod 23\), where \(-22 \leq x \leq 0\)

2. \(x \equiv 17 \bmod 29\), where \(-14 \leq x \leq 14\)

3. \(x \equiv -11 \bmod 21\), where \(90 \leq x \leq 110\)

Solution to Exercise 4.5

1. -3

2. -12

3. 94

Exercise 4.6

Consider the equivalence relation on \(\mathbb{Z}\) induced by congruence modulo \(29\). Show that, the product of any element of the equivalence class \(\overline{6}\) with any element of the equivalence class \(\overline{7}\) is an element of the equivalence class \(\overline{13}\).

Solution to Exercise 4.6

\[\begin{split} \overline{6} = \{29k + 6 \ |\ k \in \mathhb{Z}\} \\ \overline{7} = \{29\ell + 7 \ |\ \ell \in \mathhb{Z}\} \\ \overline{13} = \{29n + 13 \ |\ n \in \mathhb{Z}\} \\ 29k + 29\ell + 6 + 7 = 29(k+\ell) + 13 \in \overline{13} \end{split}\]

Exercise 4.7

Prove the following theorem.

Theorem

Let \(a,b,c\) be integers and \(m\) be a positive integer. If \(a \equiv b \bmod m\) then \(ac \equiv bc \bmod m\).

Solution to

If \(a \equiv b \bmod m\) then \(a + mk = b\) for some integer \(k\). Then, \(ca + cmk = cb\). Let \(k' = ck\) and we have \(ca + mk' = cb\). Thus, \(ac \equiv bc \bmod m\).

Exercise 4.8

Let \(a,b,c\) be integers and \(m\) be a positive integer such that \(a \equiv b \bmod m\).

1. Let \(m = 6\). Find values for \(a, b, c\) such that \(a \equiv b \bmod 6\), \(\frac{a}{c} \in \mathbb{Z}\), \(\frac{b}{c} \in \mathbb{Z}\) and \(\frac{a}{c} \equiv \frac{b}{c} \bmod 6\).

2. Let \(m= 9\). Find values for \(a, b, c\) such that \(a \equiv b \bmod 9\), \(\frac{a}{c} \in \mathbb{Z}\), \(\frac{b}{c} \in \mathbb{Z}\), and \(\frac{a}{c} \not\equiv \frac{b}{c} \bmod 9\).

Solution to

1. \(a=8, b=20, c=2\)

2. \(a=3, b=12, c=3\)

Exercise 4.9

Let \(\mathbb{Z}_{11}\) be the set of numbers \(\{0,1,2,3,4,\ldots,10\}\). Show that, using modular multiplication, every non-zero number in \(\mathbb{Z}_{11}\) has a multiplicative inverse that is also an element of \(\mathbb{Z}_{11}\).

For example, \(2 \times_{11} 6 = 1\) Therefore, the inverse of \(2\) is \(6\).

Solution to

1. The inverse of \(1\) is \(1\).

2. The inverse of \(2\) is \(6\).

3. The inverse of \(3\) is \(4\).

4. The inverse of \(4\) is \(3\).

5. The inverse of \(5\) is \(9\).

6. The inverse of \(6\) is \(2\).

7. The inverse of \(7\) is \(8\).

8. The inverse of \(8\) is \(7\).

9. The inverse of \(9\) is \(5\).

10. The inverse of \(10\) is \(10\). Wow!