A1PureStretch

Proof by Contradiction

To prove a statement by contradiction, you assume it is false and then reason until reality breaks — you reach something that cannot possibly be true. That impossibility means your assumption was wrong, so the statement must be true.

35 min Video by TLMaths Proof

The big picture

Proof by contradiction feels like a magic trick the first time you see it, and then like the most natural thing in the world. The move is bold: to prove something is true, you begin by assuming it is false, and you follow that assumption faithfully until it collapses into an absurdity — like 1=21 = 2, or a number that is both even and odd. Since valid reasoning can never turn a true assumption into a falsehood, the only escape is that the assumption itself was false.

It is the sharpest tool in the proof kit, and AQA names two specific results you must be able to prove with it: that 2\sqrt{2} is irrational, and that there are infinitely many prime numbers. Both are over two thousand years old, and both are unreachable by the direct methods you have met so far — which is exactly why contradiction exists.

A-Level Maths A1-10: Introducing Proof by ContradictionCurated by Kepler, not produced by us. Watch it, then work through the notes below.
Open on YouTube

What you'll be able to do

  • State the logic of proof by contradiction and negate a statement correctly
  • Prove a lemma by contradiction: if n2n^2 is even then nn is even
  • Reproduce the proof that 2\sqrt{2} is irrational
  • Reproduce Euclid’s proof that there are infinitely many primes
1

The logic: assume the opposite

Every proof by contradiction follows the same three-beat rhythm. Assume the negation\textbf{Assume the negation} — suppose the statement you want is false. Reason\textbf{Reason} — apply valid steps, using the assumption, until you reach a contradiction: two facts that cannot both hold. Conclude\textbf{Conclude} — since correct reasoning cannot produce an impossibility, the assumption must have been wrong, so the original statement is true.

The delicate part is the very first move: negating the statement precisely. “2\sqrt{2} is irrational” negates to “2\sqrt{2} is rational”. “There are infinitely many primes” negates to “there are finitely many primes”. Get the negation slightly wrong and the whole proof is aimed at the wrong target.

Why this works

Contradiction is what you reach for when the direct route is blocked. It is hard to build a positive thing out of “irrational” or “infinitely many” — but easy to assume the tidy opposite (“rational”, “finite list”) and then squeeze it until it breaks.

2

A warm-up: if $n^2$ is even, then $n$ is even

This small result is worth proving on its own, and we will need it for 2\sqrt{2}. A direct proof is awkward, so we use contradiction — or equivalently, we prove the contrapositive.

Assume the statement is false: suppose n2n^2 is even but nn is odd\textbf{odd}. Then we can write n=2k+1n = 2k+1 for some integer kk. Squaring, n2=(2k+1)2=4k2+4k+1=2(2k2+2k)+1n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1, which is odd. But we assumed n2n^2 is even. A number cannot be both even and odd — contradiction. So nn cannot be odd; it must be even.

n odd  ⇒  n2 odd(so n2 even⇒n even)n \text{ odd} \;\Rightarrow\; n^2 \text{ odd} \qquad\text{(so } n^2 \text{ even} \Rightarrow n \text{ even)}
The lemma we will feed into the √2 proof.

Tip — The same argument shows: if n2n^2 is a multiple of 3, then nn is a multiple of 3. That version powers the proof that 3\sqrt{3} is irrational.

3

The headline proof: $\sqrt{2}$ is irrational

This is one of the most famous proofs in all of mathematics, and AQA can ask for it directly. Follow every line — the structure is the lesson.

Example 1Prove that 2\sqrt{2} is irrational.
1Assume the opposite: suppose 2\sqrt{2} is rational. Then 2=pq\sqrt{2} = \dfrac{p}{q} where p,qp, q are integers with no common factor (the fraction is in its lowest terms) and q≠0q \neq 0.
2Square both sides: 2=p2q22 = \dfrac{p^2}{q^2}, so p2=2q2p^2 = 2q^2.
3Then p2p^2 is even, so by our lemma pp is even. Write p=2kp = 2k.
4Substitute: (2k)2=2q2⇒4k2=2q2⇒q2=2k2(2k)^2 = 2q^2 \Rightarrow 4k^2 = 2q^2 \Rightarrow q^2 = 2k^2.
5So q2q^2 is even, and by the lemma again qq is even.
6But now pp and qq are both even — they share a factor of 2. This contradicts our choice of pq\dfrac{p}{q} in lowest terms.
Answer
The assumption that 2\sqrt{2} is rational forces a contradiction, so 2\sqrt{2} is irrational. ■\blacksquare
Why this works

