Proof by contradiction: the method and the irrationality of √2

Highlights only0 highlighted

Pure Mathematics P4 (WMA14/01) is the second A Level pure paper, and proof has been part of every recent sitting.

On each of the three recent P4 papers studied for these notes, one question (or one part of a question) asked for a proof by contradiction, and it was worth 4 marks every time: twice as a question on its own and once as part (b) of a binomial question.

Those 4 marks are some of the hardest on the paper, because the examiners report that even the opening line is often wrong.

P4 assumes everything in P1, P2 and P3, and this section leans on two P2 ideas: what a proof is, and how to write odd and even numbers as $2k + 1$ and $2k$ .

The idea: show that the opposite is impossible

Most proofs you met in P2 go forwards.

You start from facts you know and reason step by step until you reach the statement.

Proof by contradiction goes the other way round.

You suppose the statement is false, reason correctly from that supposition, and arrive at something that cannot possibly be true.

Since correct reasoning from a true starting point can never produce an impossibility, the starting point must have been false.

So the statement was true all along.

You already use this kind of reasoning outside mathematics.

A detective says: "Suppose the butler did it.

Then he was in the library at nine.

But at nine he was on a train, seen by forty passengers.

So the butler did not do it."

The detective never proves directly who did it; she shows one possibility leads to an impossibility and rules it out.

The method works because a mathematical statement is either true or false, with no third option.

If "the statement is false" leads to nonsense, then "the statement is true" is the only option left.

When to reach for it

Proof by contradiction is the natural tool when the statement says something cannot happen or does not exist:

"there are no integers $a$ and $b$ such that ...";

" $\sqrt{2}$ is irrational" (it cannot be written as a fraction);

"there is no largest prime" (the list of primes does not end);

"these two curves never meet".

A direct proof of "there is no such thing" is hard, because you would have to check every case.

Assuming there is such a thing gives you an object to work with: a fraction $\frac{a}{b}$ , a largest prime $p$ , a point where the curves meet.

Then you show that object leads to an impossibility.

Step 1 is the negation: getting the assumption right

Everything depends on assuming exactly the opposite of the statement, no more and no less.

Assume too little and the contradiction does not prove the claim; assume something else and the proof is about a different statement.

The examiners' reports say this is where most proofs go wrong, and a mark scheme awards nothing until the assumption is correct.

Statement to prove

The assumption (its negation)

$\sqrt{2}$ is irrational

$\sqrt{2}$ is rational, so $\sqrt{2} = \dfrac{a}{b}$ for integers $a, b$ with $b \neq 0$

There are no integers $a, b$ with $6a + 15b = 1$

There are integers $a, b$ with $6a + 15b = 1$

For every integer $n$ , if $n^2$ is even then $n$ is even

There is an integer $n$ such that $n^2$ is even and $n$ is odd

For all real $x$ , $x^2 + 1 \geq 2x$

There is a real $x$ for which $x^2 + 1 < 2x$

There are infinitely many primes

There are only finitely many primes

Three patterns are worth learning.

"For all" becomes "there is at least one". To deny that every integer has a property, you only need one integer without it.

"If P then Q" becomes "P and not Q". The statement "if $n^2$ is even then $n$ is even" is false only when $n^2$ is even and yet $n$ is odd. Assuming " $n^2$ is odd" or " $n$ is odd" alone negates something else.

" $\geq$ " becomes " $<$ ", and " $>$ " becomes " $\leq$ ". The negation of a non-strict inequality is strict, and the other way round. A proof that negates $\geq$ as $\leq$ has assumed the wrong thing.

Proof: if $n^2$ is even, then $n$ is even

This small result is the key to the proof that $\sqrt{2}$ is irrational, so it comes first.

Assume there is an integer $n$ such that $n^2$ is even and $n$ is odd.

Since $n$ is odd, $n = 2k + 1$ for some integer $k$ .

Then

n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1.

Since $2k^2 + 2k$ is an integer, $n^2$ is one more than an even number, so $n^2$ is odd.

This contradicts the assumption that $n^2$ is even.

So there is no such $n$ : for every integer $n$ , if $n^2$ is even then $n$ is even.

