The Division Algorithm and Congruence

Section 3.5 The Division Algorithm and Congruence

Beginning Activity Beginning Activity 1: Quotients and Remainders
A4 US

1.

Let $a = 27$ and $b = 4 .$ We will now determine several pairs of integers $q$ and $r$ so that $27 = 4 q + r .$ For example, if $q = 2$ and $r = 19,$ we obtain $4 \cdot 2 + 19 = 27 .$ The following table is set up for various values of $q .$ For each $q,$ determine the value of $r$ so that $4 q + r = 27 .$

$q$	1	2	3	4	5	6	7	8	9	10
$r$		19						$- 5$
$4 q + r$	27	27	27	27	27	27	27	27	27	27

🔗

2.

What is the smallest positive value for $r$ that you obtained in your examples from Exercise 1?

🔗

Division is not considered an operation on the set of integers since the quotient of two integers need not be an integer. However, we have all divided one integer by another and obtained a quotient and a remainder. For example, if we divide 113 by 5, we obtain a quotient of 22 and a remainder of 3. We can write this as

\frac{113}{5} = 22 + \frac{3}{5} .

If we multiply both sides of this equation by 5 and then use the distributive property to “clear the parentheses,” we obtain

\begin{aligned} 5 \cdot \frac{113}{5} & = 5 (22 + \frac{3}{5}) \\ 113 & = 5 \cdot 22 + 3 \end{aligned}

🔗

This is the equation that we use when working in the integers since it involves only multiplication and addition of integers.

🔗

3.

What are the quotient and the remainder when we divide 27 by 4? How is this related to your answer for Exercise 2?

🔗

4.

Repeat Exercise 1 using $a = - 17$ and $b = 5 .$ So the object is to find integers $q$ and $r$ so that $- 17 = 5 q + r .$ Do this by completing the following table.

$q$	$- 7$	$- 6$	$- 5$	$- 4$	$- 3$	$- 2$	$- 1$
$r$	$18$					$- 7$
$5 q + r$	$- 17$	$- 17$	$- 17$	$- 17$	$- 17$	$- 17$	$- 17$

🔗

5.

The convention we will follow is that the remainder will be the smallest positive integer $r$ for which $- 17 = 5 q + r$ and the quotient will be the corresponding value of $q .$ Using this convention, what is the quotient and what is the remainder when $- 17$ is divided by 5?

🔗

Beginning Activity Beginning Activity 2: Some Work with Congruence Modulo $n$
A4 US

🔗

1.

Let $n$ be a natural number and let $a$ and $b$ be integers.

🔗

(a)

Write the definition of “ $a$ is congruent to $b$ modulo $n,$ ” which is written $a \equiv b (\mod n) .$

🔗

(b)

Use the definition of “divides” to complete the following:

When we write $a \equiv b (\mod n),$ we may conclude that there exists an integer $k$ such that ….

🔗

We will now explore what happens when we multiply several pairs of integers where the first one is congruent to 3 modulo 6 and the second is congruent to 5 modulo 6. We can use set builder notation and the roster method to specify the set

A

of all integers that are congruent to 3 modulo 6 as follows:

A = {a \in Z ∣ a \equiv 3 (\mod 6)} = {\dots, - 15, - 9, - 3, 3, 9, 15, 21, \dots} .

🔗

2.

Use the roster method to specify the set $B$ of all integers that are congruent to 5 modulo 6.

B = {b \in Z ∣ b \equiv 5 (\mod 6)} = \dots .

🔗

Notice that

15 \in A

and

11 \in B

and that

15 + 11 = 26 .

Also notice that

26 \equiv 2 (\mod 6)

and that 2 is the smallest positive integer that is congruent to

26 (\mod 6) .

🔗

3.

Now choose at least four other pairs of integers $a$ and $b$ where $a \in A$ and $b \in B .$ For each pair, calculate $(a + b)$ and then determine the smallest positive integer $r$ for which $(a + b) \equiv r (\mod 6) .$

Note: The integer $r$ will satisfy the inequalities $0 \leq r < 6 .$

🔗

4.

Prove that for all integers $a$ and $b,$ if $a \equiv 3 (\mod 6)$ and $b \equiv 5 (\mod 6),$ then $(a + b) \equiv 2 (\mod 6) .$

🔗

Subsection The Division Algorithm

🔗

Beginning Activity 1 was an introduction to a mathematical result known as the Division Algorithm. One of the purposes of this beginning activity was to illustrate that we have already with this result, perhaps without knowing its name. For example, when we divide 337 by 6, we often write

\frac{337}{6} = 56 + \frac{1}{6} .

🔗

When we multiply both sides of this equation by 6, we get

337 = 6 \cdot 56 + 1 .

🔗

When we are working within the system of integers, the second equation is preferred over the first since the second one uses only integers and the operations of addition and multiplication, and the integers are closed under addition and multiplication. Following is a complete statement of the Division Algorithm.

🔗

The Division Algorithm.

For all integers $a$ and $b$ with $b > 0,$ there exist unique integers $q$ and $r$ such that

a = b q + r and 0 \leq r < b .

🔗

Some Comments about the Division Algorithm.

The Division Algorithm can be proven, but we have not yet studied the methods that are usually used to do so. In this text, we will treat the Division Algorithm as an axiom of the integers. The work in Beginning Activity 1 provides some rationale that this is a reasonable axiom.
The statement of the Division Algorithm contains the new phrase, “there exist unique integers $q$ and $r$ such that $\dots .$ ” This means that there is only one pair of integers $q$ and $r$ that satisfy both the conditions $a = b q + r$ and $0 \leq r < b .$ As we saw in Beginning Activity 1, there are several different ways to write the integer $a$ in the form $a = b q + r .$ However, there is only one way to do this and satisfy the additional condition that $0 \leq r < b .$
In light of the previous comment, when we speak of the quotient and the remainder when we “divide an integer $a$ by the positive integer $b,$ ” we will always mean the quotient $(q)$ and the remainder $(r)$ guaranteed by the Division Algorithm. So the remainder $r$ is the least nonnegative integer such that there exists an integer (quotient) $q$ with $a = b q + r .$
If $a < 0,$ then we must be careful when writing the result of the Division Algorithm. For example, in Exercise 4 and Exercise 5 of Beginning Activity 1, with $a = - 17$ and $b = 5,$ we obtained $- 17 = 5 \cdot (- 4) + 3,$ and so the quotient is $- 4$ and the remainder is 3. Notice that this is different than the result from a calculator, which would be $\frac{- 17}{5} = - 3.4 .$ But this means

