Skip to main content
Logo image

Discrete Math for Shockers

John Hammond

Section 3.1 Divisibility and Congruences

The purpose of this section is twofold. First, Now that we have some experience with mathematical proof, we’re now going to expand the types of questions we can prove by introducing the Divides and Congruence relations. Second, this is the first step in building the tools we need towards working with some encryption algorithms.

Subsection The Divides Relation

Note 3.1.1.

Any time we say “number” in the context of divides, congruence, or number theory we mean integer.
In Example 1.3.3, we saw the divides relation. Because we’re going to use this relation frequently, we will introduce its own notation.

Definition 3.1.2. The Divides Relation.

Let \(a \and b\) be two integers with \(a \not= 0\text{.}\) We say \(a\) divides \(b\) and write \(a \divides b\) if there exists an integer \(m\) such that \(b = am\text{.}\)
We say that \(a\) is a factor of \(b\text{,}\) and \(b\) is a multiple of \(a\text{.}\)

Example 3.1.3.

The following are examples of the divides relation:
  1. \(3 \divides 6\) since \(6 = 3\cdot 2\)
  2. \(4 \divides 100\) since \(100 = 4 \cdot 25\)
Here are some non-examples:
  1. \(4 \nmid 10\) since there is no integer \(m\) for which \(10 = 4m\text{.}\)
  2. \(6 \nmid 3 \text{.}\) Order matters.
This is a good time to remember that the relational statment \(a \mid b\) is a propositional statement. It is true or false. Let’s compare the divides relation with some similar symbols.

Example 3.1.4.

What kind of object are each of the following? What is the value, truth or numeric?
  1. \(\displaystyle 2 \mid 8 \)
  2. \(\displaystyle 14 \modulus 5 \)
  3. \(\displaystyle 20 / 4 \)
  4. \(\displaystyle 8 \mid 4 \)
  5. \(\displaystyle 8 \div 4\)
Solution.
  1. This is a statement. It is saying “2 divides into 8 evenly.” This statement is true.
  2. This is a number. Its value is 4, since the remainder of 14 divided by 5 is 4.
  3. This is a number. Its value is 5.
  4. This is a statement. It says “8 divides into 4 evenly.” This is false.
  5. This is a number. Its value is 2.
The divisibility relation has some very nice properties that let us practice our new skill of mathematical proof on this new object.

Example 3.1.8.

Use the Division Algorithm to write each division as \(n = dq +r\) with \(0 \le r \lt d\text{,}\) with the variables defined in the statement above.
  1. \(\displaystyle 543 \div 7\)
  2. \(\displaystyle -42 \div 13\)
Video / Answer.

Subsection The Congruence Relation

Definition 3.1.9. The Congruence Relation.

Let \(a \and b\) be two integers and \(m\) be a positive integer. We say that \(a\) is congruent to \(b\) modulo \(m\) if
\begin{equation*} m \divides (b-a) \end{equation*}
We write \(a \equiv b \pmod m\)
We call \(m\) the modulus.

Example 3.1.10.

Each of these statements is true:
  1. \(\displaystyle 13 \equiv 6 \pmod 7 \)
  2. \(\displaystyle -8 \equiv 6 \pmod 7 \)
  3. \(\displaystyle 7 \equiv 0 \pmod 7\)
Video / Answer.

Note 3.1.11.

Let’s compare the the congruence relation with the modulus operator:
  • \(a \equiv b \pmod{m}\) is a logical statement. It tells us that \(a\) and \(b\) are related, that is, the statement \(m \divides (b-a)\) is true.
  • \(a \modulus b\) is a mathematical operation. The result is a number.
The difference is subtle but important.

Definition 3.1.12. Congruence Classes.

If \(a\) is an integer and \(m\) is a positive integer, we define the congruence class of \(a\) modulo \(m\) to be the set of all integers congruent to \(a\) modulo \(m\text{.}\)
\begin{equation*} \left[ a \right]_m = \left\{ b \mid b \equiv a\pmod{m} \right\} \end{equation*}

Example 3.1.13.

What congruence class is indicated by the set:
  1. \(\displaystyle \left\{\dots, -6, -1, 4, 9, 14, \dots\right\}\)
  2. \(\displaystyle \left\{\dots, -13, 20, 53, 86, \dots \right\}\)
Video / Answer.

Example 3.1.14.

Find all congruence classes modulo 5.
Hint.
To what numbers is 0 congruent modulo 5? Is 1? 2? 3? 4? 5? 6? 7?... Have we covered everything?
Solution.
There are a total of five congruence classes modulo 5:
  1. \(\displaystyle [0]_5 = \{ \dots, -5, 0, 5, 10, \dots \}\)
  2. \(\displaystyle [1]_5 = \{ \dots, -4, 1, 6, 11, \dots \}\)
  3. \(\displaystyle [2]_5 = \{ \dots, -3, 2, 7, 12, \dots \}\)
  4. \(\displaystyle [3]_5 = \{ \dots, -2, 3, 8, 13, \dots \}\)
  5. \(\displaystyle [4]_5 = \{ \dots, -1, 4, 9, 14, \dots \}\)