The “lowest terms” assumption is the trap that springs the contradiction. By insisting pp and qq share no factor at the start, we guarantee that discovering they are both even is an impossibility — not just an inconvenience.

4

The other named proof: infinitely many primes

Euclid proved this around 300 BC, and it is a masterpiece of contradiction. The idea: assume the primes run out, then build a number that no prime on the list can divide.

Example 1Prove that there are infinitely many prime numbers.
1Assume the opposite: suppose there are only finitely many primes. Then we can list them all: p1,p2,p3,…,pnp_1, p_2, p_3, \ldots, p_n.
2Form the number N=p1×p2×⋯×pn+1N = p_1 \times p_2 \times \cdots \times p_n + 1 — the product of every prime, plus one.
3Now N>1N > 1, so NN must have at least one prime factor.
4But dividing NN by any prime pip_i on the list leaves remainder 1 (because pip_i divides the product p1⋯pnp_1\cdots p_n exactly). So no prime on the list divides NN.
5Therefore NN has a prime factor that is not on our list — yet the list was supposed to contain every prime. Contradiction.
Answer
The assumption of finitely many primes fails, so there are infinitely many primes. ■\blacksquare
Why this works

NN itself need not be prime — the argument never claims it is. All that matters is that NN must have some\textbf{some} prime factor, and that factor cannot be any prime on the supposedly-complete list.

Think like an examiner

  • The opening line is worth a mark on its own: write “Assume\textbf{Assume} …” with the correct negation of the statement before anything else.
  • For 2\sqrt{2}, you must state that pq\dfrac{p}{q} is in lowest terms\textbf{lowest terms} (no common factor) — the entire contradiction depends on it.
  • Name the contradiction explicitly: “pp and qq share a factor of 2, contradicting lowest terms”, or “NN has a prime factor not on the list”. Do not leave the examiner to spot it.
  • For the primes proof, do not claim NN is prime — say only that it must have a prime factor. That is a classic place students lose the final mark.
  • Close by returning to the original statement: “therefore 2\sqrt{2} is irrational”.

Common misconceptions

Negating the statement incorrectly, e.g. taking the opposite of “infinitely many” to be “none”.
The negation of “infinitely many primes” is “finitely many primes”, i.e. a finite complete list. Negate carefully.
Forgetting to state that p/qp/q is in lowest terms in the 2\sqrt{2} proof.
Say it at the start. Without “no common factor”, discovering p,qp, q are both even is not a contradiction.
Claiming that N=p1⋯pn+1N = p_1 \cdots p_n + 1 is itself prime.
Only claim NN has a prime factor. Whether NN is prime or composite, that factor cannot be on the list.
Reaching an odd result and stopping without saying why it is impossible.
Spell out the impossibility (“both even and odd”, or “a factor not on a complete list”) — that is the contradiction that ends the proof.

The two named results

2∉Q\sqrt{2} \notin \mathbb{Q}
√2 is irrational (via lowest terms).
p2 even⇒p evenp^2 \text{ even} \Rightarrow p \text{ even}
The lemma behind the √2 proof.
N=p1p2⋯pn+1N = p_1 p_2 \cdots p_n + 1
Euclid’s number: primes never end.

Stretch yourself

Adapt the 2\sqrt{2} argument to prove that 3\sqrt{3} is irrational. Which lemma do you need, and where does the contradiction come from?

Hint — You need “if n2n^2 is a multiple of 3, then nn is a multiple of 3.” Start from 3=p/q\sqrt{3} = p/q in lowest terms.

Reveal solution
SolutionAssume 3=pq\sqrt{3} = \dfrac{p}{q} in lowest terms. Then 3=p2q23 = \dfrac{p^2}{q^2}, so p2=3q2p^2 = 3q^2, meaning p2p^2 is a multiple of 3. By the lemma, pp is a multiple of 3, so write p=3kp = 3k. Then 9k2=3q2⇒q2=3k29k^2 = 3q^2 \Rightarrow q^2 = 3k^2, so q2q^2 is a multiple of 3 and hence qq is too. Now pp and qq are both multiples of 3, contradicting lowest terms. So 3\sqrt{3} is irrational. ■\blacksquare (The lemma holds because if nn is not a multiple of 3, then n=3k±1n = 3k\pm1 and n2=3(3k2±2k)+1n^2 = 3(3k^2\pm2k)+1 is not a multiple of 3.)

Questions students ask