$\frac{- 17}{5} = - (3 + \frac{4}{10}) = - 3 - \frac{2}{5} .$

If we multiply both sides of this equation by 5, we obtain

$- 17 = 5 (- 3) + (- 2) .$

This is not the result guaranteed by the Division Algorithm since the value of $- 2$ does not satisfy the result of being greater than or equal to 0 and less than 5.
One way to look at the Division Algorithm is that the integer $a$ is either going to be a multiple of $b,$ or it will lie between two multiples of $b .$ Suppose that $a$ is not a multiple of $b$ and that it lies between the multiples $b \cdot q$ and $b (q + 1),$ where $q$ is some integer. This is shown on the number line in Figure 3.31.

Figure 3.31. Remainder for the Division Algorithm
If $r$ represents the distance from $b \cdot q$ to $a,$ then

$\begin{aligned} r & = a - b \cdot q, or \\ a & = b \cdot q + r . \end{aligned}$

From the diagram, also notice that $r$ is less than the distance between $b \cdot q$ and $b (q + 1) .$ Algebraically, this distance is

$\begin{aligned} b (q + 1) - b \cdot q & = b \cdot q + b - b \cdot q \\ = b . \end{aligned}$

Thus, in the case where $a$ is not a multiple of $b,$ we get $0 < r < b .$
We have been implicitly using the fact that an integer cannot be both even and odd. There are several ways to understand this fact, but one way is through the Division Algorithm. When we classify an integer as even or odd, we are doing so on the basis of the remainder (according to the Division Algorithm) when the integer is “divided” by 2. If $a \in Z,$ then by the Division Algorithm there exist unique integers $q$ and $r$ such that

$a = 2 q + r and 0 \leq r < 2 .$

This means that the remainder, $r,$ can only be zero or one (and not both). When $r = 0,$ the integer is even, and when $r = 1,$ the integer is odd.

🔗

Progress Check 3.32. Using the Division Algorithm.

🔗

(a)

What are the possible remainders (according to the Division Algorithm) when an integer is

🔗

(i)

Divided by 4?

Solution.

The possible remainders are 0, 1, 2, and 3.

🔗

(ii)

Divided by 9?

Solution.

The possible remainders are 0, 1, 2, 3, 4, 5, 6, 7, and 8.

🔗

(b)

For each of the following, find the quotient and remainder (guaranteed by the Division Algorithm) and then summarize the results by writing an equation of the form $a = b q + r,$ where $0 \leq r < b .$

🔗

(i)

When 17 is divided by 3.

Solution.

$17 = 5 \cdot 3 + 2$

🔗

(ii)

When $- 17$ is divided by 3.

Solution.

$- 17 = (- 6) \cdot 3 + 1$

🔗

(iii)

When 73 is divded by 7.

Solution.

$73 = 10 \cdot 7 + 3$

🔗

(iv)

When $- 73$ is divided by 7.

Solution.

$- 73 = (- 11) \cdot 7 + 4$

🔗

(v)

When 436 is divided by 27.

Solution.

$436 = 16 \cdot 27 + 4$

🔗

(vi)

When 539 is divided by 110.

Solution.

$539 = 4 \cdot 110 + 99$

🔗

Subsection Using Cases Determined by the Division Algorithm

🔗

The Division Algorithm can sometimes be used to construct cases that can be used to prove a statement that is true for all integers. We have done this when we divided the integers into the even integers and the odd integers since even integers have a remainder of 0 when divided by 2 and odd integers have a remainder of 1 when divided by 2.

🔗

Sometimes it is more useful to divide the integer

a

by an integer other than 2. For example, if

a

is divided by 3, there are three possible remainders: 0, 1, and 2. If

a

is divided by 4, there are four possible remainders: 0, 1, 2, and 3. The remainders form the basis for the cases.

🔗

If the hypothesis of a proposition is that “

n

is an integer,” then we can use the Division Algorithm to claim that there are unique integers

q

and

r

such that

n = 3 q + r and 0 \leq r < 3 .

🔗

We can then divide the proof into the following three cases: (1)

r = 0;

(2)

r = 1;

and (3)

r = 2 .

This is done in Proposition 3.33.

🔗

Proposition 3.33.

If $n$ is an integer, then 3 divides $n^{3} - n .$

🔗

Proof.

Let $n$ be an integer. We will show that 3 divides $n^{3} - n$ by examining the three cases for the remainder when $n$ is divided by 3. By the Division Algorithm, there exist unique integers $q$ and $r$ such that

n = 3 q + r, and 0 \leq r < 3 .

This means that we can consider the following three cases: (1) $r = 0;$ (2) $r = 1;$ and (3) $r = 2 .$

In the case where $r = 0,$ we have $n = 3 q .$ By substituting this into the expression $n^{3} - n,$ we get

\begin{aligned} n^{3} - n & = {(3 q)}^{3} - (3 q) \\ = 27 q^{3} - 3 q \\ = 3 (9 q^{3} - q) . \end{aligned}

Since $(9 q^{3} - q)$ is an integer, the last equation proves that $3 ∣ (n^{3} - n) .$

In the second case, $r = 1$ and $n = 3 q + 1 .$ When we substitute this into $(n^{3} - n),$ we obtain

