A LevelAQAEdexcelOCRAQA 2022Edexcel 2022OCR 2022

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.

A Level   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.

A Level   A Level   ## 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.

A Level   ## 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$.

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

A Level   ## Example Questions

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.

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.

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.

A Level

A Level

A Level

## You May Also Like... ### A Level Maths Revision Cards

The best A level maths revision cards for AQA, Edexcel, OCR, MEI and WJEC. Maths Made Easy is here to help you prepare effectively for your A Level maths exams.

£14.99 ### A Level Maths – Cards & Paper Bundle

A level maths revision cards and exam papers for Edexcel. Includes 2022 predicted papers based on the advance information released in February 2022! MME is here to help you study from home with our revision cards and practise papers.

From: £22.99 ### Transition Maths Cards

The transition maths cards are a perfect way to cover the higher level topics from GCSE whilst being introduced to new A level maths topics to help you prepare for year 12. Your ideal guide to getting started with A level maths!

£8.99