Proof by Contradiction

Proof by contradiction is one of the most powerful proof techniques in mathematics. It works by assuming the opposite of what you want to prove and showing that this assumption leads to a logical impossibility.

---

The Method

1. Assume the negation of the statement you want to prove.
2. Use logical reasoning and known results to derive a contradiction — a statement that is impossible or contradicts a known fact.
3. Conclude that the original assumption was false, so the statement must be true.

---

Classic Proof: √2 Is Irrational

Statement

Prove that √2 is irrational.

Proof

Assume for contradiction that √2 is rational. Then √2 = a/b where a and b are integers with no common factors (the fraction is in its lowest terms).

Squaring: 2 = a²/b² → a² = 2b²

So a² is even, which means a is even. Write a = 2k.

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

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

But if both a and b are even, they share a common factor of 2. This contradicts our assumption that a/b is in its lowest terms.

Therefore √2 is irrational. ∎

---

Proof That There Are Infinitely Many Primes

Statement

Prove that there are infinitely many prime numbers.

Proof

Assume for contradiction that there are finitely many primes: p₁, p₂, …, pₙ.

Consider the number N = p₁ × p₂ × … × pₙ + 1.

N is greater than any of the primes p₁, p₂, …, pₙ, so N is not in our list.

Now, N is either prime or composite:

• If N is prime, then we have found a prime not in the list — contradiction.
• If N is composite, then it has a prime factor p. But N leaves remainder 1 when divided by any pᵢ, so p is not in the list — again, a contradiction.

Either way, we reach a contradiction. Therefore there are infinitely many primes. ∎

---

Proof That √3 Is Irrational

Statement

Prove that √3 is irrational.

Proof

Assume √3 = a/b where a, b are integers with no common factors.

Then a² = 3b², so 3 divides a². Since 3 is prime, 3 divides a. Write a = 3k.

Then 9k² = 3b² → b² = 3k², so 3 divides b² and hence 3 divides b.

Both a and b are divisible by 3 — contradicting the assumption that a/b is in lowest terms.

Therefore √3 is irrational. ∎

---

Worked Example: Sum of Rational and Irrational

Statement

Prove that if r is rational and x is irrational, then r + x is irrational.

Proof

Assume for contradiction that r + x is rational. Then r + x = p/q for some integers p, q.

Since r is rational, r = m/n for some integers m, n.

Then x = (r + x) − r = p/q − m/n = (pn − mq)/(qn)

This is a ratio of two integers (with qn ≠ 0), so x is rational. This contradicts the given fact that x is irrational.

Therefore r + x is irrational. ∎

---

Worked Example: No Smallest Positive Rational

Statement

Prove that there is no smallest positive rational number.

Proof

Assume for contradiction that there exists a smallest positive rational number, call it s.

Consider s/2. Since s is positive and rational, s/2 is also positive and rational.

But s/2 < s, which contradicts the assumption that s is the smallest positive rational.

Therefore no smallest positive rational number exists. ∎

---

When to Use Proof by Contradiction

Proof by contradiction is particularly useful when:

Situation	Example
Proving something is impossible	“There is no integer n such that …”
Proving irrationality	“√p is irrational for prime p”
Proving infiniteness	“There are infinitely many primes”
The direct proof is not obvious	When the “forward” direction is hard to see

---

Comparison with Other Proof Methods

Method	Approach
Direct proof (deduction)	Start from hypotheses, reason forward to the conclusion
Proof by exhaustion	Check all possible cases
Disproof by counter-example	Find one case where a statement fails
Proof by contradiction	Assume the conclusion is false and derive an impossibility

---

Common Mistakes

1. Negating the statement incorrectly. The negation of “for all x, P(x)” is “there exists x such that ¬P(x)”, not “for all x, ¬P(x)”.
2. Not reaching a genuine contradiction. The derived statement must be logically impossible, not just surprising.
3. Circular reasoning. You cannot use the result you are trying to prove as part of your argument.

---

Exam Tips

• Always start by clearly stating your assumption: “Assume for contradiction that …”
• The contradiction should be against a known fact or against your assumption — state clearly what is contradicted.
• End with a clear conclusion: “This is a contradiction, therefore the original statement is true.”
• For irrationality proofs, the standard technique involves expressing as a/b in lowest terms and showing both share a common factor.
• These proofs appear as 4–6 mark questions — every logical step must be justified.
• Practice the classic proofs (√2 irrational, infinitely many primes) until you can reproduce them fluently.

