8 - Proof by cases

Proof By Cases

Some problems can be broken down into a finite set of cases:

Integers are even/odd
Real numbers can be rational or irrational.
etc

You can do some proofs by considering all possible cases separately

$Screen Shot 2023-09-21 at 11.58.19 AM.png$

Congruence

$Screen Shot 2023-09-21 at 12.05.53 PM.png$

In class practice

Proposition: If $x \in Z$ , then $x^{2} + x$ is even.

Proof: Let $x \in Z$ . We work directly. There are two cases.

Case 1: Assume that $x$ is even. Then $x = 2 k$ for some $k \in Z$ . Hence

\begin{aligned} x^{2} + x & = (2 k^{2}) + 2 k \\ = 2 (2 k^{2} + k) \end{aligned}

is even

Case 2: Assume that $x$ is odd. Then $x = 2 k + 1$ for some $k \in Z$ . Hence

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

is even.

In every case, $x^{2} + x$ is even. $◻ .$

Given $a, b \in C$ , we have $a b = 0$ iff $a = 0$ or $b = 0$ .
Proof, let $a, b \in C$ .
=> we work directly. Assume that $a b = 0$ . There are two cases.
Case 1. Assume that $a = 0$ .
Case 2. Assume that $a \neq 0$ . Then $b = \frac{0}{a}$ .

Proposition.
If $x \in Z$ , then $x^{3} \equiv x$ (mod 3).
Proof. Let $x \in Z$ . We work directly.
Case 1: Assume that $x = 3 k$ for some $k \in Z$ .
Then

\begin{aligned} x^{3} - x & = (3 k)^{3} - (3 k) \\ = 3 k [(3 k)^{2} - 1] \\ = 3 [k ((3 k)^{2} - 1)] \end{aligned}

Thus $x^{3} \equiv x$ (mod 3).

Case 2: Assume that $x = 3 k + 1$ for some $k \in Z$ .

Case 3: Assume that $x = 3 k + 2$ fro some $k \in Z$

HW 8

Ben Finch

E 8.1
Proposition:
Let $x, y \in Z$ . If $x$ and $y$ have the same parity, then $x^{2} + x y$ is even.

Proof. Let $x$ and $y$ be integers. We work directly. There are two natural cases.
Case 1:
Suppose $x$ and $y$ are odd. Thus $x = 2 k + 1$ , $y = 2 n + 1$ for some $k, n \in Z$ . We find

\begin{flalign} x^2 + xy &= (2k+1)^2 + (2n + 1)(2n + 1) \\ &= 4k^2 + 4k + 1 + 4n {#2}  + 4n + 1 \\ &= 2(2k^2 + 2k +2n^{2}+2n+1) \end{flalign}

is an even integer.

Case 2:
Suppose $x$ and $y$ are even. Thus $x = 2 k$ , $y = 2 n$ for some $k, n \in Z$ . We find

x^{2} + x y = (2 k)^{2} + 2 k (2 n) = 4 k^{2} + 4 k n = 2 (2 k^{2} + 2 k n)

is an even integer.

Thus, in every case $x^{2} + x y$ is even when $x$ and $y$ have the same parity. $◻$

E 8.2
Proposition. Let $a, b, c \in Z$ . If $a ∤ b c$ , then $a ∤ b$ and $a ∤ c$

Proof. Let $a, b, c \in Z$ . We work contrapositively. There are two natural cases.

Case 1:
Suppose $a | b$ . Thus $b = a l$ for some $l \in Z$ . So, $b c = a l c = a (l c)$ . Since $l c \in Z$ , we find $a | b c$ .

Case 2:
Suppose $a | c$ . Thus $c = a k$ for some $k \in Z$ . So, $b c = b a k = a (b k)$ . Since $b k \in Z$ we find $a | b c$ .

Thus, for all cases, If $a ∤ b c$ , then $a ∤ b$ and $a ∤ c .$ $◻$

E 8.3
a) Proposition.

If $x \in Z$ , either $x^{2} \equiv 0$ (mod 4) or $x^{2} \equiv 1$ (mod 4).

Proof:

Let $x \in Z$ . We work directly. There are two cases.

Case 1: Suppose that $x$ is even, thus $x = 2 k$ for some $k \in Z$ . Then

\begin{aligned} x^{2} - 0 & = (2 k)^{2} - 0 \\ = 4 k^{2} - 0 \\ = 4 [k^{2} - 0] \\ = 4 [k^{2}] . \end{aligned}

Thus, $4 | (x^{2} - 0)$ so $x^{2} \equiv 0 (m o d 4)$ .

Case 2: Suppose that $x$ is odd, thus $x = 2 k + 1$ for some $k \in Z$ . Then

\begin{aligned} x^{2} - 1 & = ((2 k + 1)^{2} - 1) \\ = (4 k^{2} + 4 k + 1 - 1) \\ = 4 [k^{2} + k] \\ = 4 [k (k + 1)] . \end{aligned}

