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.
A Level Maths Predicted Papers
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.
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. The profit from every pack is reinvested into making free content on MME, which benefits millions of learners across the country.
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 LevelYou 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.