A-Level Deep Dive: Proof by Contradiction

Spec mapping

AQA 7357 specification, Paper 2 — Pure Mathematics, Section A: Proof. The Year 2 specification covers the structure of mathematical proof (proceeding from assumptions through logical steps to a conclusion) and the four methods of proof: deduction, exhaustion, disproof by counter-example, and proof by contradiction — with the irrationality of $\sqrt{2}$2​ and the infinity of primes as canonical examples (refer to the official AQA 7357 specification document for exact wording). Proof by contradiction extends the proof methods first met in Year 1 (direct proof, exhaustion, counter-example) and is examined synoptically alongside number theory, algebra, sequences and analysis. Although Section A is a small section by mark count, it is highly examinable: contradiction proofs appear on most Paper 2 papers, often as the final 4–6 mark question testing AO2 reasoning. The AQA formula booklet contains no proof templates — the structure must be memorised.

---

Worked example with full mark scheme

Question (8 marks):

(a) Prove, by contradiction, that $\sqrt{2}$2​ is irrational. (5)

(b) Hence, or otherwise, prove that $\sqrt{2} + 3$2​+3 is irrational. (3)

Solution with mark scheme:

(a) Step 1 — assume the negation.

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

$\sqrt{2} = \dfrac{a}{b}$2​=ba​

where the fraction $\dfrac{a}{b}$ba​ is in its lowest terms (i.e. $\gcd(a, b) = 1$gcd(a,b)=1).

B1 — clear statement of the assumption to be contradicted, including the "lowest terms" condition. Markers expect both halves: "assume rational" and "in lowest terms". Omitting the coprimality condition loses this mark because the eventual contradiction depends on it.

Step 2 — manipulate algebraically.

Squaring both sides:

$2 = \dfrac{a^2}{b^2} \implies a^2 = 2b^2 \quad (\star)$2=b2a2​⟹a2=2b2(⋆)

M1 — squaring and rearranging to obtain a relation of the form $a^2 = 2b^2$a2=2b2.

Step 3 — deduce $a$a is even.

From $(\star)$(⋆), $a^2$a2 is even (it equals $2b^2$2b2, a multiple of 2). Since the square of an odd integer is odd, $a$a itself must be even. Write $a = 2k$a=2k for some integer $k$k.

M1 — recognising that $a^2$a2 even forces $a$a even, with the lemma stated or invoked.

Step 4 — substitute and deduce $b$b is even.

Substituting $a = 2k$a=2k into $(\star)$(⋆):

$(2k)^2 = 2b^2 \implies 4k^2 = 2b^2 \implies b^2 = 2k^2$(2k)2=2b2⟹4k2=2b2⟹b2=2k2

By the same argument, $b^2$b2 is even, so $b$b is even.

M1 — substituting and deducing $b$b is even.

Step 5 — extract the contradiction.

But $a$a and $b$b are both even, so $2$2 is a common factor of $a$a and $b$b, contradicting the assumption that $\dfrac{a}{b}$ba​ was in lowest terms. The assumption that $\sqrt{2}$2​ is rational must be false. Therefore $\sqrt{2}$2​ is irrational, as required. $\blacksquare$■

A1 — explicit identification of the contradiction (common factor of 2 versus $\gcd(a, b) = 1$gcd(a,b)=1) and a concluding statement that $\sqrt{2}$2​ is irrational. The "as required" / "QED" closure is part of the mark — a proof without a conclusion is incomplete.

(b) Step 1 — assume the negation.

Assume, for contradiction, that $\sqrt{2} + 3$2​+3 is rational. Then $\sqrt{2} + 3 = \dfrac{p}{q}$2​+3=qp​ for integers $p, q$p,q with $q \neq 0$q=0.

B1 — correct setup of the contradictory assumption.

Step 2 — rearrange.

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

The right-hand side is a difference of a rational and an integer, hence rational. So $\sqrt{2}$2​ is rational.

M1 — isolating $\sqrt{2}$2​ and observing the right-hand side is rational (closure of $\mathbb{Q}$Q under subtraction).

Step 3 — extract the contradiction.

But this contradicts part (a), which established that $\sqrt{2}$2​ is irrational. Therefore $\sqrt{2} + 3$2​+3 is irrational. $\blacksquare$■

A1 — explicit appeal to part (a) and a concluding statement.

Total: 8 marks (B2 M3 A2 + B1, structured as shown).

