Proof by Contradiction

A LevelAQAEdexcelOCR

Proof by Contradiction

You have already seen some types of proof, but there is one more which is a bit harder – proof by contradiction. There are different styles of questions in which you need to use proof by contradiction.

Product

A Level Maths Predicted Papers 2025

117

From: £19.99

The MME A level maths predicted papers are an excellent way to practise, using authentic exam style questions that are unique to our papers. Our examiners have studied A level maths past papers to develop predicted A level maths exam questions in an authentic exam format. The profit from every pack is reinvested into making free content on MME, which benefits millions of learners across the country.

View Product

Product

A-A* A Level Maths Practice Papers

£19.99

The MME A-A* A level maths practice papers are excellent for those top achieving students to practise for their exams, using authentic exam style questions that are unique to our practice papers. Our content experts have studied A level maths past papers and specifications to develop specific A-A* A level maths exam questions in an authentic exam style. The profit from every pack is reinvested into making free content on MME, which benefits millions of learners across the country.

View Product

Understanding Proof by Contradiction

A proof by contradiction assumes the statement is not true, and then proves that this can’t be the case.

Example: Prove by contradiction that there is no largest even number.

First, assume that the statement is not true and that there is a largest even number, call it $\textcolor{blue}{L = 2n}$

Consider $\textcolor{blue}{L}+2$

$\textcolor{blue}{L}+2 = 2n+2 = 2(n+1)$

which is also even and is larger than $\textcolor{blue}{L}$ .

This is a contradiction to the original assumption, since there is an even number greater than the “largest even number”.

Hence, the statement is true.

Example 1: Proving Surds are Irrational

Prove by contradiction that $\sqrt{2}$ is irrational.

[5 marks]

Assume that the statement is not true, and so $\sqrt{2}$ can be written as $\dfrac{\textcolor{red}p}{\textcolor{blue}q}$ , where $\textcolor{red}p$ and $\textcolor{blue}q$ are both non-zero integers.

Also, assume that $\textcolor{red}p$ and $\textcolor{blue}q$ have no common factors.

Then,

$\begin{aligned} \sqrt{2} &= \dfrac{\textcolor{red}p}{\textcolor{blue}q} \\ \textcolor{red}p &= \sqrt{2} \textcolor{blue}q \end{aligned}$

If we square both sides,

$\textcolor{red}p^2 = 2\textcolor{blue}q^2$

Therefore, $\textcolor{red}p^2$ is an even number.

If $\textcolor{red}p^2$ is even, then $\textcolor{red}p$ must be even also (you can prove this).

So, let $\textcolor{red}p=2k$ for some integer $k$ , and substitute this into the last step:

$\begin{aligned} \textcolor{red}p^2 = (2k)^2 = 4k^2 &= 2\textcolor{blue}q^2 \\ 2k^2 &= \textcolor{blue}q^2 \end{aligned}$

Therefore $\textcolor{blue}q^2$ is even and so $\textcolor{blue}q$ is also even.

However, we assumed at the beginning that $\textcolor{red}p$ and $\textcolor{blue}q$ had no common factors, and since they are both even they must have at least one common factor. This contradicts our initial assumption.

Hence $\sqrt{2}$ cannot be written as $\dfrac{\textcolor{red}p}{\textcolor{blue}q}$ , so it is not rational.

Therefore, the statement is true.

Example 2: Proving that there are Infinitely Many Prime Numbers

Prove by contradiction that there are infinitely many prime numbers.

[5 marks]

Assume that the statement is not true in that there are a finite number of primes ( $n$ of them). Write them as

$p_1, p_2, p_3, ... p_{n-1}, p_n$

where $p_1 = 2$ and $p_n$ is the largest prime number.

Multiply all of these primes together, and call it $\textcolor{red}{N}$ :

$\textcolor{red}{N = p_1 \times p_2 \times p_3 \times ... \times p_{n-1} \times p_n}$

$\textcolor{red}{N}$ is a multiple of every prime number in the list.

Now,

$\textcolor{limegreen}{N+1} = \textcolor{red}{p_1 \times p_2 \times p_3 \times ... \times p_{n-1} \times p_n} + \textcolor{blue}{1}$

$\textcolor{limegreen}{N+1}$ should not be a prime number, since there are no prime numbers other than $p_1, ... p_n$ .

If we divide $\textcolor{limegreen}{N+1}$ by $p_n$ , or any other prime $p_i$ , this leaves a remainder of $\textcolor{blue}{1}$ . Since there are no integers that divide $\textcolor{blue}{1}$ other than $1$ itself, $\textcolor{limegreen}{N+1}$ must be a prime number, or be divisible by another prime greater than $p_n$ .

This contradicts our original assumption.

Hence, there are infinitely many primes, and the statement is true.

Proof by Contradiction Example Questions

Question 1: Prove by contradiction that if $n^2$ is an odd integer, then $n$ must be odd.

[4 marks]

Assume that the statement is not true, in that there is an even number $n$ for which $n^2$ is an odd integer.

If $n$ is even, then we can write $n=2k$ for any integer $k$ .

Then,

$n^2 = (2k)^2 = 4k^2 = 2(2k^2)$

which is even, since it is $2 \, \times$ a number.

However, this contradicts the assumption that there is an even number $n$ for which $n^2$ is odd.

Therefore, if $n^2$ is an odd integer, then $n$ must be odd, which proves the statement.

Save your answers with

Gold Standard Education

Question 2: Prove by contradiction that there is no largest multiple of $17$

[3 marks]

Assume that the largest multiple of $17$ is $17n$ , where $n$ is an integer. Call it $L$ .

Then,

$L+17 = 17n + 17 = 17(n+1)$

which is a multiple of $17$ and is larger that $L$ .

This contradicts the assumption that $L$ is the largest multiple of $17$ .

Hence, there is no largest multiple of $17$ , and so the statement is true.

Save your answers with

Gold Standard Education

Question 3: Prove by contradiction that if $x^3$ is odd, then $x$ must be odd.

[3 marks]

Assume that there is an even number $x$ such that $x^3$ is odd.

So, define $x = 2k$ , where $k$ is an integer.

Hence,

$x^3 = (2k)^3 = 8k^3 = 2(4k^3)$

Therefore, $x^3$ is even.

However, this contradicts the assumption that there is an even number $x$ such that $x^3$ is odd.

Hence, if $x^3$ is odd, then $x$ must be odd, which proves the statement.

Save your answers with

Gold Standard Education

Additional Resources

Exam Tips Cheat Sheet

A Level

Open

Formula Booklet

A Level

Open

Specification Points Covered

A1 – Understand and use the structure of mathematical proof, proceeding from given assumptions through a series of logical steps to a conclusion; use methods of proof, including proof by deduction, proof by exhaustion
Disproof by counter example
Proof by contradiction (including proof of the irrationality of $\sqrt{2}$ and the infinity of primes, and application to unfamiliar proofs)