Proof by Contradiction (A2 Only)

Maths: Edexcel A Level Pure Maths, topic 1.3.7

What is Proof by Contradiction?

Proof by contradiction is when we assume that the conjecture is false and use a series of logical steps to obtain a statement that is mathematically impossible. This proves that the original conjecture is always true.

How do you prove by contradiction?

To prove a conjecture by contradiction, assume that the conjecture is always false.
Next, we use known theorems to make logical steps from the assumption.
You will reach a point where, by inspection, the logical step either:
Contradicts the starting assumption.
Violates a known theorem.
This proves that the original conjecture is always true.

Example

Prove that there are no integers $x$ and $y$ that satisfy:
$x^2 - y^2 = 10$

Assumption

If the conjecture is false, then that means the following equation is true:
$x^2-y^2 = 10$
Where $x,y \in$ ℤ (are integers).

Logical steps

Looking at the left hand side, we see that it is the difference of two squares:
$x^2-y^2 \equiv (x+y)(x-y) = 10$
We don't have any more information about $x$ and $y$ except that they are integers, so we need to look at what happens for the different cases of $x$ and $y$ .

Both $x$ and $y$ are odd

It is a known theorem that odd + odd = even and odd − odd = even.
So $x + y = 2m$ and $x-y = 2n$ , where $m$ and $n$ are integers.
This means $(x+y)(x-y) = 4mn$ .
By inspection, we see that the left-hand side of our initial assumption is a multiple of 4.
This is a contradiction as the right-hand side is equal to 10, which is not a multiple of 4.

Both $x$ and $y$ are even

It is a known theorem that even + even = even and even − even = even.
So $x + y = 2p$ and $x-y = 2q$ , where $p$ and $q$ are integers.
This means $(x+y)(x-y) = 4pq$ .
By inspection, we see that the left-hand side is a multiple of 4.
This is a contradiction, as 10 is not a multiple of 4.

$x$ is even, $y$ is odd

It is a known theorem that even + odd = odd and even − odd = odd.
So $x+y=2k+1$ and $x-y = 2l+1$ , where $k$ and $l$ are integers.
This means $(x+y)(x-y) = (2k+1)(2l+1) = 4kl + 2l + 2k + 1$ .
By inspection, we see that the left-hand side is equal to even + even + even + odd, which is an odd number.
This is a contradiction as 10 is an even number.
The same applies for odd $x$ and even $y$ .

Final statement

There are no integers $x$ and $y$ that satisfy:
$x^2-y^2 = 10$

Test yourself on Proof by Contradiction (A2 Only)

To prove the following statement by contradiction, which of the following should you take as your initial assumption?
All multiples of 6 are even.

Practise this topic for free