---

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) — clear statement: "Assume, for contradiction, that there is a greatest even integer; call it $N$N." Markers want the variable named and the property stated.
• M1 (AO2.2a) — constructing a candidate counter-witness. Consider $M = N + 2$M=N+2. Since $N$N is even, $N = 2k$N=2k for some integer $k$k, so $M = 2k + 2 = 2(k + 1)$M=2k+2=2(k+1), hence $M$M is also an even integer.
• A1 (AO2.4) — observing that $M = N + 2 > N$M=N+2>N, so $M$M is an even integer strictly greater than $N$N.
• A1 (AO2.4) — extracting the contradiction: this contradicts the assumption that $N$N was the greatest even integer.
• A1 (AO2.1) — concluding statement: "Therefore there is no greatest even integer."
• B1 (AO2.5) — overall logical presentation: assumption, deduction, contradiction, conclusion in that order, with each step justified.

Total: 6 marks split AO1 = 0, AO2 = 6, AO3 = 0. This is a pure AO2 question — every mark is for reasoning. Notice that no calculation appears; the entire question tests structural thinking. AQA's Section A reliably allocates contradiction proofs almost entirely to AO2, because the technique itself is the assessable content.

---

Synoptic links

Connects to:

1. Pure 1 — proof methods (AS): direct proof, exhaustion and counter-example were introduced in Year 1. Contradiction is the Year 2 extension that handles propositions where direct proof is awkward — typically existence/non-existence or irrationality statements. Knowing which method to deploy is itself an A* skill: "no greatest X" is a contradiction signal; "for all even $n$n, $P(n)$P(n)" is a direct-proof signal.

2. Algebra and indices (Pure 1): the $\sqrt{2}$2​ proof relies on the parity lemma ($a^2$a2 even $\iff a$⟺a even), which is itself a small direct proof. The infinite-primes proof uses the fundamental theorem of arithmetic, which underpins index manipulation.

3. Sequences and proof by induction (Pure 2 / Further Maths): induction is the opposite technique to contradiction in some senses — induction proves a positive statement $P(n)$P(n) for all $n$n, while contradiction usually disproves a universal claim or proves a non-existence. Recognising which fits the question is examinable.

4. Number theory (synoptic): the proofs of irrationality of $\sqrt{2}$2​, $\sqrt{3}$3​, $\sqrt{p}$p​ (for any prime $p$p), and the infinitude of primes all sit at the boundary of A-Level and undergraduate number theory. The techniques are identical; only the algebraic lemmas change.

5. Logic and reasoning (cross-curricular): the structure "assume $\neg P$¬P, derive $Q \wedge \neg Q$Q∧¬Q, conclude $P$P" is the formal rule reductio ad absurdum. The same pattern is examined in Further Maths (Discrete) and is foundational in Computer Science theory of computation modules.

---

Mark-scheme literacy

Proof-by-contradiction questions on AQA 7357 Paper 2 split AO marks heavily toward AO2:

AO	Typical share	Earned by
AO1 (knowledge / procedure)	10–20%	Recalling the algebraic lemmas (parity, divisibility, fundamental theorem of arithmetic) used inside the proof
AO2 (reasoning / interpretation)	70–85%	Constructing the assumption, executing the logical chain, identifying the contradiction, concluding correctly
AO3 (problem-solving)	0–10%	Selecting contradiction over direct proof in less obvious cases; adapting standard proofs to novel statements

Examiner-rewarded phrasing: "Assume, for contradiction, that …"; "in its lowest terms, so $\gcd(a, b) = 1$gcd(a,b)=1"; "this contradicts our assumption that …"; "therefore $P$P, as required". Phrases that lose marks: "let's say $\sqrt{2}$2​ is rational" (informal — markers want "assume for contradiction"); "so $\sqrt{2}$2​ can't be rational" (no explicit identification of the contradiction); ending the proof at the contradiction without a final concluding sentence. The proof must read as a self-contained logical document, not a stream of working.

A specific AQA pattern: questions phrased "Prove, by contradiction, that …" require the contradiction method. A correct direct proof of the same statement scores zero — the method is part of the assessment. Read the command word precisely.

---

Grade-band model answers

3-mark question

Question: Prove, by contradiction, that if $n^2$n2 is odd then $n$n is odd, where $n$n is an integer.

Grade C response (~180 words):

Assume $n$n is even. Then $n = 2k$n=2k for some integer $k$k. So $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$n2=(2k)2=4k2=2(2k2), which is even. But this contradicts the fact that $n^2$n2 is odd. So $n$n must be odd.