# Discrete Mathematics: An Active Approach to Mathematical Reasoning

## Section4.4Proof by Cases

In this section we will learn another proof technique, proof by cases. We will also see another big discrete math theorem, the Quotient-Remainder Theorem.
In the last section, we looked at the idea of divisibility. Remember, this is a relationship between two integers, not actual division. We will continue to focus on integers. One of the issues with division of integers is that if you divide two integers, you no longer necessarily have an integer. What if the only numbers we are allowed to use are integers? Can we still somehow think of division? Well, yes, this is in fact how you were probably introduced to division long ago. When you were first learning arithmetic, you only worked with integers.
Suppose you want to divide 10 by 5. This is easy, $$10\div 5=2\text{.}$$ But what if you want to divide 10 by 4? Now 4 does not “go evenly” into 10 (in other words, 4 does not divide 10). In this case, we get a remainder. In particular, 4 “goes into” 10 two times with a remainder of 2. Or, $$10\div 4$$ has quotient 2 and remainder 2.
OK, we want to formalize this idea of division, making sure we are only using integers. We know 5 divides 10, since $$10=5(2)\text{.}$$ Can we do the same sort of thing for 10 and 4? Almost. In this case, $$10=4(2)+2\text{.}$$
In general, given any integers $$n, d$$ with $$d\neq 0\text{,}$$ we can find integers $$q, r$$ with $$n=dq+r\text{.}$$ In general, $$q, r$$ are not unique. For example, $$10=4(1)+6\text{,}$$ and $$10=4(-2)+18\text{,}$$ and $$10=4(4)-6\text{.}$$ But as we noted, we want to think of $$r$$ as the remainder. If we are more specific about conditions on the remainder, then $$q$$ and $$r$$ are unique.
We say $$q$$ is the quotient and $$r$$ is the remainder when $$n$$ is divided by $$d\text{.}$$
We will see the existence part of the proof in Section 5.4.
This theorem is usually called the Division Algorithm. We won’t use that name here since it can be confusing. In particular, the Division Algorithm is not really an algorithm.
Some important observations: the remainder must be nonnegative. It can be 0. This is what happens when $$d\mid n\text{.}$$ Although $$n$$ can be any integer, we will limit $$d$$ to being positive. The Quotient-Remainder Theorem can be extended to any $$d\neq 0\text{,}$$ but we will just need $$d>0$$ in this class.

### Example4.4.2.Finding Quotients and Remainders.

Let $$n=15, d=7\text{,}$$ Find the quotient and remainder $$q, r\text{.}$$
$$15=7(2)+1; q=2, r=1$$
Let $$n=28, d=7\text{,}$$ Find the quotient and remainder $$q, r\text{.}$$
$$28=7(4)+0; q=4, r=0$$
Let $$n=9, d=12\text{,}$$ Find the quotient and remainder $$q, r\text{.}$$
$$9=12(0)+9; q=0, r=9$$
Let $$n=-17, d=5\text{,}$$ Find the quotient and remainder $$q, r\text{.}$$
$$-17=5(-4)+3; q=-4, r=3$$
Let $$n=0, d=7\text{,}$$ Find the quotient and remainder $$q, r\text{.}$$
$$0=7(0)+0; q=0, r=0$$

### Activity4.4.1.

For the given $$n$$ and $$d\text{,}$$ find $$q$$ and $$r$$ as in the Quotient-Remainder Theorem.

#### (a)

$$n=20$$ and $$d=8$$

#### (b)

$$n=45$$ and $$d=9$$

#### (c)

$$n=8$$ and $$d=12$$

#### (d)

