Mathematical Reasoning: Writing and Proof (PreTeXt Edition)

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

(ii)

Divided by 9?

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 = bq + r\text{,}\) where \(0 \leq r \lt b\text{.}\)

(i)

When 17 is divided by 3.

\(17 = 5 \cdot 3 + 2\)

(ii)

When \(-17\) is divided by 3.

\(-17 = \left( -6 \right) \cdot 3 + 1\)

(iii)

When 73 is divded by 7.

\(73 = 10 \cdot 7 + 3\)

(iv)

When \(-73\) is divided by 7.

\(-73 = \left( -11 \right) \cdot 7 + 4\)

(v)

When 436 is divided by 27.

\(436 = 16 \cdot 27 + 4\)

(vi)

When 539 is divided by 110.

\(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

\begin{equation*} n = 3q + r\text{ and } 0 \leq r \lt 3\text{.} \end{equation*}

We can then divide the proof into the following three cases: (1) \(r = 0\text{;}\) (2) \(r = 1\text{;}\) and (3) \(r = 2\text{.}\) This is done in Proposition 3.33.

Proposition 3.33.

If \(n\) is an integer, then 3 divides \(n^3-n\text{.}\)

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

\begin{equation*} n = 3q + r\text{ , and } 0 \leq r \lt 3\text{.} \end{equation*}

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

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

\begin{align*} n^3 - n \amp = \left( {3q} \right)^3 - \left( {3q} \right)\\ \amp = 27q^3 - 3q\\ \amp = 3\left( {9q^3 - q} \right)\text{.} \end{align*}

Since \(\left( {9q^3 -q} \right)\) is an integer, the last equation proves that \(3 \mid \left( n^3 - n \right)\text{.}\)

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

\begin{align*} n^3 - n \amp = \left( {3q + 1} \right)^3 - \left( {3q + 1} \right)\\ \amp = \left( 27q^3 + 27q^2 +9q + 1\right) - \left( 3q + 1 \right)\\ \amp = 27q^3 + 27q^2 + 6q\\ \amp = 3 \left( 9q^3 + 9q^2 + 2q \right)\text{.} \end{align*}

Since \(\left( {9q^3 +9q^2 + 2q} \right)\) is an integer, the last equation proves that \(3 \mid \left( n^3 - n \right)\text{.}\)

The last case is when \(r = 2\text{.}\) 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\text{.}\)

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 \mathbb{N}\text{.}\) 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\text{,}\) and we write \(a \equiv b \pmod n\text{.}\) (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, \text{ and } d\) be integers. If \(a \equiv b \pmod n\) and \(c \equiv d \pmod n\text{,}\) then

\(\left( {a + c} \right) \equiv \left( {b + d} \right) \pmod n\text{.}\)
\(ac \equiv bd \pmod n\text{.}\)
For each \(m \in \mathbb{N}\text{,}\) \(a^m \equiv b^m \pmod n\text{.}\)

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, \text{ and } d\) be integers. Assume that \(a \equiv b \pmod n\) and that \(c \equiv d \pmod n\text{.}\) This means that \(n\) divides \(a-b\) and that \(n\) divides \(c-d\text{.}\) Hence, there exist integers \(k\) and \(q\) such that \(a-b=nk\) and \(c-d=nq\text{.}\) We can then write \(a = b + nk\) and \(c = d + nq\) and obtain

\begin{align*} ac \amp \left( {b + nk} \right)\left( {d + nq} \right)\\ \amp = bd + bnq + dnk + n^2 kq\\ \amp = bd + n\left( {bq + dk + nkq} \right)\text{.} \end{align*}

By subtracting \(bd\) from both sides of the last equation, we see that

\begin{equation*} ac - bd = n\left( {bq + dk + nkq} \right)\text{.} \end{equation*}