Notice the letter $k$ .

The odd number is written $2k + 1$ with a new letter.

Writing " $n = 2n + 1$ " reuses $n$ for two different things, and the examiners record that this slip costs the last mark.

Proof: $\sqrt{2}$ is irrational

This is a named proof you must know, and it is the model for many others, so learn its shape.

Assume $\sqrt{2}$ is rational.

Then $\sqrt{2} = \dfrac{a}{b}$ , where $a$ and $b$ are integers, $b \neq 0$ , and the fraction is in its lowest terms, so $a$ and $b$ have no common factor other than 1.

Every fraction can be cancelled down to lowest terms, so this costs nothing.

Squaring, $2 = \dfrac{a^2}{b^2}$ , so $a^2 = 2b^2$ .

So $a^2$ is even, and by the result above, $a$ is even.

Write $a = 2c$ for an integer $c$ .

Then $4c^2 = 2b^2$ , so $b^2 = 2c^2$ .

So $b^2$ is even, and therefore $b$ is even.

Now $a$ and $b$ are both even, so they have the common factor 2.

This contradicts the fraction being in lowest terms.

So $\sqrt{2}$ is not rational: $\sqrt{2}$ is irrational.

Why does "lowest terms" matter so much?

It is the fact the contradiction breaks.

Without it, finding that $a$ and $b$ are both even would be no problem at all: $\frac{4}{6}$ has an even top and bottom and is a perfectly good fraction.

The phrase is not decoration; it is the trap the proof is built to spring.

Why $\sqrt{4}$ does not fall into the same trap

A good test of understanding is to run the same argument on a number that is rational.

Try $\sqrt{4} = \frac{a}{b}$ in lowest terms.

Then $a^2 = 4b^2$ , so $a^2$ is even, so $a$ is even: $a = 2c$ .

Then $4c^2 = 4b^2$ , so $b^2 = c^2$ .

Nothing forces $b$ to be even, so no contradiction appears, and the argument stops.

That is exactly what should happen, since $\sqrt{4} = \frac{2}{1}$ .

The proof for $\sqrt{2}$ works because the 2 in $a^2 = 2b^2$ survives to make $b^2 = 2c^2$ even.

The shape of every proof by contradiction

1. Assume the negation, in words, with every condition in it (integers, lowest terms, the interval for $x$ ).

2. Work from the assumption with correct algebra, writing odd and even numbers or fractions with new letters.

3. Reach a statement that is impossible, and say why it is impossible (it contradicts the lowest-terms condition; an even number cannot equal an odd one; a square cannot be negative).

4. Conclude: "this contradicts the assumption, so [the original statement] is true."

The four parts match the four marks a P4 proof usually carries.

How the marks work

M1: a correct method applied to this question. dM1, ddM1: method marks that need the M marks before them.

A1: a correct line or answer, which needs its M mark. A1*: the last mark of a "show that" or a proof, reached with no errors; in a proof by contradiction it needs the reason, the contradiction and the conclusion. A1cso: correct solution only.

B1: an independent mark, often the assumption in a proof or a stated value. ft: follow through from your own earlier value.

awrt: any answer which rounds to the value given. isw: ignore subsequent working. oe: or equivalent.

Misread: copy a number wrongly and keep the question's character, and you lose two A or B marks in that part, not everything.

Where a question says solutions relying entirely on calculator technology are not acceptable, a bare answer scores nothing.

Key terms

Proof by contradiction: a proof that assumes the statement is false and shows that this assumption leads to a contradiction, so the statement must be true.

Rational number: a number that can be written as $\dfrac{a}{b}$ , where $a$ and $b$ are integers and $b \neq 0$ .

Irrational number: a real number that cannot be written as $\dfrac{a}{b}$ with $a$ and $b$ integers and $b \neq 0$ .

Lowest terms: a fraction $\dfrac{a}{b}$ is in lowest terms when $a$ and $b$ have no common factor other than 1.

Negation: the statement that is true exactly when the original statement is false.

The wording to learn: "Proof by contradiction", with the guidance "Including proof of the irrationality of $\sqrt{2}$ and the infinity of primes, and application to unfamiliar proofs."

