Proof by Contradiction

A method of proof that involves making an assumption that turns out to be incorrect. We start by making an opposing assumption which is usually heavily hinted in the question. For example, to prove that root 2 is irrational, we assume that it is rational. If in the steps that follow we find a contradiction, it suggests that the original assumption is actually incorrect.

Proof by Contradiction that $\sqrt{2}$ is irrational

Proof by contradiction usually starts with an assumption that opposes the statement in the question. Going from there, we hope to meet a contradiction so as to rule out original assumption. In this question, we assume that $\sqrt{2}$ is rational. We express a rational number as $\frac{a}{b}$ where $a$ and $b$ are integers with no common factors. It follows that

$\sqrt{2}=\frac{a}{b}\hspace{10pt}\Rightarrow\hspace{10pt} 2=\frac{a^2}{b^2}\hspace{10pt}\Rightarrow\hspace{10pt}a^2=2b^2$

From this last expression we can see that 2 is a factor of $a^2$ and so it must be a factor of $a$ (the factors of $a$ will appear in factors of $a^2$ in pairs). We can write $a=2m$ and so $a^2=4m^2=2b^2$ or $b^2=2m^2$ . It follows that 2 is also a factor of $b^2$ and also $b$ . So 2 is factor of both $a$ and $b$ . The original assumption that $\sqrt{2}$ can be written as a rational number $\frac{a}{b}$ where $a$ and $b$ are integers with NO COMMON FACTORS has been violated. Our original assumption must be wrong. We may conclude that $\sqrt{2}$ is irrational.

Proving that there are infinitely many prime numbers is also a common proof that uses proof by contradiction. You will be required to know this proof (see Example 2) as well as the proof that $\sqrt{2}$ is irrational as above. Exam questions may also deviate slightly from these examples where you will have to apply this knowledge to prove other statements by contradiction.

Examples

Prove that there is no greatest even integer.

Solution:

We begin by making the assumption that there exists a greatest even integer and like all contradictory proofs we will end up breaking that assumption.

Let $n$ be the greatest even integer. We can add 2 to it and, since $n$ is an integer, $n+2$ is also an integer. We also have that $n+2$ is even because EVEN+EVEN=EVEN. Hence, $n+2$ is an even integer greater than $n$ , and so our original assumption that $n$ is the greatest even integer must be untrue. In conclusion, there is no greatest even integer.

Prove that there are infinitely many prime numbers.

Solution:

We begin by making the assumption that there exists a finite number of prime numbers and like all contradictory proofs we will end up breaking that assumption.

If there are finitely many prime numbers, i.e. there are precisely $n$ prime numbers, then we can list them:

$p_1, p_2, p_3, ..., p_{n-1}, p_n$ .

Consider the number

$p=p_1\times p_2\times p_3\times ...\times p_{n-1}\times p_n+1$

Dividing $p$ by any of the prime numbers listed, the remainder is 1. This means that none of these prime numbers are a factor of $p$ (see polynomials). It follows that either $p$ is prime or $p$ has another prime factor that is not in the list (every number has a unique prime factorisation). Either way, there is another prime not originally stated, breaking the original assumption. Hence, by proof by contradiction, there are infinitely many prime numbers.

Proof by Contradiction

Examples

AS Maths Proof

A2 Maths Proof

Return To The Maths Index

About

Edexcel

Maths Pages

Useful Websites

Legal

Account