Assuming the negation of a statement and deriving a contradiction to prove it true.
Answer at least 3 of 3 correctly to complete this section.
Some mathematical facts cannot be proved by simply working forwards from known results. How do you prove that something is impossible? That a number cannot be written as a fraction? That a list never ends?
Proof by contradiction is the tool for these situations. You assume the opposite of what you want to prove, then show that this assumption leads to something impossible — a contradiction. Since mathematics cannot contain contradictions, your assumption must have been wrong, and the original statement must be true.
This is one of the most elegant and powerful techniques in all of mathematics. At A-Level, you need to know how to use it and how to write it up clearly for full marks.
A proof by contradiction has three steps:
This is sometimes called reductio ad absurdum — reduction to absurdity.
The logic is simple: a mathematical statement is either true or false. If assuming it is false leads to a contradiction, then it cannot be false. So it must be true.
Proof by contradiction is particularly useful when:
Key distinction: Proof by contradiction is not the same as proof by counterexample. A counterexample disproves a statement (e.g. ”n2+n+41 is not always prime: try n=41”). Contradiction proves a statement by showing the opposite is impossible.
Prove that there is no largest even number.
Proof. Assume, for contradiction, that there is a largest even number. Call it N.
Since N is even, we can write N=2k for some integer k.
Consider N+2=2k+2=2(k+1).
This is also even (since it equals 2 times an integer), and N+2>N.
This contradicts our assumption that N is the largest even number. □
Therefore, there is no largest even number.
Answer at least 3 of 3 correctly to complete this section.
We want to prove: 2 is irrational.
Recall that a rational number can be written as qp where p and q are integers with q=0 and the fraction is in its simplest form (i.e. p and q have no common factors).
An irrational number is one that cannot be written in this form.
Proof. Assume, for contradiction, that 2 is rational.
Then we can write 2=qp where p and q are integers with no common factors (the fraction is in lowest terms).
Squaring both sides:
2=q2p2
p2=2q2
Since p2=2q2, we know p2 is even. But if p2 is even, then p must be even (because the square of an odd number is always odd).
So we can write p=2m for some integer m. Substituting:
(2m)2=2q2
4m2=2q2
q2=2m2
By the same argument, q2 is even, so q must be even.
But now both p and q are even, which means they share a common factor of 2. This contradicts our assumption that p and q have no common factors.
Therefore, 2 is irrational. □
Why “the square of an odd number is odd” matters: If p is odd, say p=2k+1, then p2=4k2+4k+1=2(2k2+2k)+1, which is odd. So if p2 is even, p cannot be odd — it must be even. This step is essential and examiners look for it.
When writing this proof in an exam, make sure you:
Answer at least 3 of 3 correctly to complete this section.
We want to prove: there are infinitely many prime numbers.
This proof dates back to Euclid, over 2000 years ago, and is considered one of the most beautiful arguments in all of mathematics.
Proof. Assume, for contradiction, that there are only finitely many primes.
Then we can list them all: p1,p2,p3,…,pn.
Now consider the number:
N=p1×p2×p3×⋯×pn+1
What can we say about N?
Case 1: N is prime. But N is not in our list (it is larger than every pi), contradicting our assumption that the list contains all primes.
Case 2: N is not prime, so it has a prime factor. But when we divide N by any prime pi in our list, the remainder is always 1 (since N=p1p2⋯pn+1). So no prime in our list divides N. This means N has a prime factor that is not in our list — again contradicting our assumption.
In both cases, we reach a contradiction. Therefore, there are infinitely many primes. □
Common misunderstanding: N=p1p2⋯pn+1 is not necessarily prime itself. For example, 2×3×5×7×11×13+1=30031=59×509. The point is that its prime factors are not in our original list.
Prove that there are infinitely many multiples of 3.
Proof. Assume, for contradiction, that there are finitely many multiples of 3. Let the largest be M=3k for some positive integer k.
Consider M+3=3k+3=3(k+1).
This is a multiple of 3, and it is greater than M. This contradicts our assumption that M was the largest multiple of 3.
Therefore, there are infinitely many multiples of 3. □
Answer at least 3 of 3 correctly to complete this section.
| Method | How it works | When to use it |
|---|---|---|
| Deduction | Start from known facts, use logical steps to reach the conclusion | Most proofs — working forwards from definitions and theorems |
| Exhaustion | Check every possible case | When there are finitely many cases (e.g. “prove for all single-digit primes”) |
| Contradiction | Assume the negation, derive a contradiction | When you need to prove something is impossible or infinite |
| Counterexample | Give one case where a statement fails | When you need to disprove a statement |
Prove that the sum of two consecutive odd numbers is divisible by 4.
Proof. Let the two consecutive odd numbers be 2n+1 and 2n+3.
Their sum is:
(2n+1)+(2n+3)=4n+4=4(n+1)
This is divisible by 4. □
This was a direct proof — no need for contradiction.
Prove by contradiction that if n2 is even, then n is even.
Proof. Assume, for contradiction, that n2 is even but n is odd.
If n is odd, we can write n=2k+1 for some integer k.
Then:
n2=(2k+1)2=4k2+4k+1=2(2k2+2k)+1
This is odd (since it is one more than an even number).
But we stated that n2 is even. This is a contradiction.
Therefore, if n2 is even, then n must be even. □
Prove by contradiction that 3 is irrational.
The structure is given. Fill in the missing steps marked with text.
Proof. Assume, for contradiction, that 3 is rational.
Then 3=qp where p and q are integers with no common factors.
Squaring: 3=q2p2, so p2=3q2.
Since p2=3q2, we know p2 is divisible by 3. Therefore p must be divisible by 3 (because if p were not divisible by 3, then p2 would not be divisible by 3).
Write p=3m. Substituting: (3m)2=3q2, so 9m2=3q2, giving q2=3m2.
By the same argument, q is divisible by 3.
But both p and q are divisible by 3, which contradicts the assumption that p and q have no common factors.
Therefore, 3 is irrational. □
Check your blanks: 3q2; 3m2; the assumption that qp is in lowest terms.
When answering a “prove by contradiction” question:
Mark scheme insight: Examiners award marks for (i) stating the assumption, (ii) logical working, (iii) identifying the contradiction, and (iv) the conclusion. Missing any of these loses marks, even if your mathematics is correct.
Answer at least 3 of 4 correctly to complete this section.
Lock in what you've learned with exam-style questions and spaced repetition.