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 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 is rational. We express a rational number as where and are integers with no common factors. It follows that

From this last expression we can see that 2 is a factor of  and so it must be a factor of (the factors of will appear in factors of in pairs). We can write and so or . It follows that 2 is also a factor of and also .  So 2 is factor of both and . The original assumption that can be written as a rational number where and are integers with NO COMMON FACTORS has been violated. Our original assumption must be wrong. We may conclude that 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 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 be the greatest even integer. We can add 2 to it and, since is an integer, is also an integer. We also have that is even because EVEN+EVEN=EVEN. Hence, is an even integer greater than , and so our original assumption that 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 prime numbers, then we can list them:

.

Consider the number

Dividing by any of the prime numbers listed, the remainder is 1. This means that none of these prime numbers are a factor of (see polynomials). It follows that either is prime or 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.