A-Level Maths (Edexcel 9MA0) · Pure Year 2 · Chapter 1: Algebraic methods · Lesson 1

Proof by contradiction

112 marks

Hints online, answers free with an account:
mathswariz.uk/worksheets/a-level-proof-by-contradiction/

Date

Do Now

Quick questions to start.

A1
Needed today
Prove that the square of any odd integer is odd.
[2 marks]
A2
Common slip
You want to prove "if $n^{2}$ is even, then $n$ is even" by contradiction. Write down the assumption you start from.
[2 marks]
A3
Needed today
Complete the definition: a number $x$ is rational if ...
[2 marks]
A4
Needed today
Prove that $n^{3} - n$ is even for every integer $n$ .
[3 marks]
A5
Common slip
Amir says $n^{2} + n + 41$ is prime for every positive integer $n$ . Show that he is wrong.
[2 marks]

Example, then your turn

A-Level

Your teacher works through each example with you. Then try the one beside it.

Example 1

Prove by contradiction that $2$ is irrational.

Hint Assume

2 = \frac{a}{b}

with

a

and

b

integers with no common factor. Show that

a

and

b

are both even.

B1
Prove by contradiction that $3$ is irrational. You may use the fact that if $a^{2}$ is a multiple of $3$ then $a$ is a multiple of $3$ .
[5 marks]

Example 2

Prove that if $n^{2}$ is a multiple of $3$ , then $n$ is a multiple of $3$ .

Hint Assume

n

is not a multiple of

3

. Then

n = 3 k + 1

n = 3 k + 2

. Square each one.

B2
Prove by contradiction that if $n^{3}$ is even, then $n$ is even.
[4 marks]

Example 3

Prove by contradiction that there are infinitely many prime numbers.

Hint Assume there is a largest list

p_{1}, p_{2}, \dots, p_{n}

of all the primes. Look at

N = p_{1} p_{2} \dots p_{n} + 1

B3
Prove by contradiction that there is no smallest positive rational number.
[4 marks]

Example 4

Prove by contradiction that there are no positive integers $x$ and $y$ with $x^{2} - y^{2} = 1$ .

Hint Factorise:

(x - y) (x + y) = 1

. Both brackets are integers and

x + y \geq 2

B4
Prove by contradiction that there are no positive integers $x$ and $y$ with $x^{2} - y^{2} = 10$ .
[5 marks]

Example 5

Given that $2$ is irrational, prove that $3 + 2$ is irrational.

Hint Assume

3 + 2 = q

, a rational number. Rearrange to make

2

the subject.

B5
Given that $5$ is irrational, prove by contradiction that $\frac{2}{5 - 1}$ is irrational.
[5 marks]

Practice

A-Level

C1
A student writes: "Assume $6 = \frac{a}{b}$ with $a$ and $b$ integers. Then $a^{2} = 6 b^{2}$ , so $a$ is even, $a = 2 c$ . Then $2 c^{2} = 3 b^{2}$ , so $b$ is even. That is a contradiction, so $6$ is irrational." Explain why the argument does not prove the result, and then correct it.
[4 marks]

C2
Ella wants to prove "for every integer $n$ , $n^{2} - 2$ is not a multiple of $4$ ". She starts: "Assume that for every integer $n$ , $n^{2} - 2$ is a multiple of $4$ ." Explain what is wrong with her assumption. Then give a full proof by contradiction.
[5 marks]
C3
Prove by contradiction that $32$ is irrational.
[5 marks]
C4
Prove by contradiction that $lo g_{2} 3$ is irrational.
[5 marks]

Exam-style questions

Edexcel exam style

D1
Prove by contradiction that there are no integers $p$ and $q$ such that $9 p^{2} - q^{2} = 16$ .
[9 marks]

D2
In this question $n$ is an integer.
(a)
Prove that if $n^{2}$ is a multiple of $5$ then $n$ is a multiple of $5$ .
[4 marks]
(b)
Hence prove by contradiction that $5$ is irrational.
[5 marks]
Total for D2: 9 marks
D3
Kai says: "The proof tells us that $N$ is always a prime number."
Kai is shown a proof that there are infinitely many primes. It uses $N = p_{1} p_{2} \dots p_{n} + 1$ , where $p_{1}, \dots, p_{n}$ are the first $n$ primes.
(a)
Explain why this does not mean $N$ is always prime, and say what the proof does show about $N$ .
[3 marks]
(b)
Show that $2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1$ is not prime.
[3 marks]
Answer
(c)
Explain why neither $59$ nor $509$ is in the list $2, 3, 5, 7, 11, 13$ , using the way $N$ was built.
[3 marks]
Total for D3: 9 marks
D4
In this question $x$ , $a$ and $b$ are positive real numbers.
(a)
Prove by contradiction that $x + \frac{1}{x} \geq 2$ .
[4 marks]
(b)
Hence show that $\frac{a}{b} + \frac{b}{a} \geq 2$ .
[2 marks]
(c)
Prove that $(x + \frac{1}{x}) (x^{2} + \frac{1}{x ^{2}}) \geq 4$ .
[3 marks]
Total for D4: 9 marks
D5
In this question $n$ , $x$ and $y$ are integers.
(a)
Prove that $n^{2} - 2$ is never a multiple of $3$ .
[4 marks]
(b)
Hence prove by contradiction that there are no integers $x$ and $y$ with $x^{2} + 3 y = 3 x + 5$ .
[4 marks]
Total for D5: 8 marks
D6
Given that $6$ is irrational, prove by contradiction that $2 + 3$ is irrational.
[6 marks]

Extension

Stretch

No route is given. The hints are at the end of the sheet. Use one at a time.

E1
Prove that if $a$ , $b$ and $c$ are odd integers, then the equation $a x^{2} + b x + c = 0$ has no rational solutions.
[9 marks]
Hint 1 · What to try
Suppose $x = \frac{p}{q}$ is a root, with $p$ and $q$ integers that have no common factor. Multiply the equation by $q^{2}$ .
Hint 2 · The first line
You now have $a p^{2} + b pq + c q^{2} = 0$ . Since $p$ and $q$ have no common factor, they are not both even. That leaves three cases.
Hint 3 · The full method
In each case work out whether each of the three terms is odd or even, using that $a$ , $b$ , $c$ are odd. What is their sum?

How did it go?

Colour one circle on each line.

	Not yet	Nearly	Yes
I can write the correct assumption to start a proof by contradiction.
I can prove that roots and logarithms are irrational.
I can prove that equations have no integer solutions.
I can find and correct the errors in a proof.

Answers and mark scheme

The worked answers and the full mark scheme are free with a Mathswariz account. Teachers and students can both sign up.

Get the answers