# Proof by Contradiction

## Proof by Contradiction Revision

**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.

**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.

**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.

**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.

## Proof by Contradiction Worksheet and Example Questions

### Proof by Contradiction

A Level## You May Also Like...

### MME Learning Portal

Online exams, practice questions and revision videos for every GCSE level 9-1 topic! No fees, no trial period, just totally free access to the UKâ€™s best GCSE maths revision platform.