Worked example 1: a parity result

Use proof by contradiction to prove that, for every integer $n$ , if $n^3$ is even then $n$ is even.

(4)

1. Assume there is an integer $n$ such that $n^3$ is even and $n$ is odd. B1 (assumption in words, both parts of the claim negated)

2. $n$ odd, so $n = 2k + 1$ for some integer $k$ , and $n^3 = (2k + 1)^3 = 8k^3 + 12k^2 + 6k + 1$ M1 (expands with a new letter)

3. $n^3 = 2(4k^3 + 6k^2 + 3k) + 1$ , which is odd since $4k^3 + 6k^2 + 3k$ is an integer A1

4. This contradicts $n^3$ being even, so for every integer $n$ , if $n^3$ is even then $n$ is even. A1*

Answer: proved.

The check on the algebra: at $k = 1$ , $n = 3$ and $n^3 = 27 = 2(4 + 6 + 3) + 1$ .

Worked example 2: hence an irrational cube root

Hence, using the result of Worked example 1, prove by contradiction that $\sqrt[3]{2}$ is irrational.

(4)

1. Assume $\sqrt[3]{2}$ is rational, so $\sqrt[3]{2} = \dfrac{a}{b}$ with $a, b$ integers, $b \neq 0$ , and $a$ and $b$ having no common factor other than 1 B1

2. Cubing: $a^3 = 2b^3$ , so $a^3$ is even and, by Worked example 1, $a$ is even; let $a = 2c$ M1

3. $8c^3 = 2b^3$ , so $b^3 = 4c^3 = 2(2c^3)$ , which is even, so $b$ is even A1

4. Then $a$ and $b$ have the common factor 2, which contradicts the fraction being in lowest terms. So $\sqrt[3]{2}$ is irrational. A1*

Answer: proved.

The "hence" is used in two places: once for $a$ and once for $b$ .

Without the earlier result you would have to prove " $a^3$ even means $a$ even" again inside this proof.

Worked example 3: a "there are no integers" proof (exam length)

In this question you must show all stages of your working. Solutions relying entirely on calculator technology are not acceptable.

Use proof by contradiction to prove that there are no positive integers $x$ and $y$ such that $x^2 - y^2 = 10$ .

(4)

1. Assume there are positive integers $x$ and $y$ with $x^2 - y^2 = 10$ . B1

2. Then $(x - y)(x + y) = 10$ . Since $x + y > 0$ and the product is positive, $x - y > 0$ , so $x - y$ and $x + y$ are positive integers with $x - y < x + y$ whose product is 10 M1

3. So ( $x - y = 1$ and $x + y = 10$ ) or ( $x - y = 2$ and $x + y = 5$ ). In each pair one number is odd and one is even. But $(x + y) - (x - y) = 2y$ is even, so $x - y$ and $x + y$ are both even or both odd A1

4. Neither pair has the same parity, which is a contradiction. So there are no positive integers $x$ and $y$ with $x^2 - y^2 = 10$ . A1*

Answer: proved.

The key fact is the parity link: two integers that differ by an even number $2y$ are both odd or both even.

A list of trial values ( $x = 4, y = \ldots$ ) is not a proof, because it can never cover every integer.

Exam tip

Write the assumption as a full sentence that starts "Assume" (or "Suppose") and contains every condition in the claim: the type of number, "in lowest terms", and both halves of an "if ...

then ..."

statement.

The first mark goes on that sentence, and without it the rest of a P4 proof scores nothing.

End with a sentence that names what is contradicted and states the original claim as proved.

Common mistakes

Negating the wrong statement. For "if $n^2$ is even then $n$ is even", assume " $n^2$ is even and $n$ is odd". Assuming "both are odd" or just " $n$ is odd" proves nothing about the claim. The fix: write the claim, then change it to "the hypothesis holds and the conclusion fails".

Reusing a letter. " $n$ is odd, so $n = 2n + 1$ " says $n = -1$ . Use a new letter: $n = 2k + 1$ .

Forgetting lowest terms. Without "no common factor other than 1" in the assumption, finding both $a$ and $b$ even is not a contradiction.