\begin{aligned} n^{3} - n & = {(3 q + 1)}^{3} - (3 q + 1) \\ = (27 q^{3} + 27 q^{2} + 9 q + 1) - (3 q + 1) \\ = 27 q^{3} + 27 q^{2} + 6 q \\ = 3 (9 q^{3} + 9 q^{2} + 2 q) . \end{aligned}

Since $(9 q^{3} + 9 q^{2} + 2 q)$ is an integer, the last equation proves that $3 ∣ (n^{3} - n) .$

The last case is when $r = 2 .$ The details for this case are part of Exercise 1. Once this case is completed, we will have proved that 3 divides $n^{3} - n$ in all three cases. Hence, we may conclude that if $n$ is an integer, then 3 divides $n^{3} - n .$

🔗

Subsection Properties of Congruence

🔗

Most of the work we have done so far has involved using definitions to help prove results. We will continue to prove some results but we will now prove some theorems about congruence (Theorem 3.34 and Theorem 3.36) that we will then use to help prove other results.

🔗

Let

n \in N .

Recall that if

a

and

b

are integers, then we say that

a

is congruent to

b

modulo

n

provided that

n

divides

a - b,

and we write

a \equiv b (\mod n) .

(See Section 3.1.) We are now going to prove some properties of congruence that are direct consequences of the definition. One of these properties was suggested by the work in Beginning Activity 2 and is Item 1 of the next theorem.

🔗

Theorem 3.34. Properties of Congruence Modulo.

Let $n$ be a natural number and let $a, b, c, and d$ be integers. If $a \equiv b (\mod n)$ and $c \equiv d (\mod n),$ then

$(a + c) \equiv (b + d) (\mod n) .$
$a c \equiv b d (\mod n) .$
For each $m \in N,$ $a^{m} \equiv b^{m} (\mod n) .$

🔗

Proof.

We will prove Item 2 and Item 3. The proof of Item 1 is Progress Check 3.35. Let $n$ be a natural number and let $a, b, c, and d$ be integers. Assume that $a \equiv b (\mod n)$ and that $c \equiv d (\mod n) .$ This means that $n$ divides $a - b$ and that $n$ divides $c - d .$ Hence, there exist integers $k$ and $q$ such that $a - b = n k$ and $c - d = n q .$ We can then write $a = b + n k$ and $c = d + n q$ and obtain

\begin{aligned} a c & (b + n k) (d + n q) \\ = b d + b n q + d n k + n^{2} k q \\ = b d + n (b q + d k + n k q) . \end{aligned}

By subtracting $b d$ from both sides of the last equation, we see that

a c - b d = n (b q + d k + n k q) .

Since $b q + d k + n k q$ is an integer, this proves that $n ∣ (a c - b d),$ and hence we can conclude that $a c \equiv b d (\mod n) .$ This completes the proof of Item 2.

Item 2 basically means that if we have two congruences, we can multiply the corresponding sides of these congruences to obtain another congruence. We have assumed that $a \equiv b (\mod n)$ and so we write this twice as follows:

\begin{aligned} a & \equiv b (\mod n), and \\ a & \equiv b (\mod n) . \end{aligned}

If we now use the result in Item 2 and multiply the corresponding sides of these two congruences, we obtain $a^{2} \equiv b^{2} (\mod n) .$ We can then use this congruence and the congruence $a \equiv b (\mod n)$ and the result in Item 2 to conclude that

a^{2} \cdot a \equiv b^{2} \cdot b (\mod n),

or that $a^{3} \equiv b^{3} (\mod n) .$ We can say that we can continue with this process to prove Item 3, but this is not considered to be a formal proof of this result. To construct a formal proof for this, we could use a proof by mathematical induction. This will be studied in Chapter 4. See Exercise 13 in Section 4.1.

🔗

Progress Check 3.35. Proving Item 1 of Theorem 3.34.

Prove Item 1 of Theorem 3.34.

Solution.

🔗

Proof.

Let $n$ be a natural number and let $a, b, c, and d$ be integers. We assume that $a \equiv b (\mod n)$ and $c \equiv d (\mod n)$ and will prove that $(a + c) \equiv (b + d) (\mod n) .$ Since $a \equiv b (\mod n)$ and $c \equiv d (\mod n),$ $n$ divides $(a - b)$ and $(c - d)$ and so there exist integers $k$ and $q$ such that $a - b = n k$ and $c - d = n q .$ We can then write $a = b + n k$ and $c = d + n q$ and obtain

\begin{aligned} a + c & = (b + n k) + (d + n q) \\ = (b + d) + n (k + q) \end{aligned}

By subtracting $(b + d)$ from both sides of the last equation, we see that

(a + c) - (b + d) = n (k + q) .

Since $(k + q)$ is an integer, this proves that $n$ divides $(a + c) - (b + d),$ and hence, we can conclude that $(a + c) \equiv (b + d) (\mod n) .$

🔗

Exercise 11 in Section 3.1 gave three important properties of congruence modulo

n .

Because of their importance, these properties are stated and proved in Theorem 3.36. Please remember that textbook proofs are usually written in final form of “reporting the news.” Before reading these proofs, it might be instructive to first try to construct a know-show table for each proof.

🔗

Theorem 3.36. Properties of Congruence Modulo $n$ .

Let $n \in N,$ and let $a,$ $b,$ and $c$ be integers.

For every integer $a,$ $a \equiv a (\mod n) .$

This is called the reflexive property of congruence modulo $n .$
If $a \equiv b (\mod n),$ then $b \equiv a (\mod n) .$

This is called the symmetric property of congruence modulo $n .$
If $a \equiv b (\mod n)$ and $b \equiv c (\mod n),$ then $a \equiv c (\mod n) .$

This is called the transitive property of congruence modulo $n .$

🔗

Proof.

We will prove the reflexive property and the transitive property. The proof of the symmetric property is Exercise 3.

