Proof by contradiction
Studying this course? Keep your progress in one place.
Key facts
- Assume the statement is false, argue logically, and reach something impossible.
- Write the negation carefully before you start.
- is irrational: assume in lowest terms and show both and are even.
- There are infinitely many primes: a list of all primes always misses a prime factor of N = (product) + 1.
- Examples never prove a general statement.
The method
Assume the statement is false and show that this leads to something impossible.
Each step must follow from the one before. The contradiction is the whole point, so state it clearly, for example "this contradicts the assumption that and have no common factor".
The negation of a statement is true exactly when the original is false. Write it down before you start.
- 1
Assume the negation
write it down before you start
- 2
Argue logically
each step follows from the last
- 3
Reach a contradiction
something impossible
- 4
Conclude
the assumption is false, so the statement is true
Statement
- For all , is even
- There is no integer with…
- is irrational
Negation
- There exists an integer with odd
- There is an integer with…
- is rational
What is the negation of " is irrational"?
√2 is irrational
Assume in lowest terms, then show and are both even.
Assume where are integers with no common factor and .
Squaring, . So is even, and therefore is even. Write . Then , so is even.
Now and share the factor 2. This contradicts the assumption. Therefore is irrational. The same argument works for for any prime .
- 1
Assume
√2 = p/q in lowest terms
- 2
Square
p² = 2q², so p is even
- 3
Substitute
p = 2k gives q² = 2k², so q is even
- 4
Contradiction
both even, so a common factor 2
Why is the condition 'no common factor' included in the first line?
Infinitely many primes
Assume a finite list of primes, form , and find a prime factor not in the list.
Dividing by any leaves remainder 1, so no divides . But has at least one prime factor, and it is not in the list.
This contradicts the assumption that the list contains all the primes.
need not itself be prime: with the primes up to 13, , and the argument works because 59 and 509 are primes outside the list.
- 1
Assume
a finite list of all the primes
- 2
Form N
multiply them all and add 1
- 3
Find a prime factor
it cannot be any prime on the list
- 4
Contradiction
so the list was incomplete
Worked example
Take the primes 2, 3, 5, 7, 11, 13. Form and show it is not divisible by any of them.
- 1
.
- 2
Each of the six primes divides the product, so each leaves remainder 1 when dividing N.
- 3
Factorise: .
What does the proof need to say about ?
Parity and divisibility
Look for a property, such as parity or divisibility, that the assumption forces on both sides of an equation.
Example 1: there are no integers with . Assume there are, then , so , which is not an integer.
Example 2: is irrational. Assume with positive integers, so : even equals odd.
Example 3: has no integer solutions. , and the two factors have the same parity, so both are even and the product is a multiple of 4, not 2.
- 1
Assume the opposite
for example that integers m and n exist
- 2
Factorise or rearrange
to expose a factor such as 7 or 2
- 3
Compare parity or divisibility
one side is a multiple, the other is not
- 4
Contradiction
so the assumption is false and the statement is true
Fact
- Even × anything is even
- Odd × odd is odd
- Square of odd is odd
- Square of even is even
Example
In Example 3, why is the product a multiple of 4 when both factors are even?
Using a known irrational
Assume the number is rational, rearrange to make equal to a rational expression, and contradict its irrationality.
You may use the fact that is irrational. To show is irrational, assume it equals with rational. Isolate a root and square: , so and .
The right-hand side is rational, which contradicts the irrationality of .
Rationals are closed under addition, subtraction, multiplication and division by a non-zero number.
- 1
Assume rational
√2 + √3 = r with r rational
- 2
Isolate a root
√3 = r − √2
- 3
Square both sides
3 = r² − 2r√2 + 2
- 4
Make √2 the subject
√2 = (r² − 1) / 2r, which is rational
- 5
Contradiction
√2 is irrational, so √2 + √3 is irrational
- rational rationalrational
- rational rationalrational
- rational non-zero rationalrational
Worked example
Prove that is irrational.
- 1
Assume with rational ().
- 2
Then . Square: .
- 3
Rearrange: , so .
- 4
The right-hand side is rational, but is irrational.
Why is rational when is rational?
Writing a proof
Assume, give each step with a reason, name the contradiction, then state what is proved.
Do not test examples: a few numerical cases never prove a general statement.
A contradiction can be with the assumption itself, with a given fact, or with a basic truth such as "even = odd". If you reach something that is merely unlikely, it is not a contradiction.
- 1
Assume
state the negation
- 2
Steps with reasons
each line follows from the last
- 3
This contradicts
name what is contradicted
- 4
Hence
state what has been proved
Does checking that a statement is true for prove it for all ?
Try an exam question
Prove by contradiction that is irrational. You may use the fact that if is a multiple of 3 then is a multiple of 3.
[5 marks]
- [1]Assumes with integers and no common factor.
- [1]Squares to get , so is a multiple of 3 and so is a multiple of 3.
- [1]Writes , giving , so is also a multiple of 3.
- [1] and share the factor 3, which contradicts the assumption.
- [1]Concludes that is irrational.
That's the notes covered.
Carry on to the next subtopic.
Try a question
Which assumption should the proof begin with?
1 mark, marked against the mark scheme
Which assumption should the proof begin with?
1 mark, marked against the mark scheme