Proof by Contradiction
Assume the opposite. Derive chaos. Conclude truth. Proof by contradiction — reductio ad absurdum — is one of mathematics' most elegant weapons. In this lesson you'll use it to prove $\sqrt{2}$ is irrational, that infinitely many primes exist, and more. Master the four-step structure and you'll never miss marks on these proofs again.
Is $\sqrt{2}$ rational? Without looking at a proof — write what you think happens when you try to write $\sqrt{2} = \frac{p}{q}$ in lowest terms and then square both sides.
Proof by contradiction (Latin: reductio ad absurdum) works like this: to prove statement $P$, assume $\neg P$ is true, then derive a logical impossibility. Since the only change was assuming $\neg P$, that assumption must be wrong — so $P$ must be true.
This is especially powerful for negative statements: things that are irrational, infinite, impossible, or unique. Direct proof often cannot easily establish these, but contradiction can.
Assume $\neg P$ ⇒ derive $\bot$ ⇒ conclude $P$
Key facts
- Proof by contradiction assumes $\neg P$ and derives a logical impossibility
- The four steps: assume negation, deduce, find contradiction, conclude
- Irrational numbers cannot be written as $\frac{p}{q}$ with $p, q$ integers and $q \neq 0$
Concepts
- Why assuming the negation forces the existence of a contradiction
- The role of "coprime" (no common factors) in irrationality proofs
- When contradiction is more natural than direct proof or induction
Skills
- Prove $\sqrt{2}$ is irrational using contradiction
- Prove there are infinitely many primes
- Prove "if $n^2$ is even, then $n$ is even"
- Write exam-ready contradiction proofs with explicit conclusions
Every proof by contradiction follows the same skeleton. Memorise it and you have the scaffold for any question of this type.
Step 1 — Assume the opposite. Write: "Suppose, for contradiction, that [negation of what we want to prove]."
Step 2 — Logical deduction. Use valid algebra or logic to derive consequences from that assumption.
Step 3 — Reach a contradiction. Show the assumption leads to something impossible: e.g. $0 = 1$, or an even number is odd, or $p$ and $q$ are both even in a supposedly lowest-terms fraction.
Step 4 — Conclude. "This is a contradiction. Therefore [original statement] must be true. $\square$"
Quick check: In a proof by contradiction for the statement "$\sqrt{3}$ is irrational", what is the correct opening assumption?
Every proof by contradiction follows the same skeleton. Memorise it and you have the scaffold for any question of this type.
Pause — copy the four-step proof-by-contradiction skeleton with the classic $\sqrt{2}$ irrational example into your book.
Worked examples · 3 classic contradiction proofs
Prove that $\sqrt{2}$ is irrational.
Prove that there are infinitely many prime numbers.
Prove that if $n^2$ is even, then $n$ is even.
Did you get this? True or false: in the proof that $\sqrt{2}$ is irrational, the contradiction arises because $p$ and $q$ both turn out to be even, violating the assumption that $\gcd(p,q) = 1$.
Fill the gap: In Euclid's proof, the number $N = p_1 p_2 \cdots p_n + 1$ is not divisible by any $p_i$ because the remainder is always .
Misconceptions to fix · the 4 traps that cost marks
Did you get this? True or false: proof by contradiction and proof by contrapositive are the same technique.
Activities · write the proofs yourself
Prove by contradiction that $\sqrt{3}$ is irrational. Follow the four-step structure.
Prove by contradiction that there is no largest prime number.
Prove by contradiction: if $n^3$ is odd, then $n$ is odd.
Identify the error: "To prove $\sqrt{5}$ is irrational, suppose $\sqrt{5}$ might be rational. Then..."
Explain in one sentence why the $\gcd(p,q) = 1$ assumption is critical in the $\sqrt{2}$ proof.
Odd one out: Three of these are valid examples of a "contradiction" in a proof. Which one is NOT a genuine contradiction?
At the start you considered whether $\sqrt{2} = \frac{p}{q}$ in lowest terms. The proof showed that squaring forces both $p$ and $q$ to be even — directly contradicting the "lowest terms" condition. The same pattern ($p^2 = kq^2$ forcing $k \mid p$, then $k \mid q$) works for $\sqrt{3}$, $\sqrt{5}$, and any $\sqrt{m}$ where $m$ is not a perfect square.
Pick your answer, then rate your confidence — that tells the system what to drill next. Each retry pulls a fresh mix from the bank.
Q1. Prove by contradiction that $\sqrt{3}$ is irrational. (3 marks)
Q2. Prove by contradiction that there is no largest prime number. (2 marks)
Q3. Explain why the assumption "$\gcd(p, q) = 1$" (lowest terms) is essential in the proof that $\sqrt{2}$ is irrational. (2 marks)
Comprehensive answers (click to reveal)
Activity answers:
1. Assume $\sqrt{3} = p/q$, $\gcd(p,q)=1$. Then $p^2 = 3q^2$, so $3 \mid p^2$, so $3 \mid p$ (since 3 is prime). Write $p = 3m$: $9m^2 = 3q^2$, so $q^2 = 3m^2$, so $3 \mid q$. Contradiction with $\gcd(p,q)=1$. $\square$
2. Suppose $p$ is the largest prime. By Euclid's argument, $N = 2 \cdot 3 \cdots p + 1$ is not divisible by any prime $\leq p$, so it has a prime factor $> p$. Contradiction. $\square$
3. If $n^3$ is odd and $n$ is even, write $n = 2k$. Then $n^3 = 8k^3 = 2(4k^3)$, which is even. Contradiction. $\square$
4. Error: "might be rational" is not the exact negation. Should say "is rational", i.e. $\sqrt{5} = p/q$ with $\gcd(p,q) = 1$.
5. The $\gcd(p,q)=1$ assumption is the statement we ultimately contradict. Without it, finding that both $p$ and $q$ are even is not a contradiction — they could legitimately share a factor.
Q1 (3 marks): [1] Correctly assumes $\sqrt{3} = p/q$ with $\gcd(p,q)=1$. [1] Derives $3 \mid p$ and then $3 \mid q$. [1] States contradiction with $\gcd(p,q)=1$ and concludes.
Q2 (2 marks): [1] Assumes finite list and constructs $N = p_1\cdots p_n + 1$. [1] Shows $N$ has an unlisted prime factor — contradiction.
Q3 (2 marks): [1] The $\gcd = 1$ condition is what allows a contradiction when both $p$ and $q$ are found to be even. [1] Without this condition, the proof collapses because there is nothing to contradict.
Five timed questions on proof by contradiction. Beat the boss to bank a tier — gold (90% + speed), silver (75%), or bronze (50%). Replays welcome.
⚔ Enter the arenaClimb platforms by answering proof by contradiction questions. Lighter alternative to the boss.
Mark lesson as complete
Tick when you've finished the practice and review.