Since \(bq + dk + nkq\) is an integer, this proves that \(n \mid \left( {ac - bd} \right)\text{,}\) and hence we can conclude that \(ac \equiv bd \pmod n\text{.}\) 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 \pmod n\) and so we write this twice as follows:

\begin{align*} a \amp \equiv b \pmod n, \text{ and }\\ a \amp \equiv b \pmod n\text{.} \end{align*}

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 \pmod n\text{.}\) We can then use this congruence and the congruence \(a \equiv b \pmod n\) and the result in Item 2 to conclude that

\begin{equation*} a^2 \cdot a \equiv b^2 \cdot b \pmod n\text{,} \end{equation*}

or that \(a^3 \equiv b^3 \pmod n\text{.}\) 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.

Proof.

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

\begin{align*} a + c \amp = (b + nk) + (d + nq)\\ \amp = (b + d) + n(k + q) \end{align*}

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

\begin{equation*} (a + c) - (b + d) = n(k + q)\text{.} \end{equation*}

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

Exercise 11 in Section 3.1 gave three important properties of congruence modulo \(n\text{.}\) 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 \(\boldsymbol{n}\).

Let \(n \in \mathbb{N}\text{,}\) and let \(a\text{,}\) \(b\text{,}\) and \(c\) be integers.

For every integer \(a\text{,}\) \(a \equiv a \pmod n\text{.}\)

This is called the reflexive property of congruence modulo \(n\text{.}\)
If \(a \equiv b \pmod n\text{,}\) then \(b \equiv a \pmod n\text{.}\)

This is called the symmetric property of congruence modulo \(n\text{.}\)
If \(a \equiv b \pmod n\) and \(b \equiv c \pmod n\text{,}\) then \(a \equiv c \pmod n\text{.}\)

This is called the transitive property of congruence modulo \(n\text{.}\)

Proof.

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

Let \(n \in \mathbb{N}\text{,}\) and let \(a \in \mathbb{Z}\text{.}\) We will show that \(a \equiv a \pmod n\text{.}\) Notice that

\begin{equation*} a - a = 0 = n \cdot 0\text{.} \end{equation*}

This proves that \(n\) divides \(\left( {a - a} \right)\) and hence, by the definition of congruence modulo \(n\text{,}\) we have proven that \(a \equiv a \pmod n\text{.}\)

To prove the transitive property, we let \(n \in \mathbb{N}\text{,}\) and let \(a\text{,}\) \(b\text{,}\) and \(c\) be integers. We assume that \(a \equiv b \pmod n\) and that \(b \equiv c \pmod n\text{.}\) We will use the definition of congruence modulo \(n\) to prove that \(a \equiv c \pmod n\text{.}\) Since \(a \equiv b \pmod n\) and \(b \equiv c \pmod n\text{,}\) we know that \(n \mid \left( a-b \right)\) and \(n \mid \left( b-c \right)\text{.}\) Hence, there exist integers \(k\) and \(q\) such that

\begin{align*} a -b \amp = nk\\ b - c \amp = nq\text{.} \end{align*}

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

\begin{equation*} \left( {a - b} \right) + \left( {b - c} \right) = nk + nq\text{.} \end{equation*}

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

\begin{equation*} a - c = n\left( {k + q} \right)\text{.} \end{equation*}

By the closure property of the integers, \(\left( {k + q} \right) \in \mathbb{Z}\text{,}\) and so this equation proves that \(n \mid \left(a-c \right)\) and hence that \(a \equiv c \pmod n\text{.}\) This completes the proof of the transitive property of congruence modulo \(n\text{.}\)

Subsection Using Cases Based on Congruence Modulo \(\boldsymbol{n}\)

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