$$n=-15$$ and $$d=7$$
In computer science it is useful to have functions that give the quotient (div) and remainder (mod). The common notation is
\begin{equation*} n \text{ div } d=q; \end{equation*}
\begin{equation*} n \text{ mod } d=r. \end{equation*}
For example, $$20 \text{ div } 3=6$$ and $$20 \text{ mod } 3=2\text{.}$$
We can use the Quotient-Remainder Theorem to find representations of the integers by grouping integers with the same remainder.
For example, if we let $$d=2\text{,}$$ what are the possible remainders? In this case, $$r=0$$ or $$r=1\text{.}$$ Thus, there are two possible forms for $$n\text{:}$$ $$n=2q+0$$ or $$n=2q+1\text{.}$$ We see that these are the two forms corresponding to $$n$$ being even or odd. Now, as a corollary of the Quotient-Remainder, we have that every integer must be even or odd.
We can use the Quotient-Remainder Theorem to get other forms, as well. For example, if $$d=4\text{,}$$ the possible forms are $$n=4q+0, n=4q+1, n=4q+2$$ or $$n=4q+3\text{.}$$ We can use these forms to get different cases for the integers.

### Proof by Cases.

To prove $$\forall x\in D, P(x)$$ by cases,
1. Break $$D$$ into smaller subsets, $$D_1, D_2, \ldots D_k\text{.}$$ Make sure every element in $$D$$ is in one of the subsets.
2. Prove each case separately. Make sure you state each case clearly.
Case 1: $$x\in D_1$$
Proof of $$P(x)\text{.}$$
Case 2: $$x\in D_2$$
Proof of $$P(x)\text{.}$$
etc.
3. Conclude $$P(x)$$ holds for all $$x\in D\text{.}$$
In choosing your subsets, make sure you cover all the elements of $$D\text{.}$$ Your subsets do not need to be similar. For example, one set could be all the nonzero integers and the other just the set with 0.
We saw an example in Theorem 4.3.5, where we broke $$D$$ into the set of primes and the set of composites.

### Example4.4.3.Proof by Cases.

Prove given any two consecutive integers, one is even and one is odd.

#### Proof.

Let $$n$$ and $$n+1$$ be consecutive integers.
Case 1: Let $$n$$ be even. Then $$n=2k$$ for some $$k\in\mathbb{Z}\text{.}$$ Then $$n+1=2k+1$$ for $$k\in\mathbb{Z}\text{.}$$ Hence $$n+1$$ is odd.
Case 2: Let $$n$$ be odd. Then $$n=2k+1$$ for some $$k\in\mathbb{Z}\text{.}$$ Then $$n+1=2k+2=2(k+1)$$ for $$k+1\in\mathbb{Z}\text{.}$$ Hence $$n+1$$ is even.
Thus, for any two consecutive integers, one is even and one is odd.

### Activity4.4.2.

Prove for all integers $$m$$ and $$n\text{,}$$ $$m+n$$ and $$m-n$$ are either both even or both odd.
Hint.
There are four cases, depending on whether $$m$$ and $$n$$ are even or odd.

### Activity4.4.3.

Recall the absolute value function is defined as
\begin{equation*} |x|= \begin{cases} x, \amp\text{if $x\geq 0$;}\\ -x \amp\text{if $x<0$.} \end{cases} \end{equation*}
Prove for all $$x\in \mathbb{R}\text{,}$$ $$|x|=|-x|\text{.}$$ What would appropriate cases be?

### Example4.4.4.More Cases.

Prove that the square of any odd integer has the form $$8m+1$$ for some $$m\in \mathbb{Z}\text{.}$$
First, let’s try to just prove this directly.
Let $$n$$ be odd. Then $$n=2k+1, k\in\mathbb{Z}\text{.}$$ Thus, $$n^2=(2k+1)^2=4k^2+4k+1\text{.}$$
It is not clear $$n^2$$ has the form $$8m+1\text{.}$$
If we try using some cases, we may get a bit more to work with. We know any integer has the form $$4k, 4k+1, 4k+2,$$ or $$4k+3\text{.}$$ But only $$4k+1$$ and $$4k+3$$ are odd. Thus, we can try cases with $$n=4k+1$$ and $$n=4k+3\text{.}$$

#### Proof.

