Proof by Contradiction in Depth

Proof by contradiction — also known as reductio ad absurdum — is one of the most elegant and powerful techniques in mathematics. The method works by assuming the opposite of what you want to prove and then showing that this assumption leads to a logical impossibility (a contradiction). Since the assumption produces a contradiction, it must be false, and therefore the original statement must be true.

The AQA A-Level Mathematics specification (7357) explicitly lists proof by contradiction as a required technique. The classic examples — the irrationality of √2 and the infinitude of primes — are staple exam and interview questions.

---

The Logical Structure

The logical structure of proof by contradiction is as follows:

1. State the proposition P that you wish to prove.
2. Assume ¬P (the negation of P).
3. Derive a sequence of logical consequences from ¬P.
4. Arrive at a contradiction — a statement that is logically impossible (e.g., both X and ¬X are true, or a known fact is violated).
5. Conclude that since ¬P leads to a contradiction, ¬P is false. Therefore P is true.

This method relies on the law of excluded middle: a mathematical statement is either true or false; there is no third option.

Exam Tip: When writing a proof by contradiction, begin with: "Assume, for contradiction, that..." This signals clearly to the examiner that you are using this technique.

---

The Irrationality of √2

This is the most important proof by contradiction at A-Level and is frequently examined.

Theorem: √2 is irrational.

Proof:

Assume, for contradiction, that √2 is rational. Then we can write:

√2 = a/b

where a and b are positive integers with no common factors (i.e., the fraction a/b is in its simplest form, or equivalently, a and b are coprime with gcd(a, b) = 1).

Squaring both sides:

2 = a²/b²

So a² = 2b².

This means a² is even. Since the square of an odd number is odd (as proved earlier), a must be even.

Write a = 2k for some integer k.

Then:

(2k)² = 2b²
4k² = 2b²
b² = 2k²

So b² is even, which means b must be even.

But now both a and b are even, so they share a common factor of 2. This contradicts our assumption that a/b is in its simplest form (i.e., that a and b have no common factors).

Therefore, our assumption is false, and √2 is irrational. ∎

Key Point: The proof works because assuming rationality and lowest terms leads inevitably to the conclusion that the fraction is not in lowest terms — a contradiction.

---

Extending to Other Irrationality Proofs

The Irrationality of √3

Theorem: √3 is irrational.

Proof:

Assume, for contradiction, that √3 = a/b where a and b are coprime positive integers.

Then a² = 3b².

So a² is divisible by 3. We need the fact that if p is prime and p | n², then p | n. (This follows from the Fundamental Theorem of Arithmetic.)

Therefore 3 | a, so write a = 3k.

Then 9k² = 3b², giving b² = 3k².

So 3 | b² and hence 3 | b.

But then both a and b are divisible by 3, contradicting gcd(a, b) = 1.

Therefore √3 is irrational. ∎

The Irrationality of √5

The same argument applies, replacing 3 with 5 throughout. In general, √p is irrational for any prime p.

---

Infinitely Many Primes

This is Euclid's famous proof from around 300 BC and is one of the most celebrated proofs in all of mathematics.

Theorem: There are infinitely many prime numbers.

Proof:

Assume, for contradiction, that there are only finitely many primes. List them all:

p₁, p₂, p₃, ..., pₙ

Consider the number:

N = p₁ × p₂ × p₃ × ... × pₙ + 1

Now, N is greater than 1. Every integer greater than 1 is either prime or has a prime factor.

Divide N by any prime pᵢ from our list:

N ÷ pᵢ = (p₁ × p₂ × ... × pₙ)/pᵢ + 1/pᵢ

The first term is an integer, but 1/pᵢ is not (since pᵢ ≥ 2). So N is not divisible by pᵢ.

This means N is not divisible by any prime on our list. Therefore, either:

• N is itself a prime not on the list, or
• N has a prime factor not on the list.

Either way, there exists a prime not on our list. This contradicts the assumption that we listed all primes.

Therefore, there are infinitely many primes. ∎

Common Misconception: The proof does NOT claim that N itself is prime. It claims that N has a prime factor not on the list — which could be N itself or a smaller prime that was not included.

---

When to Use Proof by Contradiction

Proof by contradiction is particularly useful when:

• The statement involves irrationality or non-existence.
• The statement is about the impossibility of a certain situation.
• A direct proof is difficult because the conclusion is hard to reach constructively.
• The negation of the statement provides a clear starting point for algebraic manipulation.

Examples of statements well-suited to contradiction:

• "√2 is irrational" — the negation (√2 is rational) gives a fraction to work with.
• "There are infinitely many primes" — the negation (finitely many) gives a finite list to work with.
• "There is no largest even number" — the negation (there is a largest) gives a specific number to work with.

---

Further Examples

Example: Prove that there is no largest even number.

Assume, for contradiction, that there is a largest even number, call it M.

Consider M + 2. Since M is even, M + 2 is also even. And M + 2 > M.

This contradicts the assumption that M is the largest even number.

Therefore, there is no largest even number. ∎

Example: Prove that if n² is even, then n is even.

Assume, for contradiction, that n² is even but n is odd.

Let n = 2k + 1.

n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1

This is odd. But we assumed n² is even — a contradiction.

Therefore, if n² is even, then n is even. ∎

---

Common Errors in Proof by Contradiction

1. Not clearly stating the assumption. Always begin with "Assume, for contradiction, that..."
2. Not reaching a genuine contradiction. The contradiction must be a logically impossible statement, such as "a and b are coprime, but both are even."
3. Confusing the conclusion. After reaching a contradiction, the conclusion is that the assumption is false — make sure you state the original proposition as the conclusion.
4. Circular reasoning. Do not use the result you are trying to prove within the proof itself.

---

Summary

• Proof by contradiction assumes the negation of the desired result and derives a logical impossibility.
• The irrationality of √2 is proved by assuming √2 = a/b in lowest terms and showing both a and b must be even — a contradiction.
• The infinitude of primes is proved by assuming finitely many primes, constructing N = p₁p₂...pₙ + 1, and showing N has a prime factor not on the list.
• Use contradiction when the statement involves irrationality, non-existence, or impossibility.
• Always state your assumption clearly, derive the contradiction rigorously, and conclude by affirming the original statement.

Exam Tip: In AQA papers, proof by contradiction questions are often worth 4–6 marks. The mark scheme typically awards marks for: (1) stating the assumption, (2) performing the key algebraic steps, (3) identifying the contradiction, and (4) writing a concluding statement. Practise the √2 proof until you can write it fluently from memory.

A-Level Deep Dive: Proof by Contradiction

Spec mapping

AQA 7357 Pure Mathematics, Section A — Proof, sub-strand A2 (Year 2 content) covers proof by contradiction (refer to the official specification document for exact wording). The technique sits inside the broader Year 2 Pure paper (Paper 2, Section A) but is examined synoptically — a contradiction step can appear inside a number-theory question, a sequences/series question, or a logarithms question without being signposted. The AQA formula booklet provides nothing for this topic; the entire technique is procedural memory plus disciplined logical phrasing.

The required exemplars are listed explicitly in the AQA subject content: prove that $\sqrt{2}$2​ is irrational, prove there are infinitely many primes, prove that there is no greatest even integer, prove that if $n^2$n2 is even then $n$n is even. Examiners assume fluency with at least the first two — the irrationality of $\sqrt{2}$2​ is the canonical contradiction proof and appears in some form across most Year-2 mock series. Confidence with these named examples is the price of entry; A* candidates can also recognise when a novel question is asking for contradiction rather than direct proof.

---

Worked example with full mark scheme

Question (8 marks): Prove, by contradiction, that $\sqrt{2}$2​ is irrational.

Solution with mark scheme:

Step 1 — state the assumption (the negation of the conclusion).

Assume, for contradiction, that $\sqrt{2}$2​ is rational. Then there exist integers $p$p and $q$q with $q \neq 0$q=0 such that

$\sqrt{2} = \dfrac{p}{q}$2​=qp​

where the fraction $\dfrac{p}{q}$qp​ is written in lowest terms — that is, $p$p and $q$q share no common factor greater than $1$1, so $\gcd(p, q) = 1$gcd(p,q)=1.

B1 — correct opening assumption: stating that $\sqrt{2}$2​ is rational and writing it as $p/q$p/q with integer $p, q$p,q and $q \neq 0$q=0. Common slip: writing only "let $\sqrt{2} = p/q$2​=p/q" without naming $p, q$p,q as integers. The integrality is the entire point.

B1 — explicit "lowest terms" / coprimality clause. Without this, the contradiction at the end has no force, because every rational has some representation as $p/q$p/q. Examiners look for the words "lowest terms", "coprime", or "$\gcd(p, q) = 1$gcd(p,q)=1".

Step 2 — algebraic manipulation.

Square both sides:

$2 = \dfrac{p^2}{q^2} \implies p^2 = 2q^2$2=q2p2​⟹p2=2q2

M1 — squaring and rearranging to expose the parity relationship.

So $p^2$p2 is even (it equals $2q^2$2q2, which is twice an integer).