No reason and no conclusion. "Contradiction." on its own loses the A1*. Say what is contradicted and why, then state the result.

Check your understanding

1. Write down the negation of each statement.
(a) For every positive integer $n$ , $n^2 + n$ is even. (1)
(b) There is no largest even number. (1) Total [2]

2. (a) Use proof by contradiction to prove that, for every integer $n$ , if $n^2$ is a multiple of 3 then $n$ is a multiple of 3. (4)
(b) Hence use proof by contradiction to prove that $\sqrt{3}$ is irrational. (4) Total [8]

3. Use proof by contradiction to prove that if $x$ is irrational then $\dfrac{1}{x}$ is irrational. (4) Total [4]

4. A student tries to prove that $\sqrt{4}$ is irrational by copying the proof for $\sqrt{2}$ . They assume $\sqrt{4} = \dfrac{a}{b}$ in lowest terms and reach $b^2 = c^2$ . State, with a reason, why the student cannot reach a contradiction. (2) Total [2]

5. Use proof by contradiction to prove that there are no integers $a$ and $b$ such that $6a + 15b = 1$ . (4) Total [4]

6. Use proof by contradiction to show that the sum of a rational number and an irrational number is irrational. (4) Total [4]

Answers

1. (a) There is a positive integer $n$ for which $n^2 + n$ is odd. B1
(b) There is a largest even number. B1

2. (a) Assume there is an integer $n$ such that $n^2$ is a multiple of 3 and $n$ is not a multiple of 3 B1; then $n = 3k + 1$ or $n = 3k + 2$ for an integer $k$ , giving $n^2 = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1$ or $n^2 = 9k^2 + 12k + 4 = 3(3k^2 + 4k + 1) + 1$ M1; in both cases $n^2$ leaves remainder 1 on division by 3, so is not a multiple of 3 A1; this contradicts the assumption, so if $n^2$ is a multiple of 3 then $n$ is a multiple of 3 A1*
(b) Assume $\sqrt{3} = \dfrac{a}{b}$ , $a, b$ integers, $b \neq 0$ , no common factor other than 1 B1; $a^2 = 3b^2$ , so $a^2$ is a multiple of 3 and by (a) $a = 3c$ M1; $9c^2 = 3b^2 \Rightarrow b^2 = 3c^2$ , so $b$ is a multiple of 3 A1; $a$ and $b$ share the factor 3, contradicting lowest terms, so $\sqrt{3}$ is irrational A1*

3. Assume $x$ is irrational and $\dfrac{1}{x}$ is rational, so $\dfrac{1}{x} = \dfrac{p}{q}$ with $p, q$ integers, $q \neq 0$ B1; $\frac{1}{x} \neq 0$ , so $p \neq 0$ , and $x = \dfrac{q}{p}$ M1; $q$ and $p$ are integers with $p \neq 0$ , so $x$ is rational A1; this contradicts $x$ being irrational, so $\dfrac{1}{x}$ is irrational A1*

4. $b^2 = c^2$ says nothing about whether $b$ is even (for example $b = c = 1$ ) B1; so $a$ and $b$ need not share a factor, there is no contradiction, and indeed $\sqrt{4} = \frac{2}{1}$ is rational B1

5. Assume there are integers $a, b$ with $6a + 15b = 1$ B1; $6a + 15b = 3(2a + 5b)$ , so $2a + 5b = \frac{1}{3}$ M1; $2a + 5b$ is an integer because $a$ and $b$ are, but $\frac{1}{3}$ is not an integer A1; contradiction, so no such integers exist A1*

6. Assume $r$ is rational, $x$ is irrational and $r + x$ is rational B1; write $r = \dfrac{a}{b}$ and $r + x = \dfrac{c}{d}$ with integers and $b, d \neq 0$ M1; then $x = \dfrac{c}{d} - \dfrac{a}{b} = \dfrac{bc - ad}{bd}$ , a quotient of integers with $bd \neq 0$ , so $x$ is rational A1; this contradicts $x$ being irrational, so the sum of a rational number and an irrational number is irrational A1*

Proof by contradiction: the method and the irrationality of √2

Your course level