\begin{equation*} \left\{ n \in \Z \mid n \equiv 2 \pmod7 \right\} = \left\{ \ldots , - 19, - 12, - 5, 2, 9, 16, 23, \ldots \right\}\text{.} \end{equation*}

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{align*} 2 \amp = 7 \cdot 0 + 2 \amp -5 \amp = 7 \left( -1 \right) + 2\\ 9 \amp = 7 \cdot 1 + 2 \amp -12 \amp = 7 \left( -2 \right) +2\\ 16 \amp = 7 \cdot 2 + 2 \amp -19 \amp = 7 \left( -3 \right) +2\\ 23 \amp = 7 \cdot 3 + 2. \amp \amp \end{align*}

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 \mathbb{Z}\text{.}\) By the Division Algorithm, there exist unique integers \(q\) and \(r\) such that

\begin{equation*} a = nq + r\text{ and } 0 \leq r \lt n\text{.} \end{equation*}

By subtracting \(r\) from both sides of the equation \(a = nq + r\text{,}\) we obtain

\begin{equation*} a - r = nq\text{.} \end{equation*}

But this implies that \(n \mid \left( a - r \right)\) and hence that \(a \equiv r \pmod n\text{.}\) We have proven the following result.

Theorem 3.37.

Let \(n \in \mathbb{N}\) and let \(a \in \mathbb{Z}\text{.}\) If \(a = nq + r\text{ and } 0 \leq r \lt n\) for some integers \(q\) and \(r\text{,}\) then \(a \equiv r \pmod n\text{.}\)

This theorem says that an integer is congruent (mod \(n\)) to its remainder when it is divided by \(n\text{.}\) Since this remainder is unique and since the only possible remainders for division by \(n\) are \(0,1,2, \ldots ,n - 1\text{,}\) we can state the following result.

Corollary 3.38.

If \(n \in \mathbb{N}\text{,}\) then each integer is congruent, modulo \(n\text{,}\) to precisely one of the integers \(0,1,2, \ldots ,n - 1\text{.}\) That is, for each integer \(a\text{,}\) there exists a unique integer \(r\) such that

\begin{equation*} a \equiv r \pmod n \text{ and } 0 \leq r \lt n\text{.} \end{equation*}

Corollary 3.38 can be used to set up cases for an integer in a proof. If \(n \in \mathbb{N}\) and \(a \in \mathbb{Z}\text{,}\) then we can consider \(n\) cases for \(a\text{.}\) The integer \(a\) could be congruent to \(0,1,2, \ldots , \text{ or } n - 1\) modulo \(n\text{.}\) For example, if we assume that 5 does not divide an integer \(a\text{,}\) 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{align*} 1^2 \amp = 1 \amp \text{ and } \amp \amp 1 \amp \equiv 1 \pmod 5.\\ 3^2 \amp = 9 \amp \text{ and } \amp \amp 9 \amp \equiv 4 \pmod 5.\\ 6^2 \amp = 36 \amp \text{ and } \amp \amp 36 \amp \equiv 1 \pmod 5.\\ 8^2 \amp = 64 \amp \text{ and } \amp \amp 64 \amp \equiv 4 \pmod 5.\\ 9^2 \amp = 81 \amp \text{ and } \amp \amp 81 \amp \equiv 1 \pmod 5\text{.} \end{align*}

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\text{,}\) if \(a \not \equiv 0 \pmod 5\text{,}\) then \(a^2 \equiv 1 \pmod 5\) or \(a^2 \equiv 4 \pmod 5\text{.}\)

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 \not \equiv 0 \pmod 5\text{,}\) we can use four cases, which are: (1) \(a \equiv 1 \pmod 5\text{,}\) (2) \(a \equiv 2 \pmod 5\text{,}\) (3) \(a \equiv 3 \pmod 5\text{,}\) and (4) \(a \equiv 4 \pmod 5\text{.}\) Following are proofs for the first and fourth cases.

Case 1. \(\left( a \equiv 1 \pmod 5 \right)\text{.}\) In this case, we use Theorem 3.34 to conclude that

\begin{equation*} a^2 \equiv 1^2 \pmod 5 \text{ or } a^2 \equiv 1 \pmod 5\text{.} \end{equation*}

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

