A5PureStretch

Proof by Contradiction

Q: Why does the 2 proof insist the fraction is in lowest terms?

That assumption is the tripwire. If p/q has no common factor, then proving p and q are both even is a genuine contradiction. Without it, both being even would just mean you could cancel — no impossibility, no proof.

Q: In the primes proof, is N = p_1 p_n + 1 always prime?

No, and the proof never says so. N 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 509, not prime.)

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 = 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$ 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 ContradictionWatch the walkthrough, 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 $n^{2}$ is even then $n$ is even
Reproduce the proof that $2$ is irrational
Reproduce Euclid’s proof that there are infinitely many primes

The logic: assume the opposite

Every proof by contradiction follows the same three-beat rhythm. $Assume the negation$ — suppose the statement you want is false. $Reason$ — apply valid steps, using the assumption, until you reach a contradiction: two facts that cannot both hold. $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$ is irrational” negates to “ $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.

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$ . A direct proof is awkward, so we use contradiction — or equivalently, we prove the contrapositive.

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

n odd \Rightarrow n^{2} odd (so n^{2} even \Rightarrow n even)

The lemma we will feed into the √2 proof.

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

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.

1Assume the opposite: suppose

2

is rational. Then

2 = \frac{p}{q}

where

p, q

are integers with no common factor (the fraction is in its lowest terms) and

q \neq = 0

2Square both sides:

2 = \frac{p ^{2}}{q ^{2}}

, so

p^{2} = 2 q^{2}

3Then

p^{2}

is even, so by our lemma

p

is even. Write

p = 2 k

4Substitute:

(2 k)^{2} = 2 q^{2} \Rightarrow 4 k^{2} = 2 q^{2} \Rightarrow q^{2} = 2 k^{2}

5So

q^{2}

is even, and by the lemma again

q

is even.

6But now

p

and

q

are both even — they share a factor of 2. This contradicts our choice of

\frac{p}{q}

in lowest terms.

AnswerThe assumption that

2

is rational forces a contradiction, so

2

is irrational.

■

Why this works

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

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.

1Assume the opposite: suppose there are only finitely many primes. Then we can list them all:

p_{1}, p_{2}, p_{3}, \dots, p_{n}

2Form the number

N = p_{1} \times p_{2} \times \dots \times p_{n} + 1

— the product of every prime, plus one.

3Now

N > 1

, so

N

must have at least one prime factor.

4But dividing

N

by any prime

p_{i}

on the list leaves remainder 1 (because

p_{i}

divides the product

p_{1} \dots p_{n}

exactly). So no prime on the list divides

N

5Therefore

N

has a prime factor that is not on our list — yet the list was supposed to contain every prime. Contradiction.

AnswerThe assumption of finitely many primes fails, so there are infinitely many primes.

■

Why this works

$N$ itself need not be prime — the argument never claims it is. All that matters is that $N$ must have $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$ …” with the correct negation of the statement before anything else.
For $2$ , you must state that $\frac{p}{q}$ is in $lowest terms$ (no common factor) — the entire contradiction depends on it.
Name the contradiction explicitly: “ $p$ and $q$ share a factor of 2, contradicting lowest terms”, or “ $N$ has a prime factor not on the list”. Do not leave the examiner to spot it.
For the primes proof, do not claim $N$ 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$ 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 / q

is in lowest terms in the

2

proof.

Say it at the start. Without “no common factor”, discovering

p, q

are both even is not a contradiction.

Claiming that

N = p_{1} \dots p_{n} + 1

is itself prime.

Only claim

N

has a prime factor. Whether

N

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 \in / Q

√2 is irrational (via lowest terms).

p^{2} even \Rightarrow p even

The lemma behind the √2 proof.

N = p_{1} p_{2} \dots p_{n} + 1

Euclid’s number: primes never end.

Stretch yourself

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

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

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

proof insist the fraction is in lowest terms?

That assumption is the tripwire. If

p / q

has no common factor, then proving

p

and

q

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 = p_{1} \dots p_{n} + 1

always prime?

No, and the proof never says so.

N

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 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30031 = 59 \times 509

, 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 $n^{2}$ is even then $n$ is even — proved by contradiction, and reused in the √2 proof.
$2$ irrational: assume $2 = p / q$ in lowest terms; force $p$ and $q$ both even; contradiction.
Infinitely many primes: assume a finite list; build $N = p_{1} \dots p_{n} + 1$ ; it needs a prime factor off the list.

How this fits the course

Build on

Surds and Rationalisingsoon
Disproof by Counter-Example

Leads to

Algebra and Functionssoon

Test yourself

Ready to lock in Proof by Contradiction? Pick a mode and earn XP & Dobloons.