1.3 Proof by exhaustion — Practise

Work through these on your own. For every item, write the list of cases first, then check them. Say in words why the list is complete, or explain what is missing from a list that is not. The last item asks you to choose the method: say which one fits and why before you calculate.

Both the questions and the answers below come from a set that is checked by computer every time the book is built.

Show that every whole number from $1$ to $6$ divides $60$ .
Show that every even number from $4$ to $20$ is the sum of two prime numbers.
Prove by exhaustion that $n^2 + n$ is even for $n = 0, 1, 2, 3, 4$ .
Show that $7$ is prime by testing every whole number from $2$ to $6$ .
Show that for $n = 1, 2, 3, 4, 5$ , the value of $n^2 + 1$ is never a multiple of $3$ .
Check the claim " $n^2 + n + 41$ is prime" for $n = 0, 1, 2, 3$ .
Show that $91$ is not prime by testing the primes whose squares are at most $91$ .
Show that $97$ is prime by testing the primes up to $\sqrt{97}$ .
Show that $n^3 - n$ is a multiple of $6$ for $n = 1, 2, 3, 4$ .
The claim " $n^2 + n + 41$ is prime" holds for every whole number $n$ from $0$ to $39$ . Explain why this does not prove the claim.
Choose the method for each part before you answer, then explain your choice. (a) Prove that $n^2 + n$ is even for every whole number $n$ . (b) Prove that every whole number from $1$ to $5$ divides $60$ .

Answers and concise solutions

1. Each case

Answer: $60 = 1 \times 60$ , $2 \times 30$ , $3 \times 20$ , $4 \times 15$ , $5 \times 12$ and $6 \times 10$ . Every case leaves remainder $0$ , and there are only six cases to check.

2. Each case

Answer: $4 = 2 + 2$ , $6 = 3 + 3$ , $8 = 3 + 5$ , $10 = 5 + 5$ , $12 = 5 + 7$ , $14 = 7 + 7$ , $16 = 5 + 11$ , $18 = 7 + 11$ , $20 = 7 + 13$ . The addends $2$ , $3$ , $5$ and $7$ are prime; $\sqrt{11}$ and $\sqrt{13}$ lie between $3$ and $5$ , so checking $2$ and $3$ is enough to show that $11$ and $13$ are prime too. Every even number in the list is covered, so the cases exhaust the range.

3. Each case

Answer: The values are $0$ , $2$ , $6$ , $12$ and $20$ . Each is a multiple of $2$ . The five cases exhaust $n = 0$ to $4$ , so the statement is proved for that finite set.

4. Each case

Answer: None of $2$ , $3$ , $4$ , $5$ or $6$ divides $7$ , so $7$ has no factor except $1$ and itself: $7$ is prime.

5. Each case

Answer: The values are $2$ , $5$ , $10$ , $17$ and $26$ . Their remainders on division by $3$ are $2$ , $2$ , $1$ , $2$ and $2$ . None is $0$ , so none of the five values is a multiple of $3$ .

6. The four values

Answer: The values are $41$ , $43$ , $47$ and $53$ , and all four are prime. The check covers four values only; it does not prove the claim for every $n$ .

7. The factor found

Answer: $91 = 7 \times 13$ , so $91$ is not prime. The prime $7$ is found by testing $2$ , $3$ , $5$ and then $7$ , and one factor is enough to settle the case.

8. Each case

Answer: The primes up to $\sqrt{97} \approx 9.85$ are $2$ , $3$ , $5$ and $7$ . None of them divides $97$ . If $97$ had a factor, it would have a prime factor no larger than $\sqrt{97}$ , so no factor exists: $97$ is prime.

9. Each case

Answer: The values are $0$ , $6$ , $24$ and $60$ . Each is a multiple of $6$ , and the list covers $n = 1$ to $4$ .

10. The gap in the argument

Answer: The value at $n = 39$ is $1601$ , and $1601$ is prime, so the forty cases $n = 0$ to $39$ are all correct. But the claim is about every whole number. Exhaustion proves a statement only when the list of cases is the whole domain, and here it is not: there are infinitely many values of $n$ . The claim is in fact false.

11. Which method, and why

Answer: (a) Deduction. The domain is every whole number, so a list of cases can never cover it. Factorise $n^2 + n = n(n + 1)$ ; the two factors are consecutive, so one is even, and the product is even. (b) Exhaustion. The domain is the five numbers $1$ to $5$ , a finite list. Check each: $60 = 1 \times 60 = 2 \times 30 = 3 \times 20 = 4 \times 15 = 5 \times 12$ . The method follows from the size of the domain: infinite needs an argument, finite can be checked.