Case 4. \(\left( a \equiv 4 \pmod 5 \right)\text{.}\) In this case, we use Theorem 3.34 to conclude that

\begin{equation*} a^2 \equiv 1^2 \pmod 5 \text{ or } a^2 \equiv 16 \pmod 5\text{.} \end{equation*}

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

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.

Case 2. \(\left( a \equiv 2 \pmod 5 \right)\text{.}\) In this case, we use Theorem 3.34 to conclude that

\begin{equation*} a^2 \equiv 2^2 \pmod 5 \text{ or } a^2 \equiv 4 \pmod 5\text{.} \end{equation*}

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

Case 3. \(\left( a \equiv 3 \pmod 5 \right)\text{.}\) In this case, we use Theorem 3.34 to conclude that

\begin{equation*} a^2 \equiv 3^2 \pmod 5 \text{ or } a^2 \equiv 9 \pmod 5\text{.} \end{equation*}

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

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 \pmod 6\text{,}\) then there exists an integer \(k\) such that \(a = 6k\text{.}\) But then \(a = 2(3k)\) and hence, \(a\) is even. Since we assumed that \(a\) is odd, this case is not possible.
If \(a \equiv 2 \pmod 6\text{,}\) then there exists an integer \(k\) such that \(a = 6k + 2\text{.}\) But then \(a = 2(3k + 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\text{,}\) 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\text{,}\) if \(a\) is an odd integer that is not multiple of 3, then \(a^2 \equiv 1 \pmod 6\text{.}\)

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\text{,}\) \(n^3 \equiv n \pmod 3\text{.}\)

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

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

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

(b)

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

Since \(n^3 \equiv n \pmod 3\text{,}\) we use the definition of congruence to conclude that 3 divides \(\left( n^3 - n \right)\text{.}\)

3.

Prove the symmetric property of congruence stated in Theorem 3.36.

For \(a, b \in \mathbb{Z}\text{,}\) you need to prove that if \(a \equiv b \pmod n\text{,}\) then \(b \equiv a \pmod n\text{.}\) So let \(a, b \in \mathbb{Z}\) and assume that \(a \equiv b \pmod n\text{.}\) So \(n \mid \left( a - b \right)\) and there exists an integer \(k\) such that \(a - b = nk\text{.}\) Then, \(b - a = n ( -k )\) and \(b \equiv a \pmod n\text{.}\)

4.

Consider the following proposition: For each integer \(a\text{,}\) if 3 divides \(a^2\text{,}\) then 3 divides \(a\text{.}\)

(a)

Write the contrapositive of this proposition.

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

(b)

Prove the proposition by proving its contrapositive.

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

To prove the contrapositive, let \(a \in \Z\) and assume that 3 does not divide \(a\text{.}\) So using the Division Algorithm, we can consider two cases: (1) There exists a unique integer \(q\) such that \(a = 3q + 1\text{.}\) (2) There exists a unique integer \(q\) such that \(a = 3q + 2\text{.}\) For the first case, show that \(a^2 = 3 \left( 3q^2 + 2q \right) + 1\text{.}\) For the second case, show that \(a^2 = 3 \left( 3q^2 + 4q + 1 \right) + 1\text{.}\) 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\text{.}\)

5.

Complete the following.

(a)

Let \(n \in \mathbb{N}\) and let \(a \in \mathbb{Z}\text{.}\) Explain why \(n\) divides \(a\) if and only if \(a \equiv 0 \pmod n\text{.}\)

\(a \equiv 0 \pmod n\) if and only if \(n \mid \left( a - 0 \right)\text{.}\)

(b)

Let \(a \in \mathbb{Z}\text{.}\) Explain why if \(a \not \equiv 0 \pmod 3\text{,}\) then \(a \equiv 1\pmod 3\) or \(a \equiv 2 \pmod 3\text{.}\)