Step 3 — first parity deduction.

If $p^2$p2 is even, then $p$p is even. (Because if $p$p were odd, then $p^2$p2 would be odd: an odd number times an odd number is odd.)

M1 — invoking the standard lemma "if $p^2$p2 is even then $p$p is even", with a one-line justification. AQA mark schemes for Year 2 contradiction proofs accept either a brief contrapositive remark or a citation of a previously proved result.

So write $p = 2k$p=2k for some integer $k$k.

A1 — correct substitution form.

Step 4 — second parity deduction.

Substitute $p = 2k$p=2k back into $p^2 = 2q^2$p2=2q2:

$(2k)^2 = 2q^2 \implies 4k^2 = 2q^2 \implies q^2 = 2k^2$(2k)2=2q2⟹4k2=2q2⟹q2=2k2

M1 — algebraic substitution and simplification.

So $q^2$q2 is even, and by the same lemma, $q$q is even.

Step 5 — derive the contradiction.

We now have that both $p$p and $q$q are even — so $2$2 divides both. But this contradicts the assumption that $p$p and $q$q were coprime ($\gcd(p, q) = 1$gcd(p,q)=1).

A1 — explicit naming of the contradiction. The candidate must identify what contradicts what: "$p$p and $q$q are both even, contradicting $\gcd(p, q) = 1$gcd(p,q)=1." Saying merely "this is a contradiction" without identifying the contradicted statement loses this mark.

Step 6 — conclusion.

Therefore the assumption that $\sqrt{2}$2​ is rational must be false. Hence $\sqrt{2}$2​ is irrational, as required.

B1 — concluding sentence that names the original conjecture and asserts it. The phrase "as required" or "QED" or "which was to be shown" is examiner-rewarded because it closes the logical loop.

Total: 8 marks.

---

Specimen question modelled on the AQA 7357 Paper 2 format

Question (6 marks): Prove, by contradiction, that there is no greatest even integer.

Mark scheme decomposition by AO:

• B1 (AO2.1) — assumption: "Assume, for contradiction, that there is a greatest even integer; call it $N$N."
• M1 (AO1.1a) — construct a candidate larger even integer: consider $N + 2$N+2.
• A1 (AO1.1b) — verify it is even: since $N$N is even, $N = 2m$N=2m for some integer $m$m, so $N + 2 = 2(m + 1)$N+2=2(m+1), which is also even.
• A1 (AO2.1) — verify it is greater than $N$N: clearly $N + 2 > N$N+2>N.
• R1 (AO2.4) — name the contradiction: "this contradicts the assumption that $N$N was the greatest even integer."
• B1 (AO2.4) — concluding statement: "therefore there is no greatest even integer."

Total: 6 marks split AO1 = 2, AO2 = 4. Notice the AO2 dominance: contradiction proofs are reasoning-heavy by design. Examiners reward logical hygiene — the named contradiction, the coherent conclusion — more than they reward technical algebra.

---

Synoptic links

Connects to:

1. Direct deduction (Section A1): contradiction is the logical mirror of direct proof. A direct proof goes "assume $P$P, deduce $Q$Q"; contradiction goes "assume $P$P and not-$Q$Q, deduce a falsehood". Choosing between them is itself an AO2 skill — irrationality and infinity statements often cannot be tackled directly because there is no constructive object to reason from.

2. Logic and quantifiers (cross-cutting): the negation of "for all $x$x, $P(x)$P(x)" is "there exists $x$x with $\neg P(x)$¬P(x)". Contradiction proofs of universal claims open with a "there exists" assumption. Misnegating the statement at the start dooms the proof — see the misconceptions section.

3. Sequences and induction (Further Maths Pure): induction proves "for all $n$n, $P(n)$P(n)" by chaining $P(k) \implies P(k+1)$P(k)⟹P(k+1). Contradiction is the alternative when no clean inductive structure exists. Many Further Maths students learn both and choose by problem shape.

4. Number theory (synoptic Pure): primes, divisibility, parity, and the fundamental theorem of arithmetic provide the raw material for most contradiction proofs at A-Level. Euclid's infinitude-of-primes proof rests on contradiction plus the existence of prime factorisations.

5. Limits and convergence (Year 2 Calculus): rigorous $\varepsilon$ε-$\delta$δ arguments at university often proceed by contradiction — "suppose the limit is not $L$L; then there exists $\varepsilon > 0$ε>0 such that...". The seed of this style is planted at A-Level.

---

Mark-scheme literacy

AQA proof-by-contradiction questions split AO marks heavily toward AO2: