A LevelAQAEdexcelOCR

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 LevelAQAEdexcelOCR

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 LevelAQAEdexcelOCR
A LevelAQAEdexcelOCR

## 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 LevelAQAEdexcelOCR

## 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 LevelAQAEdexcelOCR

## Proof by Contradiction 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

## Proof by Contradiction Worksheet and Example Questions 