Let \(a \in \mathbb{Z}\text{.}\) Corollary 3.38 tell us that if \(a \not \equiv 0 \pmod 3\text{,}\) then \(a \equiv 1 \pmod 3\) or \(a \equiv 2 \pmod 3\text{.}\)

(c)

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

For each \(a \in \mathbb{Z}\text{,}\) if \(a \not \equiv 0 \pmod 3\text{,}\) then \(a^2 \equiv 1 \pmod 3\text{.}\)

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

6.

Prove the following proposition by proving its contrapositive.

For all integers \(a\) and \(b\text{,}\) if \(ab \equiv 0 \pmod 3\text{,}\) then \(a \equiv 0 \pmod 3\) or \(b \equiv 0 \pmod 3\text{.}\)

Use case analysis. There are several cases.

The contrapositive is: Let \(a\) and \(b\) be integers. If \(a \not\equiv 0 \pmod3\) and \(b \not\equiv 0 \pmod 3\text{,}\) then \(ab \not\equiv 0 \pmod 3\text{.}\) Using Task 5.b, we can use the following four cases:

\(a \equiv 1 \pmod 3\) and \(b \equiv 1 \pmod 3\text{;}\)
\(a \equiv 1 \pmod 3\) and \(b \equiv 2 \pmod 3\text{;}\)
\(a \equiv 2 \pmod 3\) and \(b \equiv 1 \pmod 3\text{;}\)
\(a \equiv 2 \pmod 3\) and \(b \equiv 2 \pmod 3\text{.}\)

In all four cases, we use Theorem 3.34 to conclude that \(ab \not \equiv 0 \pmod 3\text{.}\) For example, for the third case, we see that \(ab \equiv 2 \cdot 1 \pmod 3\text{.}\) That is, \(ab \equiv 2 \pmod 3\text{.}\)

7.

Complete the following.

(a)

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

For all integers \(a\) and \(b\text{,}\) if \(3 \mid ab\) , then \(3 \mid a\) or \(3 \mid b\text{.}\)

This follows from Exercise 5 and the fact that \(3 \mid k\) if and only if \(k \equiv 0 \pmod 3\text{.}\)

(b)

Prove that for each integer \(a\text{,}\) if 3 divides \(a^2\text{,}\) then 3 divides \(a\text{.}\)

This follows directly from Task 7.a using \(a = b\text{.}\)

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\text{,}\) then \(r\) is irrational.

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\text{,}\) \(\sqrt{3n + 2}\) is not a natural number.

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\text{,}\) \(m + 1\text{,}\) and \(m + 2\text{,}\) where \(m\) is an integer.

(a)

Explain why we can also represent three consecutive integers as \(k - 1\text{,}\) \(k\text{,}\) and \(k + 1\text{,}\) where \(k\) is an integer.

(b)

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

Factor \(n^3 - n\text{.}\)

(c)

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

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

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\text{,}\) if 5 divides \(a^2\text{,}\) then 5 divides \(a\text{.}\)

(b)

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

13.

Prove the following.

(a)

For each integer \(a\text{,}\) if \(a \not \equiv 0 \pmod 7\text{,}\) then \(a^2 \not \equiv 0 \pmod 7\text{.}\)

(b)

For each integer \(a\text{,}\) if 7 divides \(a^2\text{,}\) then 7 divides \(a\text{.}\)

(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\text{,}\) is it possible to determine the remainder of the square of that integer when it is divided by \(n\text{?}\) 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\text{.}\) Make whatever conclusions you can about the remainder of \(a^2\) when it is divided by \(n\text{.}\) 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\text{,}\) if 3 does not divide \(\left( n^2 + 2 \right)\text{,}\) then \(n\) is not a prime number or \(n=3\text{.}\)

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\text{,}\) if \(n\) is odd, then \(n^2 \equiv 1 \pmod 8\text{.}\)