Thus, $4 | (x^{2} - 1)$ so $x^{2} \equiv 1 (m o d 4)$ .

So, in all cases, $x^{2} \equiv 0 (m o d 4)$ or $x^{2} \equiv 1 (m o d 4)$ . $◻$

(b)
Proposition: If $x \in Z$ , then $4 | (x^{4} - x^{2})$ .

Proof:
Let $x \in Z$ . We have two cases. We work directly.

Case 1: Suppose $x$ is even, thus $x = 2 k$ for some $k \in Z$ . We find

\begin{aligned} x^{4} - x^{2} & = (x^{2}) (x^{2} - 1) \\ = (2 k)^{2} [(2 k)^{2} - 1] \\ = 4 k^{2} (4 k^{2} - 1) \\ = 4 [k^{2} (4 k^{2} - 1)] . \end{aligned}

Since $k^{2} (4 k^{2} - 1)$ is an integer, it follows that $4 | (x^{4} - x^{2})$ when $x$ is even.

Case 2: Suppose $x$ is odd, thus $x = 2 k + 1$ for some $k \in Z$ . We find

\begin{aligned} x^{4} - x^{2} & = (x^{2}) (x^{2} - 1) \\ = (x^{2}) (x - 1) (x + 1) \\ = (2 k + 1)^{2} (2 k + 1 - 1) (2 k + 1 + 1) \\ = (4 k^{2} + 4 k + 1) (2 k) (2 k + 2) \\ = (4 k^{2} + 4 k + 1) (4 k^{2} + 4 k) \\ = 16 k^{4} + 16 k^{3} + 16 k^{3} + 4 k^{2} + 4 k \\ = 4 (4 k^{4} + 8 k^{3} + k^{2} + k) \end{aligned}

Since $4 k^{4} + 8 k^{3} + k^{2} + k$ is an integer, it follows that $4 | (x^{4} - x^{2})$ when $x$ is odd.

Thus, in all cases, $4 | (x^{4} - x^{2})$ . $◻$

E 8.4
Proposition. Let $a, b, c, n \in Z$ . If $a \equiv b$ (mod $n$ ) and $b \equiv c$ (mod $n$ ), then $a \equiv c$ (mod $n$ ).

Proof. Let $a, b, c, n \in Z$ . We work directly.

Assume $a \equiv b$ (mod $n$ ) and $b \equiv c$ (mod $n$ ), hence $a - b = n k$ for some $k \in Z$ and $b - c = n j$ for some $j \in Z$ . We find

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

Since $k j$ is an integer, we have $a \equiv c$ (mod $n$ ). $◻$

If we know 11 ≡ −3 (mod 7) and −3 ≡ 4 (mod 7), can we say that 11 ≡ 4 (mod 7)?

Based on this proof, yes, we can say that $11 \equiv 4$ (mod $7)$ .

E 8.5
Proposition: For any $n \in Z$ , $3 | n$ if and only if $3 | n^{2}$ .

Proof:
(=>) We work directly. Assume $3 ∣ n$ . Thus $n = 3 k$ for some $k \in Z$ . We find

\begin{aligned} n^{2} & = (3 k^{2}) \\ = 9 k^{2} \\ = 3 (3 k^{2}) \end{aligned}

Since $3 k^{2}$ is an integer, we have $3 | n^{2}$ .

(<=) We work contrapositively. Assume $3 ∤ n$ . There are two cases:

Case 1:
Suppose $n = 3 k + 1$ for some $k \in Z$ . We find

\begin{aligned} n^{2} & = (3 k + 1)^{2} \\ = 9 k^{2} + 6 k + 1 \\ = 3 (3 k^{2} + 2 k) + 1 \end{aligned}

is not a multiple of three. Hence we have $3 ∤ n^{2}$ .

Case 2:
Suppose $n = 3 n + 2$ for some $n \in Z$ . We find

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

is not a multiple of three. Hence we have $3 ∤ n^{2}$ .

In both cases, if 3 does not divide $n$ , then $3$ does not divide $n^{2}$ . Therefore, we have shown that if $3 | n^{2}$ , then $3 | n$ .

In conclusion, we have proved that $3 | n$ if and only if $3 | n^{2}$ . $◻$

E 8.6
Proposition: Let $n \in Z$ , $3 | (2 n^{2} + 1)$ if and only if $3 ∤ n$ .

Proof:
Let $n \in Z$ .
(=>) We work contrapositively. Assume $3 ∣ n$ . Thus $n = 3 k$ for some $k \in Z$ . We find

\begin{aligned} 2 n^{2} + 1 & = 2 (3 k)^{2} + 1 \\ = 18 k^{2} + 1 \\ = 3 (6 k^{2}) + 1 \end{aligned}

is not a multiple of 3. Thus we have $3 ∤ (2 n^{2} + 1)$ .