How is proof by contradiction different from disproof by counter-example?
A counter-example disproves a statement by exhibiting one failing case. Proof by contradiction proves a statement is true, by assuming it is false and deriving an impossibility. One tears a claim down with an example; the other builds a claim up from an absurdity.
Why does the 2\sqrt{2} proof insist the fraction is in lowest terms?
That assumption is the tripwire. If p/qp/q has no common factor, then proving pp and qq are both even is a genuine contradiction. Without it, both being even would just mean you could cancel — no impossibility, no proof.
In the primes proof, is N=p1⋯pn+1N = p_1\cdots p_n + 1 always prime?
No, and the proof never says so. NN simply must have some prime factor, and that factor cannot be any prime on the assumed-complete list — which is the contradiction. (For example 2×3×5×7×11×13+1=30031=59×5092\times3\times5\times7\times11\times13+1 = 30031 = 59\times509, not prime.)
How do I know when to use contradiction rather than a direct proof?
Use it when the statement is hard to attack head-on — especially claims about irrationality, infinity, or “there is no…”. Assuming the neat opposite (rational, finite, “there is a smallest…”) usually gives you something concrete to work with.

Key takeaways

  • Assume the statement is false, reason to an impossibility, and conclude it must be true.
  • The first and most error-prone step is negating the statement correctly.
  • Lemma: if n2n^2 is even then nn is even — proved by contradiction, and reused in the √2 proof.
  • 2\sqrt{2} irrational: assume 2=p/q\sqrt2 = p/q in lowest terms; force pp and qq both even; contradiction.
  • Infinitely many primes: assume a finite list; build N=p1⋯pn+1N = p_1\cdots p_n + 1; it needs a prime factor off the list.

How this fits the course

Related

Leads to

  • Algebra and Functionssoon

Test yourself

Answer a few questions, then review anything you missed.

Prefer paper? Open the written self-check

Answer each question before opening its answer. This self-check does not record a quiz score.

  1. A proof by contradiction begins by:

    • assuming the statement is false
    • assuming the statement is true
    • testing several examples
    • listing all cases
    Show answer and explanation

    Answer: assuming the statement is false

    You assume the negation, then derive an impossibility from it.

  2. The correct negation of “there are infinitely many primes” is:

    • there are finitely many primes
    • there are no primes
    • there is exactly one prime
    • all numbers are prime
    Show answer and explanation

    Answer: there are finitely many primes

    The opposite of “infinitely many” is “finitely many”, i.e. a finite complete list.

  3. In the 2\sqrt{2} proof, assuming 2=p/q\sqrt{2} = p/q in lowest terms leads to:

    • pp and qq are both even, contradicting lowest terms
    • pp is prime
    • q=0q = 0
    • p=qp = q
    Show answer and explanation

    Answer: pp and qq are both even, contradicting lowest terms

    p2=2q2p^2 = 2q^2 forces pp even, then qq even — but a lowest-terms fraction cannot have both even.

  4. Why must pp be even once we know p2=2q2p^2 = 2q^2?

    • Because p2p^2 is even, and if n2n^2 is even then nn is even
    • Because pp is a multiple of qq
    • Because all squares are even
    • Because p>qp > q
    Show answer and explanation

    Answer: Because p2p^2 is even, and if n2n^2 is even then nn is even

    This is exactly the lemma proved earlier in the lesson.

  5. In Euclid’s proof, the number N=p1p2⋯pn+1N = p_1 p_2 \cdots p_n + 1 is used because:

    • no prime on the list divides it (each leaves remainder 1)
    • it is always prime
    • it is always even
    • it equals the largest prime
    Show answer and explanation

    Answer: no prime on the list divides it (each leaves remainder 1)

    Dividing NN by any listed prime leaves remainder 1, so its prime factor is not on the list.

  6. A contradiction is reached when you derive:

    • two facts that cannot both be true
    • a surprising but valid result
    • a large number
    • an example that works
    Show answer and explanation

    Answer: two facts that cannot both be true

    An impossibility (e.g. a number both even and odd) signals the assumption was false.

  7. Proof by contradiction is most useful for statements about:

    • irrationality or infinity, where a direct proof is hard
    • small finite sets of numbers
    • disproving universal claims
    • differentiating functions
    Show answer and explanation

    Answer: irrationality or infinity, where a direct proof is hard

    Assuming the tidy opposite (rational, finite) gives something concrete to work with.

Next step

Keep practising

Start with the quiz above to check the key ideas. You can also choose another topic from the practice library.

Browse practice topics

Related lessons

All 6 lessons

Put the methods into practice: see how A-Level maths duels work. An account is required to play; the overview and sample are public.