(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\text{,}\) if \(n\) is odd and \(n\) is not a multiple of 3, then \(n^2 \equiv 1 \pmod {24}\text{.}\)

18.

Prove the following proposition:

For all integers \(a\) and \(b\text{,}\) if 3 divides \(\left( a^2 + b^2 \right)\text{,}\) then 3 divides \(a\) and 3 divides \(b\text{.}\)

19.

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

For each integer \(a\text{,}\) 3 divides \(a^3 + 23a\text{.}\)

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\text{,}\) if \(a \cdot b \equiv 0 \pmod 6\text{,}\) then \(a \equiv 0 \pmod 6\) or \(b \equiv 0 \pmod 6\text{.}\)

(b)

For all integers \(a\) and \(b\text{,}\) if \(a \cdot b \equiv 0 \pmod 8\text{,}\) then \(a \equiv 0 \pmod 8\) or \(b \equiv 0 \pmod 8\text{.}\)

(c)

For all integers \(a\) and \(b\text{,}\) if \(a \cdot b \equiv 1 \pmod 6\text{,}\) then \(a \equiv 1 \pmod 6\) or \(b \equiv 1 \pmod 6\text{.}\)

(d)

For all integers \(a\) and \(b\text{,}\) if \(ab \equiv 7 \pmod 12\text{,}\) then either \(a \equiv 1 \pmod 12\) or \(a \equiv 7 \pmod 12\text{.}\)

21.

Complete the following.

(a)

Determine several pairs of integers \(a\) and \(b\) such that \(a \equiv b \pmod 5\text{.}\) For each such pair, calculate \(4a + b\text{,}\) \(3a + 2b\text{,}\) and \(7a + 3b\text{.}\) 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 \pmod 5\) and let \(a, b \in \Z\text{.}\) If \(a \equiv b \pmod 5\text{,}\) then \((ma +nb) \equiv 0 \pmod 5\text{.}\)

22. Evaluation of Proofs.

See the instructions for Exercise 19 from Section 3.1.

(a)

Proposition

For all integers \(a\) and \(b\text{,}\) if \((a + 2b) \equiv 0 \pmod 3\text{,}\) then \((2a + b) \equiv 0 \pmod 3\text{.}\)

Proof

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

\begin{align*} 2(3m - 2b) + b \amp = 3x\\ 6m - 3b \amp = 3x\\ 3(2m - b) \amp = 3x\\ 2m - b \amp = x\text{.} \end{align*}

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

(b)

Proposition

For each integer \(m\text{,}\) 5 divides \(\left(m^5 - m \right)\text{.}\)

Proof

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

For the first case, if \(m \equiv 0 \pmod 5\text{,}\) then \(m^5 \equiv 0 \pmod 5\) and, hence, \(\left(m^5 - m \right) \equiv 0 \pmod 5\text{.}\)

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

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

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 \mathbb{Z}\text{.}\) If 2 divides \(a\) and 3 divides \(a\text{,}\) then 6 divides \(a\text{.}\)

Proof

Let \(a \in \mathbb{Z}\) and assume that 2 divides \(a\) and 3 divides \(a\text{.}\) We will prove that 6 divides \(a\text{.}\) Since 3 divides \(a\text{,}\) there exists an integer \(n\) such that

\begin{equation*} a = 3n\text{.} \end{equation*}

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 \pmod 100\) since \(7,381,272 - 72 = 7,381,200\text{,}\) 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 \pmod {100}\) to prove that \(3^8 \equiv 61 \pmod {100}\) and then prove that \(3^{16} \equiv 21 \pmod {100}\text{.}\) What does this tell you about the last two digits in the decimal representation of \(3^{16}\text{?}\)

(b)

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

(c)

Determine the last two digits in the decimal representation of \(3^{400}\text{.}\)

(d)

Determine the last two digits in the decimal representation of \(4^{804}\text{.}\)