Proof by Contradiction
Proving statements by showing their opposite leads to impossibility
SPEC 1.1 • PROOF
When to Use This Method
Proof by contradiction is particularly useful for proving:
Type of StatementExample
A number is irrational√2 is irrational
There are infinitely many of somethingThere are infinitely many primes
Something does not existThere is no largest prime
Negative statementsNo integer n satisfies n² = 2
Key Insight
If assuming the opposite of what you want to prove leads to something impossible, then what you wanted to prove must be true.
The Method
1
Assume the opposite of what you want to prove
"Assume, for contradiction, that..."
2
Work logically from this assumption
Use algebra, known facts, and valid reasoning
3
Reach a contradiction
Arrive at something impossible or self-contradictory
4
Conclude the original statement must be true
"This is a contradiction, therefore..."
Important
The contradiction must genuinely follow from your assumption. Common contradictions include: a number being both even and odd, 1 = 0, or a positive number being negative.
Key Technique: Proving Irrationality
Definition
A rational number can be written as where a and b are integers with b ≠ 0.
We can always write this fraction in lowest terms (a and b have no common factors other than 1).
Strategy
To prove a number is irrational:
Assume it IS rational, so it equals in lowest terms
Manipulate algebraically
Show a and b must share a common factor
This contradicts "lowest terms" → the number is irrational
Tip
"In lowest terms" means a and b are coprime (HCF = 1). They cannot both be even, both divisible by 3, etc.
Worked Example01
Prove that √2 is irrational.
•
Assume, for contradiction, that √2 is rational.
•
Then √2 = where a, b are integers with no common factors (lowest terms).
•
Squaring both sides: 2 = , so a² = 2b²
•
Therefore a² is even, which means a must be even. Write a = 2k.
•
Substituting: (2k)² = 2b², so 4k² = 2b², giving b² = 2k²
•
Therefore b² is even, which means b must be even.
•
Contradiction: Both a and b are even, so they share factor 2. But we said they had no common factors!
•
∴ Our assumption was wrong. √2 is irrational. ✓
Worked Example02
Prove that √3 is irrational.
•
Assume, for contradiction, that √3 is rational.
•
Then √3 = where a, b are integers in lowest terms (no common factors).
•
Squaring: 3 = , so a² = 3b²
•
Therefore a² is divisible by 3, which means a is divisible by 3. Write a = 3k.
•
Substituting: (3k)² = 3b², so 9k² = 3b², giving b² = 3k²
•
Therefore b² is divisible by 3, which means b is divisible by 3.
•
Contradiction: Both a and b are divisible by 3, but they should have no common factors!
•
∴ Our assumption was wrong. √3 is irrational. ✓
Key Fact: Divisibility of Squares
Key Result
If p is prime and p divides n², then p divides n
This is because prime factors in n² come in pairs from n × n.
Why This Matters
If 2 divides a², then 2 divides a (so a is even)
If 3 divides a², then 3 divides a
If 5 divides a², then 5 divides a
Exam Tip
You can state this fact in your proof. Write: "If a² is divisible by 2, then a must be divisible by 2 (since if a were odd, a² would be odd)."
Worked Example03
Prove that √5 is irrational.
•
Assume, for contradiction, that √5 is rational.
•
Then √5 = where a, b are integers in lowest terms.
•
Squaring: a² = 5b²
•
So 5 | a² (5 divides a²), which means 5 | a. Write a = 5k.
•
Then (5k)² = 5b², so 25k² = 5b², giving b² = 5k²
•
So 5 | b² which means 5 | b.
•
Contradiction: Both a and b are divisible by 5, contradicting lowest terms.
•
∴ √5 is irrational. ✓
Worked Example04
Prove that there are infinitely many prime numbers.
•
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
•
N is larger than all the primes, so N is not prime (by our assumption).
•
So N must be divisible by some prime pᵢ from our list.
•
But dividing N by any pᵢ gives remainder 1 (since N = product of all primes + 1).
•
Contradiction: N is not divisible by any prime in our list, but every integer > 1 must have a prime factor!
•
∴ Our assumption was wrong. There are infinitely many primes. ✓
Worked Example05
Prove that there is no largest even number.
•
Assume, for contradiction, that there IS a largest even number.
•
Call this largest even number E.
•
Consider E + 2.
•
Since E is even, E = 2k for some integer k.
•
So E + 2 = 2k + 2 = 2(k + 1), which is also even.
•
And E + 2 > E.
•
Contradiction: We found an even number (E + 2) larger than the "largest" even number E!
•
∴ Our assumption was wrong. There is no largest even number. ✓
Worked Example06
Prove that the sum of a rational number and an irrational number is irrational.
•
Let r be rational and x be irrational. We want to prove r + x is irrational.
•
Assume, for contradiction, that r + x is rational.
•
Then r + x = for some integers a, b (b ≠ 0).
•
Since r is rational, r = for some integers c, d (d ≠ 0).
•
Then x = (r + x) − r =
•
This is a fraction of integers, so x is rational.
•
Contradiction: We said x is irrational, but we've shown x is rational!
•
∴ Our assumption was wrong. r + x is irrational. ✓
Worked Example07
Prove that there are no positive integers x and y such that x² − y² = 1.
•
Assume, for contradiction, that positive integers x and y exist with x² − y² = 1.
•
Factorise: (x + y)(x − y) = 1
•
Since x and y are positive integers, x + y is a positive integer ≥ 2.
•
For the product to equal 1, we need (x + y) = 1 and (x − y) = 1.
•
But x + y ≥ 2 (since x ≥ 1 and y ≥ 1), so (x + y) cannot equal 1.
•
Contradiction: We cannot have (x + y)(x − y) = 1 with positive integers.
•
∴ No positive integers x and y satisfy x² − y² = 1. ✓
Practice
Question 1: Prove that √7 is irrational.
Assume, for contradiction, that √7 is rational.
Then √7 = where a, b are integers in lowest terms.
Squaring: a² = 7b²
So 7 | a² which means 7 | a. Write a = 7k.
Then 49k² = 7b², so b² = 7k², meaning 7 | b.
Contradiction: Both a and b are divisible by 7, but they should have no common factors!
∴ √7 is irrational. ✓
Practice
Question 2: Prove that if n² is even, then n is even.
Assume, for contradiction, that n² is even but n is odd.
If n is odd, then n = 2k + 1 for some integer k.
Then n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1
This is of the form 2m + 1, so n² is odd.
Contradiction: We said n² is even, but we've shown n² is odd!
∴ Our assumption was wrong. If n² is even, then n is even. ✓
Practice
Question 3: Prove that there is no smallest positive rational number.
Assume, for contradiction, that there IS a smallest positive rational number.
Call this smallest positive rational r.
Consider .
Since r is rational, r = , so , which is also rational.
Also, (since r > 0) and .
Contradiction: We found a positive rational () smaller than the "smallest" positive rational r!
∴ There is no smallest positive rational number. ✓
Summary
Key Concepts
ConceptDescription
The MethodAssume opposite → derive contradiction → original statement is true
Irrationality ProofsAssume rational (a/b in lowest terms) → show common factor → contradiction
Infinity ProofsAssume finite → construct something bigger → contradiction
Non-existenceAssume it exists → derive impossibility → it doesn't exist
Exam Skills
Start clearly: "Assume, for contradiction, that..."
State your contradiction explicitly: "This is a contradiction because..."
Conclude properly: "Therefore our assumption was wrong, and..."
For √p proofs: Use "in lowest terms" and show both a and b share factor p
Next: When to Use This Method