Let $n \in N,$ and let $a \in Z .$ We will show that $a \equiv a (\mod n) .$ Notice that

a - a = 0 = n \cdot 0 .

This proves that $n$ divides $(a - a)$ and hence, by the definition of congruence modulo $n,$ we have proven that $a \equiv a (\mod n) .$

To prove the transitive property, we let $n \in N,$ and let $a,$ $b,$ and $c$ be integers. We assume that $a \equiv b (\mod n)$ and that $b \equiv c (\mod n) .$ We will use the definition of congruence modulo $n$ to prove that $a \equiv c (\mod n) .$ Since $a \equiv b (\mod n)$ and $b \equiv c (\mod n),$ we know that $n ∣ (a - b)$ and $n ∣ (b - c) .$ Hence, there exist integers $k$ and $q$ such that

\begin{aligned} a - b & = n k \\ b - c & = n q . \end{aligned}

By adding the corresponding sides of these two equations, we obtain

(a - b) + (b - c) = n k + n q .

If we simplify the left side of the last equation and factor the right side, we get

a - c = n (k + q) .

By the closure property of the integers, $(k + q) \in Z,$ and so this equation proves that $n ∣ (a - c)$ and hence that $a \equiv c (\mod n) .$ This completes the proof of the transitive property of congruence modulo $n .$

🔗

Subsection Using Cases Based on Congruence Modulo $n$

🔗

Notice that the set of all integers that are congruent to 2 modulo 7 is

{n \in Z ∣ n \equiv 2 (\mod 7)} = {\dots, - 19, - 12, - 5, 2, 9, 16, 23, \dots} .

🔗

If we divide any integer in this set by 7 and write the result according to the Division Algorithm, we will get a remainder of 2. For example,

\begin{aligned} 2 & = 7 \cdot 0 + 2 & - 5 & = 7 (- 1) + 2 \\ 9 & = 7 \cdot 1 + 2 & - 12 & = 7 (- 2) + 2 \\ 16 & = 7 \cdot 2 + 2 & - 19 & = 7 (- 3) + 2 \\ 23 & = 7 \cdot 3 + 2. \end{aligned}

🔗

Is this a coincidence or is this always true? Let's look at the general case. For this, let

n

be a natural number and let

a \in Z .

By the Division Algorithm, there exist unique integers

q

and

r

such that

a = n q + r and 0 \leq r < n .

🔗

By subtracting

r

from both sides of the equation

a = n q + r,

we obtain

a - r = n q .

🔗

But this implies that

n ∣ (a - r)

and hence that

a \equiv r (\mod n) .

We have proven the following result.

🔗

Theorem 3.37.

Let $n \in N$ and let $a \in Z .$ If $a = n q + r and 0 \leq r < n$ for some integers $q$ and $r,$ then $a \equiv r (\mod n) .$

🔗

This theorem says that an integer is congruent (mod

n

) to its remainder when it is divided by

n .

Since this remainder is unique and since the only possible remainders for division by

n

are

0, 1, 2, \dots, n - 1,

we can state the following result.

🔗

Corollary 3.38.

If $n \in N,$ then each integer is congruent, modulo $n,$ to precisely one of the integers $0, 1, 2, \dots, n - 1 .$ That is, for each integer $a,$ there exists a unique integer $r$ such that

a \equiv r (\mod n) and 0 \leq r < n .

🔗

Corollary 3.38 can be used to set up cases for an integer in a proof. If

n \in N

and

a \in Z,

then we can consider

n

cases for

a .

The integer

a

could be congruent to

0, 1, 2, \dots, or n - 1

modulo

n .

For example, if we assume that 5 does not divide an integer

a,

then we know

a

is not congruent to 0 modulo 5, and hence, that

a

must be congruent to 1, 2, 3, or 4 modulo 5. We can use these as 4 cases within a proof. For example, suppose we wish to determine the values of

a^{2}

modulo 5 for integers that are not congruent to 0 modulo 5. We begin by squaring some integers that are not congruent to 0 modulo 5. We see that

\begin{aligned} 1^{2} & = 1 & and & 1 & \equiv 1 (\mod 5) . \\ 3^{2} & = 9 & and & 9 & \equiv 4 (\mod 5) . \\ 6^{2} & = 36 & and & 36 & \equiv 1 (\mod 5) . \\ 8^{2} & = 64 & and & 64 & \equiv 4 (\mod 5) . \\ 9^{2} & = 81 & and & 81 & \equiv 1 (\mod 5) . \end{aligned}

🔗

These explorations indicate that the following proposition is true and we will now outline a method to prove it.

🔗

Proposition 3.39.

For each integer $a,$ if $a ≢ 0 (\mod 5),$ then $a^{2} \equiv 1 (\mod 5)$ or $a^{2} \equiv 4 (\mod 5) .$

🔗

Proof.

We will prove this proposition using cases for $a$ based on congruence modulo 5. In doing so, we will use the results in Theorem 3.34 and Theorem 3.36. Because the hypothesis is $a ≢ 0 (\mod 5),$ we can use four cases, which are: (1) $a \equiv 1 (\mod 5),$ (2) $a \equiv 2 (\mod 5),$ (3) $a \equiv 3 (\mod 5),$ and (4) $a \equiv 4 (\mod 5) .$ Following are proofs for the first and fourth cases.

Case 1. $(a \equiv 1 (\mod 5)) .$ In this case, we use Theorem 3.34 to conclude that

a^{2} \equiv 1^{2} (\mod 5) or a^{2} \equiv 1 (\mod 5) .

This proves that if $a \equiv 1 (\mod 5),$ then $a^{2} \equiv 1 (\mod 5) .$

Case 4. $(a \equiv 4 (\mod 5)) .$ In this case, we use Theorem 3.34 to conclude that

a^{2} \equiv 1^{2} (\mod 5) or a^{2} \equiv 16 (\mod 5) .

