1.3 Proof by exhaustion — Practise with help

1. $20 = 3 \times 6 + 2$, so the remainder is $2$.
2. $2$, $3$, $5$, $7$.
3. $36$.

Write one multiplication or division for each number in the list, and look for a remainder that is not zero.

Start with $30 = 1 \times 30$ and work upwards through $2$, $3$, $4$ and $5$.

Look at the case $4$: $30 \div 4 = 7$ remainder $2$, so $4$ does not divide $30$. The statement is false, and the single case $4$ is a counter example.

First work out which prime numbers have squares at most $89$. Those are the only ones you need to test.

Work out $9^2$ and $10^2$, then test $89$ by $2$, $3$, $5$ and $7$.

Since $9^2 = 81 \leq 89$ and $10^2 = 100 > 89$, test the primes $2$, $3$, $5$ and $7$.

None divides $89$, so $89$ has no prime factor. Therefore $89$ is prime.

Work out the four values first. Then test each one for prime factors, using the primes up to its square root.

The four values are $41$, $43$, $47$ and $53$. For each, test the primes $2$, $3$, $5$ and $7$.

The values are

Each is odd, so none is divisible by $2$. The digit sums are $5$, $7$, $11$ and $8$, none of which is a multiple of $3$, so none is divisible by $3$. None ends in $0$ or $5$, so none is divisible by $5$. Checking the four values against $7$ gives remainders $6$, $1$, $5$ and $4$ for $41$, $43$, $47$ and $53$ in turn, and none is zero.

The four cases cover $n = 0$ to $3$, so the statement is proved for those values. It is not proved for every whole number $n$.

Work out each value, then divide by $6$ and look at the remainder. You need the remainder to be $0$ in all four cases.

The values are $0$, $6$, $24$ and $60$. Divide each by $6$.

Each value is a multiple of $6$. The four cases cover $n = 1$ to $4$, so the statement is proved for that finite list.

Do not divide in your head. Write each division with its remainder, so the reader can check it.

Work down the list from $2$: $13 = 2 \times 6 + 1$, then continue.

Every remainder is non-zero, so none of the five numbers divides $13$. The only smaller whole numbers left are $1$ and, trivially, $13$ itself. Since no whole number between $2$ and $12$ divides $13$, the number $13$ is prime.

Compare the size of the list with the size of the domain. How many whole numbers are there?

Say what a complete exhaustion proof needs: a list that contains every case. Then check whether this list does.

The domain is every whole number, and there are infinitely many whole numbers. The list $n = 0$ to $39$ has forty entries, so it leaves out infinitely many cases. Exhaustion proves a statement only when the list covers the whole domain. One value that is not on the list, $n = 40$, gives $1681 = 41 \times 41$, so the claim fails. A finite check is evidence; only a complete list, or a general argument, is a proof.