7 - Contrapositive Proof

What is a contrapositive?

The contrapositive of $P ⟹ Q$ is $\neg Q ⟹ \neg P$ . The two statements are logically equivalent.

This is useful when the original direct proof is difficult to prove than the contrapositive proof.

Division

![[Screen Shot 2023-09-19 at 1.34.08 PM.png]]

We can turn $a | b$ into the statement $b = a c$ for some $c \in Z$ . ![[Screen Shot 2023-09-19 at 2.54.10 PM.png]]

In class practice

$\forall x \in Z$ , if $3 x - 7$ is even, then $x$ is odd.

$\forall x \in Z$ , if $x$ is even, then $3 x - 7$ is odd.

Proposition. Given $x \in Z$ , if $3 x - 7$ is even, then $x$ is odd.

Proof. Let $x \in Z$ . We work contrapositively. Assume that $x$ is even.
Thus $x = 2 k$ for some $k \in Z$ . We find

3 x - 7 = 3 (2 k) - 7 = 6 k - 7 = 2 (3 k - 4) + 1

is odd.
Since $3 k - 4$ is an integer, $3 x - 7$ is odd. $◻$

Direct Proof
Let $x \in Z$ . We work directly. Assume that $3 x - 7$ is even. Then $3 x - 7 = 2 j$ for some $j \in Z$ . Then $x = 2 j + 7 - 2 x = 2 (j - x + 3) + 1$ . Since $j - x + 3$

Proposition. Let $x \in Z$ . If $x^{2} - 6 x + 7$ is odd, then $x$ is even.

Proof. Let $x \in Z$ . We work contrapositively. Assume that $x$ is odd. Thus $x = 2 k + 1$ for some $k \in Z$ . Hence,

\begin{aligned} x^{2} - 6 x + 7 & = (2 k + 1)^{2} - 6 (2 k + 1) + 7 \\ = 4 k^{2} + 4 k + 1 - 12 k - 6 + 7 \\ = 4 k^{2} - 8 k + 2 \\ = 2 (2 k^{2} - 4 k + 1) \end{aligned}

Since $2 k^{2} - 4 k + 1$ is an integer, $x^{2} - 6 x + 7$ is even. $◻$

Proposition. Let $a, b \in Z$ . If $a ∣ b$ , then $a ∣ 2 b$ .

Proof. Let $a, b \in Z$ . We work directly. Assume that $a ∣ b$ .
Thus there exists $c \in Z$ such that $b = a c$ .
Thus $2 b = 2 a c = a (2 c)$ . Since $2 c$ is an integer, $a ∣ 2 b$ . $◻$

Proposition. Given $x \in Z$ , if $2 ∤ x$ , then $x$ is odd.

Proof. Let $x \in Z$ . We work contrapositively. Assume that $x$ is even. Thus $x = 2 k$ for some $k \in Z$ . Thus $2 ∣ x$ .

HW 7

Ben Finch

E 7.1
Proposition. Let $a \in Z$ . If $a^{2} + 3$ is odd, then $a$ is even.

Proof.
Let $a \in Z$ . We work contraposititvely. Assume $a$ is odd. Thus $a = 2 k + 1$ for some $k \in Z$ . We find

\begin{aligned} a^{2} + 3 & = (2 k + 1)^{2} + 3 \\ = 4 k^{2} + 4 k + 1 + 3 \\ = 2 (2 k^{2} + 2 k + 2) \end{aligned}

is even. $◻$

E 7.2
Proposition. Let $x, y \in Z$ . If $x y + y^{2}$ is even, then $x$ is odd or $y$ is even.

Proof. Let $x, y \in Z$ . We work contrapositively. Assume $x$ is even and $y$ is odd. Thus $x = 2 k$ for some $k \in Z$ and $y = 2 n + 1$ for some $n \in Z$ .
We find

\begin{aligned} x y + y^{2} & = 2 k (2 k + 1) + (2 n + 1)^{2} \\ = 4 k^{2} + 2 k + 4 n^{2} + 4 n + 1 \\ = 2 (2 k^{2} + k + 2 n^{2} + 2 n) + 1 \end{aligned}

is an odd integer. $◻$

E 7.3
Proposition. Let $s \in Z$ . $s$ is odd if and only if $s^{3}$ is odd.

Proof. Let $s \in Z$ . We first prove that $s^{3}$ is odd if $s$ is odd. We work directly. Assume $s$ is odd, thus $s = 2 k + 1$ for some $k \in Z$ . We find that

\begin{aligned} s^{3} & = (2 k + 1)^{2} \\ = 4 k^{2} + 4 k + 1 \\ = 2 (2 k^{2} + 2 k) + 1 \end{aligned}

is an odd integer.

We now prove that $s$ is odd if $s^{3}$ is odd. We work contrapositively. Assume $s$ is even, thus $s = 2 k$ for some $k \in Z$ . We find that

\begin{aligned} s^{3} & = (2 k)^{3} \\ = 8 k^{2} \\ = 2 (4 k^{2}) \end{aligned}

is an even integer. $◻$

E 7.4
In the student's proof, they use the converse instead of the contrapositive. The correct contrapositive would be:
If $x$ is odd, then $2 ∤ x$ .

Proof. Assume, contrapositively, that $x$ is odd. Thus, $x = 2 k + 1$ for some $k \in Z,$ which means $2$ does not divide $x$ . $◻$

E 7.5

Proposition: Let $a, b, c, d \in Z$ . If $a | c$ and $b | d$ , then $a b | c d$ .

Proof: Let $a, b, c, d \in Z$ . We work directly. Assume $a | c$ and $b | d$ . Thus $c = a x$ and $d = b y$ for some $x, y \in Z$ .

Now, $c d = (a x) (b y) = a b (x y)$ . Since $x y \in Z$ , we have $a b | c d$ . $◻$

E 7.6
If $a b ∤ c d$ , then $a ∤ c$ or $b ∤ d$ .

E 7.7
Proposition. Let $a \in Z$ . If $4 ∤ a^{2}$ , then $a$ is odd.

Proof. Let $a \in Z$ . We work contrapositively. The logically equivalent contrapositive is if $a$ is even, then $4 ∣ a^{2}$ .
Assume $a$ is even. Thus $a = 2 k$ for some $k \in Z$ . We find

a^{2} = (2 k)^{2} = 4 k^{2}

Which is a multiple of four. In other words, 4 is a divisor of 4 times some integer $k^{2}$ . Thus $4 ∣ a^{2} .$ $◻$

E 7.8
Proposition. Given $x \in Z$ , then $5 x - 1$ is even only if $x$ is odd.

Direct Proof.
Let $x \in Z$ .
We work directly.
Assume $x$ is even. Thus $x = 2 k$ for some $k \in Z$ We find

5 x - 1 = 5 (2 k) - 1 = 2 (5 k) - 1

is odd. $◻$

Contrapositive Proof.
Let $x \in Z$ .
We work contrapositively.
Assume $5 x - 1$ is odd. Thus $5 x - 1 = 2 k + 1$ for some $k \in Z$ . We find

\begin{aligned} 5 x - 1 & = 2 k + 1 \\ 5 x & = 2 k + 2 \\ x & = \frac{2 k + 2}{5} \end{aligned}

is even. $◻$