We also know that $16 \equiv 1 (\mod 5) .$ So we have $a^{2} \equiv 16 (\mod 5)$ and $16 \equiv 1 (\mod 5),$ and we can now use the transitive property of congruence (Theorem 3.36) to conclude that $a^{2} \equiv 1 (\mod 5) .$ This proves that if $a \equiv 4 (\mod 5),$ then $a^{2} \equiv 1 (\mod 5) .$

🔗

Progress Check 3.40. Using Properties of Congruence.

Complete a proof of Proposition 3.39 by completing proofs for the other two cases.

Note: It is possible to prove Proposition 3.39 using only the definition of congruence instead of using the properties that we have proved about congruence. However, such a proof would involve a good deal of algebra. One of the advantages of using the properties is that it avoids the use of complicated algebra in which it is easy to make mistakes.

Solution.

Case 2. $(a \equiv 2 (\mod 5)) .$ In this case, we use Theorem 3.34 to conclude that

a^{2} \equiv 2^{2} (\mod 5) or a^{2} \equiv 4 (\mod 5) .

This proves that if $a \equiv 2 (\mod 5),$ then $a^{2} \equiv 4 (\mod 5) .$

Case 3. $(a \equiv 3 (\mod 5)) .$ In this case, we use Theorem 3.34 to conclude that

a^{2} \equiv 3^{2} (\mod 5) or a^{2} \equiv 9 (\mod 5) .

We also know that $9 \equiv 4 (\mod 5) .$ So we have $a^{2} \equiv 9 (\mod 5)$ and $9 \equiv 4 (\mod 5),$ and we can now use the transitive property of congruence (Theorem 3.36) to conclude that $a^{2} \equiv 4 (\mod 5) .$ This proves that if $a \equiv 3 (\mod 5),$ then $a^{2} \equiv 4 (\mod 5) .$

🔗

In the proof of Proposition 3.39, we used four cases. Sometimes it may seem a bit overwhelming when confronted with a proof that requires several cases. For example, if we want to prove something about some integers modulo 6, we may have to use six cases. However, there are sometimes additional assumptions (or conclusions) that can help reduce the number of cases that must be considered. This will be illustrated in the next progress check.

🔗

Progress Check 3.41. Using Cases Modulo 6.

Suppose we want to determine the possible values for $a^{2}$ modulo 6 for odd integers that are not multiples of 3. Before beginning to use congruence arithmetic (as in the proof of Proposition 3.39) in each of the possible six cases, we can show that some of the cases are not possible under these assumptions. (In some sense, we use a short proof by contradiction for these cases.) So assume that $a$ is an odd integer. Then:

If $a \equiv 0 (\mod 6),$ then there exists an integer $k$ such that $a = 6 k .$ But then $a = 2 (3 k)$ and hence, $a$ is even. Since we assumed that $a$ is odd, this case is not possible.
If $a \equiv 2 (\mod 6),$ then there exists an integer $k$ such that $a = 6 k + 2 .$ But then $a = 2 (3 k + 1)$ and hence, $a$ is even. Since we assumed that $a$ is odd, this case is not possible.

🔗

(a)

Prove that if $a$ is an odd integer, then $a$ cannot be congruent to 4 modulo 6.

🔗

(b)

Prove that if $a$ is an integer and 3 does not divide $a,$ then $a$ cannot be congruent to 3 modulo 6.

🔗

(c)

So if $a$ is an odd integer that is not a multiple of 3, then $a$ must be congruent to 1 or 5 modulo 6. Use these two cases to prove the following proposition:

🔗

Proposition 3.42.

For each integer $a,$ if $a$ is an odd integer that is not multiple of 3, then $a^{2} \equiv 1 (\mod 6) .$

🔗

Exercises Exercises

🔗

1.

Complete the details for the proof of Case 3 of Proposition 3.33.

🔗

2.

Complete the following.

🔗

(a)

Use cases based on congruence modulo 3 and properties of congruence to prove that for each integer $n,$ $n^{3} \equiv n (\mod 3) .$

Answer.

The first case is when $n \equiv 0 (\mod 3) .$ We can then use Theorem 3.34 to conclude that $n^{3} \equiv 0^{3} (\mod 3)$ or that $n^{3} \equiv 0 (\mod 3) .$ So in this case, $n^{3} \equiv n (\mod 3) .$

For the second case, $n \equiv 1 (\mod 3) .$ We can then use Theorem 3.34 to conclude that $n^{3} \equiv 1^{3} (\mod 3)$ or that $n^{3} \equiv 1 (\mod 3) .$ So in this case, $n^{3} \equiv n (\mod 3) .$

The last case is when $n \equiv 2 (\mod 3) .$ We then get $n^{3} \equiv 2^{3} (\mod 3)$ or $n^{3} \equiv 8 (\mod 3) .$ Since $8 \equiv 2 (\mod 3),$ we can use the transitive property to conclude that $n^{3} \equiv 2 (\mod 3),$ and so $n^{3} \equiv n (\mod 3) .$ Since we have proved it in all three cases, we conclude that for each integer $n,$ $n^{3} \equiv n (\mod 3) .$

🔗

(b)

Explain why the result in Task 2.a proves that for each integer $n,$ 3 divides $(n^{3} - n) .$ Compare this to the proof of the same result in Proposition 3.33.

Answer.

Since $n^{3} \equiv n (\mod 3),$ we use the definition of congruence to conclude that 3 divides $(n^{3} - n) .$

🔗

3.

Prove the symmetric property of congruence stated in Theorem 3.36.

Answer.

For $a, b \in Z,$ you need to prove that if $a \equiv b (\mod n),$ then $b \equiv a (\mod n) .$ So let $a, b \in Z$ and assume that $a \equiv b (\mod n) .$ So $n ∣ (a - b)$ and there exists an integer $k$ such that $a - b = n k .$ Then, $b - a = n (- k)$ and $b \equiv a (\mod n) .$

