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 proofwrite 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 confidencethat 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.