(<=) We work directly. Assume $3 ∤ n$ . There are two cases:

Case 1:
Suppose $n = 3 k + 1$ for some $k \in Z$ . We find

\begin{aligned} 2 n^{2} + 1 & = 2 (3 k + 1)^{2} + 1 \\ = 2 (9 k^{2} + 6 k + 1) + 1 \\ = 18 k^{2} + 12 K + 3 \\ = 3 (6 k^{2} + 4 k + 1) \end{aligned}

is a multiple of 3. Thus we have $3 ∣ (2 n^{2} + 1)$ .

Case 2
Suppose $n = 3 k + 2$ for some $k \in Z$ . We find

\begin{aligned} 2 n^{2} + 1 & = 2 (3 k + 2)^{2} + 1 \\ = 2 (9 k^{2} + 12 k + 4) + 1 \\ = 18 k^{2} + 24 k + 8 + 1 \\ = 3 (6 k^{2} + 8 k + 3) \end{aligned}

is a multiple of 3. Thus we have $3 ∣ (2 n^{2} + 1)$ .

Thus we have $3 ∣ (2 n^{2} + 1)$ for all cases.

In conclusion, we have proved $3 | (2 n^{2} + 1)$ if and only if $3 ∤ n .$ $◻$

E 8.7
Proposition: Let $a, b, c, d, n \in Z$ . If $a \equiv b$ (mod $n$ ) and $c \equiv d$ (mod $n$ ), prove that $a c \equiv b d$ (mod $n$ ).

Proof:
Let $a, b, c, d, n \in Z$ . Assume $a \equiv b$ (mod $n$ ) and $c \equiv d$ (mod $n$ ). Thus we have $a - b = n k$ for some $k \in Z$ and $c - d = n j$ for some $j \in Z$ . We find

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

is a multiple of $n$ . Thus we have $a c \equiv b d$ (mod $n$ ). $◻$

What does this statement say if we take c = a and d = b?
Simplified, it would say if $a \equiv b$ (mod $n$ ), then $a^{2} \equiv b^{2}$ (mod $n$ ).

We know that $19 \equiv 5$ (mod 7). Do we then know $19^{2} \equiv 5^{2}$ (mod 7)? Yes.
How about $19^{3} \equiv 5^{3}$ (mod 7)? No, not based on this proof.

E 8.8
Proposition: Let $x, y \in R$ . Then $| x y | = | x | | y |$ .

Proof: We work directly. There are four cases.

Case 1
Suppose $x < 0$ and $y < 0$ . In this case, $| x | = - x, | y | = - y$ , and $| x y | = - (- x y) = x y$ . We find $| x | | y | = (- x) (- y) = x y$ . So, $| x | | y | = x y = | x y |$

Case 2
Suppose $x \geq 0$ and $y \geq 0$ . Then $| x | = x, | y | = y$ , and $| x y | = x y$ . So, $| x | | y | = x y = | x y |$ .

Case 3
Suppose $x < 0$ and $y \geq 0$ . Then $| x | = - x, | y | = y$ , and $| x y | = - x y$ . We find $| x | | y | = (- x) y = - x y$ . So, $| x | | y | = - x y = | x y |$ .

Case 4
Suppose $x \geq 0$ and $y < 0$ . This case is similar to case 3, thus $| x | | y | = | x y |$

Thus, in all cases, $| x y | = | x | | y |$ . $◻$

E 8.9

Proposition: $a^{2} \leq 1$ if and only if $- 1 \leq a \leq 1$

Proof. Let $a \in R$ . We work directly.
( $\Leftarrow$ ) Assume $- 1 \leq a \leq 1$ . There are two cases:

Case 1: Suppose $0 \leq a \leq 1$ :

We have $0 \leq a$ and $a \leq 1$ . From fact (1), if $a \leq 1$ and $0 < a$ , then $0 \leq a^{2} \leq 1$ .

Case 2: Suppose $- 1 \leq a < 0$ :

We have $- 1 \leq a$ and $a < 0$ . From fact (2), if $a \leq - 1$ and $- a > 0$ , then $a^{2} = (- a)^{2} \geq 1^{2} = 1$ .

Therefore, in both cases, the assertion $a^{2} \leq 1$ holds.

( $\Rightarrow$ ) Assume $a^{2} \leq 1$ . There are two cases:

Case 1 Suppose $a \geq 0$ :

Since $a^{2} \leq 1$ and $a \geq 0$ , it follows that $0 \leq a \leq 1$ .

Case 2 Suppose $a < 0$ :

Then $- a \geq 0$ and $(- a)^{2} = a^{2} \leq 1$ ; therefore, $- 1 \leq - a \leq 1$ .

Therefore, in both cases, the assertion $- 1 \leq a \leq 1$ holds.

Hence, $a^{2} \leq 1$ if and only if $- 1 \leq a \leq 1$ . $◻$