🔗

4.

Consider the following proposition: For each integer $a,$ if 3 divides $a^{2},$ then 3 divides $a .$

🔗

(a)

Write the contrapositive of this proposition.

Answer.

The contrapositive is: For each integer $a,$ if 3 does not divide $a,$ then 3 divides $a^{2} .$

🔗

(b)

Prove the proposition by proving its contrapositive.

Hint.

Consider using cases based on the Division Algorithm using the remainder for “division by 3.” There will be two cases.

Answer.

To prove the contrapositive, let $a \in Z$ and assume that 3 does not divide $a .$ So using the Division Algorithm, we can consider two cases: (1) There exists a unique integer $q$ such that $a = 3 q + 1 .$ (2) There exists a unique integer $q$ such that $a = 3 q + 2 .$ For the first case, show that $a^{2} = 3 (3 q^{2} + 2 q) + 1 .$ For the second case, show that $a^{2} = 3 (3 q^{2} + 4 q + 1) + 1 .$ Since the Division Algorithm states that the remainder is unique, this shows that in both cases, the remainder is 1 and so 3 does not divide $a^{2} .$

🔗

5.

Complete the following.

🔗

(a)

Let $n \in N$ and let $a \in Z .$ Explain why $n$ divides $a$ if and only if $a \equiv 0 (\mod n) .$

Answer.

$a \equiv 0 (\mod n)$ if and only if $n ∣ (a - 0) .$

🔗

(b)

Let $a \in Z .$ Explain why if $a ≢ 0 (\mod 3),$ then $a \equiv 1 (\mod 3)$ or $a \equiv 2 (\mod 3) .$

Answer.

Let $a \in Z .$ Corollary 3.38 tell us that if $a ≢ 0 (\mod 3),$ then $a \equiv 1 (\mod 3)$ or $a \equiv 2 (\mod 3) .$

🔗

(c)

Is the following proposition true or false? Justify your conclusion.

For each $a \in Z,$ if $a ≢ 0 (\mod 3),$ then $a^{2} \equiv 1 (\mod 3) .$

Answer.

Task 5.b tells us we can use a proof by cases using the following two cases: (1) $a \equiv 1 (\mod 3);$ (2) $a \equiv 2 (\mod 3) .$ So, if $a \equiv 1 (\mod 3),$ then by Theorem 3.34, $a \cdot a \equiv 1 \cdot 1 (\mod 3),$ and hence, $a^{2} \equiv 1 (\mod 3) .$ If $a \equiv 2 (\mod 3),$ then by Theorem 3.34, $a \cdot a \equiv 2 \cdot 2 (\mod 3),$ and hence, $a^{2} \equiv 4 (\mod 3) .$ Since $4 \equiv 1 (\mod 3),$ this implies that $a^{2} \equiv 1 (\mod 3) .$

🔗

6.

Prove the following proposition by proving its contrapositive.

For all integers $a$ and $b,$ if $a b \equiv 0 (\mod 3),$ then $a \equiv 0 (\mod 3)$ or $b \equiv 0 (\mod 3) .$

Hint.

Use case analysis. There are several cases.

Answer.

The contrapositive is: Let $a$ and $b$ be integers. If $a ≢ 0 (\mod 3)$ and $b ≢ 0 (\mod 3),$ then $a b ≢ 0 (\mod 3) .$ Using Task 5.b, we can use the following four cases:

$a \equiv 1 (\mod 3)$ and $b \equiv 1 (\mod 3);$
$a \equiv 1 (\mod 3)$ and $b \equiv 2 (\mod 3);$
$a \equiv 2 (\mod 3)$ and $b \equiv 1 (\mod 3);$
$a \equiv 2 (\mod 3)$ and $b \equiv 2 (\mod 3) .$

In all four cases, we use Theorem 3.34 to conclude that $a b ≢ 0 (\mod 3) .$ For example, for the third case, we see that $a b \equiv 2 \cdot 1 (\mod 3) .$ That is, $a b \equiv 2 (\mod 3) .$

🔗

7.

Complete the following.

🔗

(a)

Explain why the following proposition is equivalent to the proposition in Exercise 6.

For all integers $a$ and $b,$ if $3 ∣ a b$ , then $3 ∣ a$ or $3 ∣ b .$

Answer.

This follows from Exercise 5 and the fact that $3 ∣ k$ if and only if $k \equiv 0 (\mod 3) .$

🔗

(b)

Prove that for each integer $a,$ if 3 divides $a^{2},$ then 3 divides $a .$

Answer.

This follows directly from Task 7.a using $a = b .$

🔗

8.

Complete the following.

🔗

(a)

Prove that the real number $\sqrt{3}$ is an irrational number. That is, prove that

If $r$ is a positive real number such that $r^{2} = 3,$ then $r$ is irrational.

Hint.

Use a proof similar to the proof of Theorem 3.24. The result of Exercise 7 may be helpful.

🔗

(b)

Prove that the real number $\sqrt{12}$ is an irrational number.

🔗

9.

Prove that for each natural number $n,$ $\sqrt{3 n + 2}$ is not a natural number.

Hint.

The result in Task 5.c may be helpful in a proof by contradiction.

🔗

10.

Extending the idea in Exercise 1 of Section 3.4, we can represent three consecutive integers as $m,$ $m + 1,$ and $m + 2,$ where $m$ is an integer.

🔗

(a)

Explain why we can also represent three consecutive integers as $k - 1,$ $k,$ and $k + 1,$ where $k$ is an integer.

🔗

(b)

Explain why Proposition 3.33 proves that the product of any three consecutive integers is divisible by 3.

Hint.

Factor $n^{3} - n .$

🔗

(c)

Prove that the product of three consecutive integers is divisible by 6.

Hint.

Consider using cases based on congruence modulo 6.

🔗

11.

Complete the following.

