1.5 Proof by contradiction — Practise

Work through these on your own. Write the assumption first, and say which sentence it conflicts with before you write your conclusion. The last item asks you to choose the method: say which one fits and why before you start.

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

In the proof that $\sqrt{2}$ is irrational, the number $a$ is even, so $a = 2k$ for a whole number $k$ . Show that $a^2$ is a multiple of $4$ .
In the same proof, $4k^2 = 2b^2$ . Show that $b^2 = 2k^2$ .
Suppose $b$ is odd, so $b = 2k + 1$ . Show that $b^2$ is odd.
In Euclid's proof that there are infinitely many primes, let $N = 2 \times 3 \times 5 \times 7 + 1$ . Work out $N$ .
For $N = 2 \times 3 \times 5 \times 7 + 1 = 211$ , show that $N$ leaves remainder $1$ when divided by each of $2$ , $3$ , $5$ and $7$ .
Show that $211$ is prime by testing the primes up to $\sqrt{211}$ .
In the proof that $\sqrt{2}$ is irrational, show that the number $2(2k^2 + 2k) + 1$ leaves remainder $1$ when divided by $2$ .
Suppose $x > 0$ is the smallest positive real number. Show that $x/2$ is positive and that $x/2 < x$ .
Suppose $r$ is rational and $i$ is irrational, and suppose $r + i$ is rational. Show that $i = (r + i) - r$ .
Suppose $M$ is the greatest even number. Show that $M + 2$ is even and that $M + 2 > M$ .
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) Decide whether the claim "for all real $x$ and $y$ , if $x^2 > y^2$ then $x > y$ " is true.

Answers and concise solutions

1. Show $a^2$ is a multiple of $4$

Answer: Substitute $a = 2k$ into $a^2$ : $a^2 = (2k)^2 = 4k^2$ . This has a factor $4$ , so $a^2$ is a multiple of $4$ .

2. Solve for $b^2$

Answer: Divide both sides of $4k^2 = 2b^2$ by $2$ : $2k^2 = b^2$ , so $b^2 = 2k^2$ . This says $b^2$ is even, so $b$ is even too.

3. Show $b^2$ is odd

Answer: Expand: $b^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$ . This is one more than a multiple of $2$ , so $b^2$ is odd. But $b^2 = 2k^2$ is even. An odd number cannot equal an even number, so the assumption is false.

4. The value of $N$

Answer: $2 \times 3 \times 5 \times 7 = 210$ , so $N = 210 + 1 = 211$ .

5. The four remainders

Answer: Each of $2$ , $3$ , $5$ and $7$ divides the product $2 \times 3 \times 5 \times 7$ , so each leaves remainder $0$ for that product and remainder $1$ for $N$ . A number that leaves remainder $1$ cannot be a multiple of that prime, so none of the four primes divides $N$ .

6. The factor check

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

7. The remainder

Answer: The first part, $2(2k^2 + 2k)$ , is a multiple of $2$ , so its remainder is $0$ . Adding $1$ changes the remainder to $1$ . The number is odd, and it cannot equal $2k^2$ , which is even.

8. Compare $\frac{x}{2}$ with $x$

Answer: Because $x > 0$ , the number $x/2$ is also positive. And $x/2 < x$ , because dividing a positive number by $2$ makes it smaller. So $x/2$ is a smaller positive real number, which contradicts the claim that $x$ is the smallest. The assumption is false.

9. Make $i$ the subject

Answer: Rearrange $r + i = q$ , where $q$ is rational. Then $i = q - r$ . The difference of two rational numbers is rational, so $i$ would be rational. But $i$ is irrational, so $i$ cannot be both. The assumption that $r + i$ is rational is false.

10. The larger even number

Answer: The number $M + 2$ is even, because it is the sum of two even numbers. It is also greater than $M$ . So $M + 2$ is a larger even number than $M$ , which contradicts the claim that $M$ is the greatest. The assumption is false, so there is no greatest even number.

11. Which method, and why

Answer: (a) Deduction. Factorise $n^2 + n = n(n + 1)$ ; consecutive numbers include one even number, so the product is even. (b) Counter example. Take $x = -3$ and $y = 2$ : $x^2 = 9 > 4 = y^2$ , yet $x = -3 < 2 = y$ . The claim is false. Nothing here needs contradiction: contradiction is for a statement you believe is true but cannot reach directly, and a counter example is quicker when a "for all" claim is false.