In general, there will always be \(m\) distinct congruence classes modulo \(m\text{.}\)
We call the collection of the operations of addition and multiplication modulo \(m\) modular arithmetic.

Note 3.1.17.

For modular arithmetic, we have addition and multiplication. Subtraction is done via additive inverses, but division is not a defined operation! We’ll discuss multiplicative inverses in section 3.4.

Exercises Exercises

1.

Show that if \(a \equiv b\pmod{m}\text{,}\) then \(b \equiv a \pmod{m}\)
Hint.
If \(m \divides (b-a)\text{,}\) how can we write that \(m \divides (a-b)\text{?}\)

2.

Show that if \(a, b, \and c\) are integers with \(a\not=0 \and c \not= 0\) such that \(ac \divides bc\) then \(a\divides b\text{.}\)
Solution.
Proof.
Assume that \(a, b, c\) are integers with \(a \ne 0\) and \(c\ne 0\) such that \(ac \divides bc\text{.}\) Then there exists an integer \(m\) such \(bc = acm\)
Since \(c \ne 0\text{,}\) we can divide both sides of the equation by \(c\text{,}\) yielding the equality \(b = am\text{.}\) Thus \(a \divides b\text{.}\)

3.

Use the division algorithm to write the following divisions as \(n = dq + r\) with the variables defined in the theorem:
  1. 17 is divided by 9
  2. 1234 is divided by 23
  3. 0 is divided by 13
  4. 8 is divided by 1
Solution.
  1. \(\displaystyle 17 = 9\cdot 1 + 8 \)
  2. \(\displaystyle 1234 = 23 \cdot 53 + 15\)
  3. \(\displaystyle 0 = 13 \cdot 0 + 0\)
  4. \(\displaystyle 8 = 1 \cdot 8 + 0\)

4.

Determine whether the following integers are congruent to 3 modulo 7:
  1. 37
  2. 66
  3. -17
  4. -67
  5. 80
Solution.
  1. Since \(37 - 3 = 34\) is not divisible by 7, we conclude \(37 \not\equiv 3\pmod 7\)
  2. Since \(66 - 3 = 63\) is divisible by 7, we conclude \(66 \equiv 3\pmod 7\)
  3. Since \(-17 - 3 = -20\) is not divisible by 7, we conclude \(-17 \not \equiv 3\pmod 7\)
  4. Since \(-67 - 3 = -70\) is divisible by 7, we conclude \(-67 \equiv 3\pmod 7\)
  5. Since \(80 - 3 = 77\) is divisible by 7, we conclude \(80 \equiv 3\pmod 7\)

5.

List all integers between -100 and 100 that are congruent to -1 modulo 25
Solution.
These numbers are \(-1, -26, -51, -76, 24, 49, 74, 99,\) all numbers that are of the form \(-1 + 25 \cdot k\) for integers \(k\text{.}\)

6.

Suppose that \(a \and b\) are integers, \(a \equiv 4 \pmod{13}\) and \(b \equiv 9\pmod{13}\text{.}\) Find the integer \(c\) with \(0 \le c \le 12\) such that:
  1. \(\displaystyle c \equiv 9a \pmod{13} \)
  2. \(\displaystyle c \equiv 11b \pmod{13} \)
  3. \(\displaystyle c \equiv a+b \pmod{13} \)
  4. \(\displaystyle c \equiv a^2 + b^2 \pmod{13} \)
  5. \(\displaystyle c \equiv a^2 - b^2 \pmod{13} \)
Solution.
  1. 10
  2. 8
  3. 0
  4. 6
  5. 0

7.

Find counterexamples to the following statements:
  1. If \(ac \equiv bc \pmod m\) where \(a, b, c, m \in \Z\) with \(m \ge 2\text{,}\) then \(a \equiv b \pmod m\text{.}\)
  2. If \(a \equiv b \pmod m\) and \(c \equiv d \pmod m\) where \(a, b, c, m \in \Z\) with \(m \ge 2\text{,}\) then \(a^c \equiv b^d \pmod m\text{.}\)
The first part of this exercise should convince you: you cannot “divide” both sides by \(c\) in modular arithmetic!
Solution.
  1. One possible counterexample is \(a = 2, b=4, c=4, and m=6\text{.}\) Certainly \(2\cdot 3 \equiv 4 \cdot 3 \pmod 6\) but \(2 \not \equiv 4 \pmod 6\text{.}\)
  2. One possible counterexample here is \(a = 2, b=7, c=7, b=2, m=5\text{.}\) Then we can see \(2\equiv 7\pmod 5\) satisfies both parts of the hypothesis, but \(2^7 \equiv 3 \pmod 5\) while \(7^2 \equiv 4 \pmod 5\text{.}\)
<Prev^TopNext>