Skip to main content

Chapter 6 Proofs

Here are the definitions of even and odd.

  • An integer \(n \in \mathbb{Z}\) is even when there exists \(k \in \mathbb{Z}\) such that \(n = 2k\text{.}\)

  • An integer \(n \in \mathbb{Z}\) is odd when there exists \(k \in \mathbb{Z}\) such that \(n = 2k+1\text{.}\)

Here are the definitions of divisible and not divisisble. Let \(n,d \in \mathbb{Z}\) be integers.

  • We say that \(d \mid n\) when there exists \(k \in \mathbb{Z}\) such that \(n=dk\text{.}\)

  • Otherwise, we say that \(d \nmid n\text{.}\) This means that \(n \neq dk\) for all \(k \in \mathbb{Z}\text{.}\)

Use these definitions to prove the following statements.

Exercises Practice Problems

1. Odd to Even.

Prove that for all integers \(n \in \mathbb{Z}\text{,}\) if \(n\) is odd, then \(5n + 3 \) is even.

Solution.

We have \(n=2r+1\) for some \(r \in \mathbb{Z}\text{.}\) Therefore

\begin{equation*} 5n+3 = 5(2r+1)+3 = 10r+8 = 2(5r+4). \end{equation*}

Taking \(s=5r+4\text{,}\) we have \(5n+3=2s\text{,}\) which proves that \(5n+3\) is even.

2. Any to Odd.

Prove that if \(n \in \mathbb{Z}\text{,}\) then \(5n^2+3n+7\) is odd.

Solution.

There are two cases: when \(n\) is odd and when \(n\) is even.

Case 1: \(n\) is odd. We have \(n=2r+1\) for some \(r \in \mathbb{Z}\text{.}\) Therefore

\begin{align*} 5n^2+3n+7 & = 5(2r+1)^2+3(2r+1)+7 = (20r^2 + 20r+ 5) + (6r+3) + 7\\ & = 20r^2 + 26r+15 = 2(10r^2+13r+7) +1. \end{align*}

Taking \(s=10r^2+13r+7\text{,}\) we have \(5n^2+3n+7=2s+1\text{,}\) which proves that \(5n^2+3n+7\) is odd.

Case 2: \(n\) is even. We have \(n=2r\) for some \(r \in \mathbb{Z}\text{.}\) Therefore

\begin{equation*} 5n^2+3n+7 = 5(2r)^2+3(2r)+7 = 20r^2 + 6r + 7 = 2(10r^2+3r+3) +1. \end{equation*}

Taking \(s=10r^2+3r+3\text{,}\) we have \(5n^2+3n+7=2s+1\text{,}\) which proves that \(5n^2+3n+7\) is odd.

3. Even/Odd Combo.

Prove that if \(a\) is any odd integer and \(b\) is any even integer, then \(2a+3b\) is an even integer.

Solution.

We have \(a=2r+1\) for some \(r \in \mathbb{Z}\text{,}\) and \(b=2s\) for some \(s \in \mathbb{Z}\text{.}\) Therefore

\begin{equation*} 2a+3b = 2(2r+1) + 3(2s) = 4r+6s+2 = 2(2r+3s+1) \end{equation*}

Taking \(t=2r+3s+1\text{,}\) we have \(2a+3b=2t\text{,}\) which proves that \(5n^2+3n+7\) is even.

4. Summing Squares.

Prove that if \(a\) is any odd integer and \(b\) is any even integer, then \(a^2+b^2\) is an odd integer.

Solution.

We have \(a=2r+1\) for some \(r \in \mathbb{Z}\text{,}\) and \(b=2s\) for some \(s \in \mathbb{Z}\text{.}\) Therefore

\begin{equation*} a^2 + b^2 = (2r+1)^2 + (2s)^2 = 4r^2 + 4r + 4s^2 + 1 = 2(2r^2+ 2r+2s^2) +1 \end{equation*}

Taking \(t=2r^2+ 2r+2s^2\text{,}\) we have \(a^2+b^2=2t+1\text{,}\) which proves that \(5n^2+3n+7\) is odd.

5. Proof by Contrapositive.

Use a proof by contrapositive to show that for all integers \(m,n \in \mathbb{Z}\text{,}\) if \(mn\) is even then \(m\) is even or \(n\) is even.

Solution.

The contrapositive of the statement is: if \(m\) is odd and \(n\) is odd then \(mn\) is odd. Let's prove this statment. We have \(m=2r+1\) and \(n=2s+1\) for some \(r,s \in \mathbb{Z}\text{.}\) Then

\begin{equation*} mn = (2r+1)(2s+1) = 4rs+2r+2s+1 = 2(2rs+r+s)+1. \end{equation*}

Taking \(t=2rs+r+s\text{,}\) we have \(mn= 2t+1\) and therefore \(mn\) is odd. We have proved the contrapositive, so the original statement is also true (because an implication and its contrapositive have the same truth values).

6. Proof by Contradiction.

Use a proof by contradiction to show that for any integer \(n \in \mathbb{Z}\text{,}\) we have \(4 \nmid n^2-2.\)

Solution.

Assume for the sake of contradiction (AFSOC) that \(4 \mid n^2-2.\) This means that \(n^2-2 = 4k\) for some \(k \in \mathbb{Z}\text{.}\) We have two cases.

Case 1: \(n\) is odd. We have \(n=2r+1\) for some \(r \in \mathbb{Z}\text{.}\) We now have

\begin{align*} (2r+1)^2-2 & = 4k\\ 4r^2+4r-1 & = 4k\\ 4r^2+4r-4k & = 1\\ 2(2r^2+2r-2k) & = 1\\ 2r^2+2r-2k & = \frac{1}{2} \end{align*}

which is a contradiction because the left hand size is an integer, while the right hand side is not. Therefore \(4 \nmid n^2-2\) when \(n\) is odd.

Case 2: \(n\) is even. We have \(n=2r\) for some \(r \in \mathbb{Z}\text{.}\) We now have

\begin{align*} (2r)^2-2 & = 4k\\ 4r^2-2 & = 2k\\ 4r^2-4k & = 2\\ 2(r^2-k) & = 1\\ r^2-k & = \frac{1}{2} \end{align*}

which is a contradiction because the left hand size is an integer, while the right hand side is not. Therefore \(4 \nmid n^2-2\) when \(n\) is even.

7. Your Choice.

Prove the following statement using either proof by contrapositive, or proof by contradiction.

For integers \(a,b,n \in \mathbb{Z}\text{,}\) if \(ab = n\text{,}\) then either \(a \geq \sqrt{n}\) or \(b \geq \sqrt{n}\text{.}\)

Solution.

Here is a proof by contrapositive. We must prove that if \(a < \sqrt{n}\) and \(b < \sqrt{n}\) then \(ab \neq n\text{.}\)

So assume that \(a < \sqrt{n}\) and \(b < \sqrt{n}\text{.}\) We have

\begin{equation*} ab < \sqrt{n} \cdot \sqrt{n} = n. \end{equation*}

Now, we have \(ab < n\text{,}\) so of course \(ab \neq n\text{.}\) We have proved that the contrapositive statement is true, so the original implication is true as well.