🔗

(a)

Use the result in Proposition 3.39 to help prove that the integer $m = 5, 344, 580, 232, 468, 953, 153$ is not a perfect square. Recall that an integer $n$ is a perfect square provided that there exists an integer $k$ such that $n = k^{2} .$

Hint.

Use a proof by contradiction.

🔗

(b)

Is the integer $n = 782, 456, 231, 189, 002, 288, 438$ a perfect square? Justify your conclusion.

🔗

12.

Complete the following.

🔗

(a)

Use the result in Proposition 3.39 to help prove that for each integer $a,$ if 5 divides $a^{2},$ then 5 divides $a .$

🔗

(b)

Prove that the real number $\sqrt{5}$ is an irrational number.

🔗

13.

Prove the following.

🔗

(a)

For each integer $a,$ if $a ≢ 0 (\mod 7),$ then $a^{2} ≢ 0 (\mod 7) .$

🔗

(b)

For each integer $a,$ if 7 divides $a^{2},$ then 7 divides $a .$

🔗

(c)

The real number $\sqrt{7}$ is an irrational number.

🔗

14.

Complete the following.

🔗

(a)

If an integer has a remainder of 6 when it is divided by 7, is it possible to determine the remainder of the square of that integer when it is divided by 7? If so, determine the remainder and prove that your answer is correct.

🔗

(b)

If an integer has a remainder of 11 when it is divided by 12, is it possible to determine the remainder of the square of that integer when it is divided by 12? If so, determine the remainder and prove that your answer is correct.

🔗

(c)

Let $n$ be a natural number greater than 2. If an integer has a remainder of $n - 1$ when it is divided by $n,$ is it possible to determine the remainder of the square of that integer when it is divided by $n ?$ If so, determine the remainder and prove that your answer is correct.

🔗

15.

Let $n$ be a natural number greater than 4 and let $a$ be an integer that has a remainder of $n - 2$ when it is divided by $n .$ Make whatever conclusions you can about the remainder of $a^{2}$ when it is divided by $n .$ Justify all conclusions.

🔗

16.

Is the following proposition true or false? Justify your conclusion with a proof or a counterexample.

For each natural number $n,$ if 3 does not divide $(n^{2} + 2),$ then $n$ is not a prime number or $n = 3 .$

🔗

17.

Complete the following.

🔗

(a)

Is the following proposition true or false? Justify your conclusion with a counterexample or a proof.

For each integer $n,$ if $n$ is odd, then $n^{2} \equiv 1 (\mod 8) .$

🔗

(b)

Compare this proposition to the proposition in Exercise 7 from Section 3.4. Are these two propositions equivalent? Explain.

🔗

(c)

Is the following proposition true or false? Justify your conclusion with a counterexample or a proof.

For each integer $n,$ if $n$ is odd and $n$ is not a multiple of 3, then $n^{2} \equiv 1 (\mod 24) .$

🔗

18.

Prove the following proposition:

For all integers $a$ and $b,$ if 3 divides $(a^{2} + b^{2}),$ then 3 divides $a$ and 3 divides $b .$

🔗

19.

Is the following proposition true or false? Justify your conclusion with a counterexample or a proof.

For each integer $a,$ 3 divides $a^{3} + 23 a .$

🔗

20.

Are the following statements true or false? Either prove the statement is true or provide a counterexample to show it is false.

🔗

(a)

For all integers $a$ and $b,$ if $a \cdot b \equiv 0 (\mod 6),$ then $a \equiv 0 (\mod 6)$ or $b \equiv 0 (\mod 6) .$

🔗

(b)

For all integers $a$ and $b,$ if $a \cdot b \equiv 0 (\mod 8),$ then $a \equiv 0 (\mod 8)$ or $b \equiv 0 (\mod 8) .$

🔗

(c)

For all integers $a$ and $b,$ if $a \cdot b \equiv 1 (\mod 6),$ then $a \equiv 1 (\mod 6)$ or $b \equiv 1 (\mod 6) .$

🔗

(d)

For all integers $a$ and $b,$ if $a b \equiv 7 (\mod 1) 2,$ then either $a \equiv 1 (\mod 1) 2$ or $a \equiv 7 (\mod 1) 2 .$

🔗

21.

Complete the following.

🔗

(a)

Determine several pairs of integers $a$ and $b$ such that $a \equiv b (\mod 5) .$ For each such pair, calculate $4 a + b,$ $3 a + 2 b,$ and $7 a + 3 b .$ Are each of the resulting integers congruent to 0 modulo 5?

🔗

(b)

Prove or disprove the following proposition:

Let $m$ and $n$ be integers such that $(m + n) \equiv 0 (\mod 5)$ and let $a, b \in Z .$ If $a \equiv b (\mod 5),$ then $(m a + n b) \equiv 0 (\mod 5) .$

🔗

22. Evaluation of Proofs.

See the instructions for Exercise 19 from Section 3.1.

🔗

(a)

Proposition

For all integers $a$ and $b,$ if $(a + 2 b) \equiv 0 (\mod 3),$ then $(2 a + b) \equiv 0 (\mod 3) .$

Proof

We assume $a, b \in Z$ and $(a + 2 b) \equiv 0 (\mod 3) .$ This means that 3 divides $a + 2 b$ and, hence, there exists an integer $m$ such that $a + 2 b = 3 m .$ Hence, $a = 3 m - 2 b .$ For $(2 a + b) \equiv 0 (\mod 3),$ there exists an integer $x$ such that $2 a + b = 3 x .$ Hence,

\begin{aligned} 2 (3 m - 2 b) + b & = 3 x \\ 6 m - 3 b & = 3 x \\ 3 (2 m - b) & = 3 x \\ 2 m - b & = x . \end{aligned}

Since $(2 m - b)$ is an integer, this proves that 3 divides $(2 a + b)$ and hence, $(2 a + b) \equiv 0 (\mod 3) .$

