Skip to main content

Section 5.3 Practice Problems for ChapterĀ 5

Exercises

1.

Consider the following proposition:

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

(a)

Write the contrapositive of this proposition.

(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 since the hypothesis of the contrapositive is, ā€œ3 does not divide \(a\text{.}\)ā€

Solution.
Proof.

We will prove the contrapositive of this proposition, which is:

For each integer \(a\text{,}\) if 3 does not divide \(a\text{,}\) then 3 does not divide \(a^2\)
So we let \(a\) be an integer, assume that 3 does not divide \(a\text{,}\) and will prove that 3 does not divide \(a^2\text{.}\) Since 3 does not divide \(a\text{,}\) we can use the Division Algorithm to conclude that there exists an integer \(q\) such that \(a = 3q + 1\) or \(a = 3q + 2\text{.}\)

For the case where \(a = 3q + 1\text{,}\) we obtain

\begin{align*} a^2 \amp = (3q + 1)^2\\ \amp = 9q^2 + 6q + 1\\ \amp = 3 ( 3q^2 + 2q) + 1 \end{align*}

By the closure properties of the integers \(( 3q^2 + 2q)\) is an integer, and so the last equation means that \(a^2\) has a remainder of 1 when divided by 3 and so 3 does not divide \(a^2\text{.}\)

For the case where \(a = 3q + 2\text{,}\) we obtain

\begin{align*} a^2 \amp = (3q + 2)^2\\ \amp = 9q^2 + 12q + 4\\ \amp = 3 ( 3q^2 + 4q + 1) + 1 \end{align*}

By the closure properties of the integers \(( 3q^2 + 4q + 1)\) is an integer, and so the last equation means that \(a^2\) has a remainder of 1 when divided by 3 and so 3 does not divide \(a^2\text{.}\)

Since we have proved that 3 does not divide \(a^2\) in both cases, we have proved the contrapositive of the proposition, and hence, we have proved that for each integer \(a\text{,}\) if 3 divides \(a^2\) , then 3 divides \(a\text{.}\)

2.

Complete the details for the proof of Case 3 of PropositionĀ 5.2.

Solution.

For the third case, \(n = 3q + 2\) and \(r = 2\text{.}\) When we substitute this into \((n^3 - n)\text{,}\) we obtain

\begin{align*} n^3 - n \amp = (3q + 2)^3 - (3q + 2)\\ \amp = ( 27 q^3 + 54q^2+ 36q + 8) - (3q + 2)\\ \amp = 27 q^3 + 54q^2 + 33q + 6\\ \amp = 3 (9q^3 + 18q^2 + 11q + 2)\text{.} \end{align*}

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

3.

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

For each integer \(n\text{,}\) if \(n\) is odd, then 8 divides \(n^2 - 1\text{.}\)

Solution.
Proof.

We let \(n\) be an integer, assume that \(n\) is odd, and will prove that 8 divides \(n\) 21. Since \(n\) is odd, there exists an integer \(k\) such that \(n = 2k + 1\text{.}\) We then see that

\begin{align} n^2 - 1 \amp = (2k + 1)^2 - 1\notag\\ \amp = 4k^2 + 4k\notag\\ \amp = 4k (k + 1)\tag{5} \end{align}

We also know since \(k\) is an integer, either \(k\) or \(k + 1\) is even. In either case, the product \(k(k + 1)\) must be even and so there exists an integer \(q\) such that

\begin{equation*} k (k + 1) = 2q \end{equation*}

Substituting this into the right side of equation (5), we obtain \(n^2 - 1 = 8q\) and so 8 divides \(n^2 - 1\text{.}\) This proves that for each integer \(n\text{,}\) if \(n\) is odd, then 8 divides \(n^2 - 1\text{.}\)