Let $$n$$ be odd.
Case 1: Let $$n=4k+1$$ for some $$k\in\mathbb{Z}\text{.}$$ Then
\begin{align*} n^2&=(4k+1)^2\\ &=16k^2+8k+1\\ &=8(2k^2+k)+1 \end{align*}
for some $$2k^2+k\in\mathbb{Z}\text{.}$$ Let $$m=2k^2+k\text{.}$$ Then $$n$$ has the form $$8m+1, m\in \mathbb{Z}\text{.}$$
Case 2: Let $$n=4k+3$$ for some $$k\in\mathbb{Z}\text{.}$$ Then
\begin{align*} n^2&=(4k+3)^2\\ &=16k^2+24k+9\\ &=8(2k^2+3k)+9\\ &=8(2k^2+3k)+8+1\\ &=8(2k^2+3k+1)+1 \end{align*}
for some $$2k^2+3k+1\in\mathbb{Z}\text{.}$$ Let $$m=2k^2+3k+1\text{.}$$ Then $$n$$ has the form $$8m+1, m\in \mathbb{Z}\text{.}$$
Thus, any odd integer has the form $$8m+1\text{.}$$
Note, what this theorem really says is that the square of an odd integer must have remainder 1 when divided by 8. That might be a little surprising.

### Activity4.4.4.

Use the Quotient Remainder Theorem to find the possible forms of an integer when $$d=3\text{.}$$
Hint.
What are the possible values for $$r\text{?}$$

### Activity4.4.5.

Prove the product of any two consecutive integers has the form $$3k$$ or $$3k+2$$ for some integer $$k\text{.}$$
Hint.
Use the cases in Activity 4.4.4.

#### 1.

Find the quotient and remainder if $$n=34, d=6\text{.}$$
Quotient:, Remainder:

#### 2.

Find the quotient and remainder if $$n=34, d=2\text{.}$$
Quotient:, Remainder:

#### 3.

Find the quotient and remainder if $$n=-34, d=6\text{.}$$
Quotient:, Remainder:

#### 4.

Find the quotient and remainder if $$n=4, d=10\text{.}$$
Quotient:, Remainder:

#### 5.

Find the quotient and remainder if $$n=-40, d=12\text{.}$$
Quotient:, Remainder:

#### 6.

Review: Give the negation of $$\forall x\in D, P(x)\rightarrow Q(x)\text{.}$$

#### 7.

Review: Give the contrapositive of $$\forall x\in D, P(x)\rightarrow Q(x)\text{.}$$

### ExercisesExercises

#### 1.

For the given $$n$$ and $$d\text{,}$$ find $$q$$ and $$r$$ such that $$n=dq+r$$ with $$0\leq r<d$$ (as in the Quotient-Remainder Theorem).
1. $$n=36$$ and $$d=40$$
2. $$n=-45$$ and $$d=11$$

#### 2.

Evaluate $$28$$ div $$5$$ and $$28$$ mod $$5\text{.}$$

#### 3.

Suppose $$d$$ is a positive integer and $$n$$ is any integer. If $$d\mid n\text{,}$$ what is the remainder when the Quotient-Remainder Theorem is applied to $$n$$ with divisor $$d\text{?}$$

#### 4.

Prove for all integers $$n\text{,}$$ $$n^2-n+3$$ is odd.

#### 5.

Let $$n\in \mathbb{Z}\text{.}$$ Prove if $$n$$ has remainder 3 when divided by 5, then $$n^2$$ has remainder 4 when divided by 5.
Hint.
Think Quotient-Remainder Theorem.

#### 6.

Let $$a, b\in \mathbb{Z}\text{.}$$ Prove if $$a$$ has remainder 5 when divided by 7 and $$b$$ has remainder 6 when divided by 7, then $$ab$$ has remainder 2 when divided by 7.
Hint.
Think Quotient-Remainder Theorem.

#### 7.

Prove the square of of any integer has the form $$4k$$ or $$4k+1$$ for some integer $$k\text{.}$$