🔗

(b)

Proposition

For each integer $m,$ 5 divides $(m^{5} - m) .$

Proof

Let $m \in Z .$ We will prove that 5 divides $(m^{5} - m)$ by proving that $(m^{5} - m) \equiv 0 (\mod 5) .$ We will use cases.

For the first case, if $m \equiv 0 (\mod 5),$ then $m^{5} \equiv 0 (\mod 5)$ and, hence, $(m^{5} - m) \equiv 0 (\mod 5) .$

For the second case, if $m \equiv 1 (\mod 5),$ then $m^{5} \equiv 1 (\mod 5)$ and, hence, $(m^{5} - m) \equiv (1 - 1) (\mod 5),$ which means that $(m^{5} - m) \equiv 0 (\mod 5) .$

For the third case, if $m \equiv 2 (\mod 5),$ then $m^{5} \equiv 32 (\mod 5)$ and, hence, $(m^{5} - m) \equiv (32 - 2) (\mod 5),$ which means that $(m^{5} - m) \equiv 0 (\mod 5) .$

🔗

Activity 17. Using a Contradiction to Prove a Case Is Not Possible.

Explore the statements in Task 17.a and Task 17.b by considering several examples where the hypothesis is true.

🔗

(a)

If an integer $a$ is divisible by both 4 and 6, then it divisible by 24.

🔗

(b)

If an integer $a$ is divisible by both 2 and 3, then it divisible by 6.

🔗

(c)

What can you conclude from the examples in Task 17.a?

🔗

(d)

What can you conclude from the examples in Task 17.b?

The proof of the following proposition based on Task 17.b uses cases. In this proof, however, we use cases and a proof by contradiction to prove that a certain integer cannot be odd. Hence, it must be even. Complete the proof of the proposition.

Proposition

Let $a \in Z .$ If 2 divides $a$ and 3 divides $a,$ then 6 divides $a .$

Proof

Let $a \in Z$ and assume that 2 divides $a$ and 3 divides $a .$ We will prove that 6 divides $a .$ Since 3 divides $a,$ there exists an integer $n$ such that

a = 3 n .

The integer $n$ is either even or it is odd. We will show that it must be even by obtaining a contradiction if it assumed to be odd. So, assume that $n$ is odd. (Now complete the proof.)

🔗

Activity 18. The Last Two Digits of a Large Integer.

Notice that $7, 381, 272 \equiv 72 (\mod 1) 00$ since $7, 381, 272 - 72 = 7, 381, 200,$ which is divisible by 100. In general, if we start with an integer whose decimal representation has more than two digits and subtract the integer formed by the last two digits, the result will be an integer whose last two digits are 00. This result will be divisible by 100. Hence, any integer with more than 2 digits is congruent modulo 100 to the integer formed by its last two digits.

🔗

(a)

Start by squaring both sides of the congruence $3^{4} \equiv 81 (\mod 100)$ to prove that $3^{8} \equiv 61 (\mod 100)$ and then prove that $3^{16} \equiv 21 (\mod 100) .$ What does this tell you about the last two digits in the decimal representation of $3^{16} ?$

🔗

(b)

Use the two congruences in Task 18.a and laws of exponents to determine $r$ where $3^{20} \equiv r (\mod 100)$ and $r \in Z$ with $0 \leq r < 100$ . What does this tell you about the last two digits in the decimal representation of $3^{20} ?$

🔗

(c)

Determine the last two digits in the decimal representation of $3^{400} .$

🔗

(d)

Determine the last two digits in the decimal representation of $4^{804} .$

Hint.

One way is to determine the “mod 100 values” for $4^{2},$ $4^{4},$ $4^{8},$ $4^{16},$ $4^{32},$ $4^{64},$ and so on. Then use these values and laws of exponents to determine $r,$ where $4^{804} \equiv r (\mod 100)$ and $r \in Z$ with $0 \leq r < 100 .$

🔗

(e)

Determine the last two digits in the decimal representation of $3^{3356} .$

🔗

(f)

Determine the last two digits in the decimal representation of $7^{403} .$

Section 3.5 The Division Algorithm and Congruence

Beginning Activity Beginning Activity 1: Quotients and Remainders A4US

1.

2.

3.

4.

5.

Beginning Activity Beginning Activity 2: Some Work with Congruence Modulo n A4US

1.

(a)

(b)

2.

3.

4.

Subsection The Division Algorithm

The Division Algorithm.

Some Comments about the Division Algorithm.

Progress Check 3.32. Using the Division Algorithm.

(a)

(i)

(ii)

(b)

(i)

(ii)

(iii)

(iv)

(v)

(vi)

Subsection Using Cases Determined by the Division Algorithm

Proposition 3.33.

Proof.

Subsection Properties of Congruence

Theorem 3.34. Properties of Congruence Modulo.

Proof.

Progress Check 3.35. Proving Item 1 of Theorem 3.34.

Proof.

Theorem 3.36. Properties of Congruence Modulo n.

Proof.

Subsection Using Cases Based on Congruence Modulo n

Theorem 3.37.

Corollary 3.38.

Proposition 3.39.

Proof.

Progress Check 3.40. Using Properties of Congruence.

Progress Check 3.41. Using Cases Modulo 6.

(a)

(b)

(c)

Proposition 3.42.

Exercises Exercises

1.

2.

(a)

(b)

3.

4.

(a)

(b)

5.

(a)

(b)

(c)

6.

7.

(a)

(b)

8.

(a)

(b)

9.

10.

(a)

(b)

(c)

11.

(a)

(b)

12.

(a)

(b)

Beginning Activity Beginning Activity 1: Quotients and Remainders
A4 US

Beginning Activity Beginning Activity 2: Some Work with Congruence Modulo $n$
A4 US

Theorem 3.36. Properties of Congruence Modulo $n$ .

Subsection Using Cases Based on Congruence Modulo $n$