Some of the most beautiful results in mathematics, $\sqrt{2}$ is irrational, there are infinitely many primes, no smallest positive rational exists, share one technique. Assume the opposite of what you want, follow the consequences, and reach an impossibility. The contradiction forces the original claim. This lesson teaches the structure and the three classics that every Extension 2 student must know.
Start with the warm-up and record your first reasoning.
If $n^2$ is even, what can you say about $n$? Before checking write the contrapositive ("if $n$ is odd, then $n^2$ is odd") and prove that one-line algebra. Then explain why this fact will be needed inside the $\sqrt{2}$ irrational proof.
Orient yourself to the lesson goals, language, and core approach.
Every contradiction proof rewards two habits: negate the claim cleanly (write down what "assume the opposite" actually means), then drive forward by deduction until two of your deductions disagree. Skipping the explicit negation step is the most common cause of a stalled proof.
The assume-deduce-contradict structure: (1) Assume $\neg P$ (the opposite of what you want), (2) Derive consequences step by step, (3) Reach a statement of the form $A \wedge \neg A$, (4) Conclude $P$ must be true.
If $\neg P \Rightarrow (A \wedge \neg A)$, then $P$ must be true.
Work through the concept and complete its check.
To prove a statement $P$ by contradiction:
Worked through the hook ($\sqrt{2}$ is irrational):
Four steps: assume $\neg P$, deduce, contradict, conclude · $\sqrt{2}$ irrational: assume $\sqrt{2} = p/q$ in lowest terms; show $2 \mid p$ and $2 \mid q$; contradicts $\gcd = 1$ · Always state the assumption explicitly at the start · The contradiction must be a specific statement of form $A \wedge \neg A$
Pause, copy the four contradiction steps and the $\sqrt{2}$ irrationality proof skeleton (assume $p/q$ in lowest terms, show $2 \mid p$ and $2 \mid q$, contradict $\gcd = 1$) into your book.
Quick check: In the standard proof that $\sqrt{2}$ is irrational, what is the explicit contradiction reached?
Build the next proof move and complete its check.
We just saw the four-step contradiction template: assume $\neg P$, deduce, reach $A \wedge \neg A$, conclude. That raises a question: can this technique handle an infinite set? This card answers it → Euclid's proof that infinitely many primes exist, using $N = p_1 \cdots p_n + 1$ to force a contradiction.
Euclid's argument is the canonical contradiction proof. Claim: there are infinitely many prime numbers.
Assume finitely many primes: $p_1, \ldots, p_n$ · Let $N = p_1 \cdots p_n + 1$ · $N$ has a prime factor $q$, but $q \neq p_i$ for any $i$ (since $p_i \nmid N$) · Contradiction, list was supposed to contain ALL primes · $N$ itself is NOT necessarily prime (e.g., $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \times 509$)
Pause, copy Euclid's construction $N = p_1 \cdots p_n + 1$, the argument that no $p_i$ divides $N$, and the warning that $N$ need not itself be prime, into your book.
Did you get this? True or false: in Euclid's proof of infinitely many primes, the number $N = p_1 p_2 \cdots p_n + 1$ is itself guaranteed to be prime.
Follow the worked examples, then complete the check.
Worked examples · 3 in a row, reveal as you go
Prove by contradiction that $\sqrt{2}$ is irrational, citing every step.
Prove by contradiction that there is no smallest positive rational number.
Prove by contradiction that there are infinitely many prime numbers.
Fill the gap: To prove $P$ by contradiction, you assume , derive a contradiction of the form $A \wedge \neg A$, and conclude that $P$ must be .
Correct the common traps and test your understanding.
Misconceptions to fix · the 3 traps that cost marks
Did you get this? True or false: the same contradiction proof structure used for $\sqrt{2}$ can be adapted to prove that $\sqrt{3}$ is irrational, by using the lemma "if $3 \mid n^2$ then $3 \mid n$".
Complete the practice activities and revisit your opening thinking.
Activities · practice with the ideas
Prove by contradiction that $\sqrt{3}$ is irrational. Use the lemma "if $3 \mid n^2$ then $3 \mid n$".
Prove by contradiction that there is no largest natural number.
Prove by contradiction that if $n^2$ is odd, then $n$ is odd. (Note: the direct proof uses the contrapositive, but you can also do this by contradiction.)
Prove that the sum of a rational and an irrational is irrational.
Show that there are infinitely many primes of the form $4k + 3$. (Adapt Euclid's argument; consider $N = 4 p_1 p_2 \cdots p_n - 1$.)
Odd one out: Three of these are correct steps in the proof that $\sqrt{2}$ is irrational. Which one is NOT?
Earlier you analysed $2q^2 = p^2$ and predicted what it told you about $p$ and $q$.
$2q^2 = p^2$ forces $p^2$ even, so $p$ even (by the lemma); writing $p = 2k$ then forces $q^2 = 2k^2$, so $q^2$ even, so $q$ even. The hidden contradiction with $\gcd(p,q) = 1$ surfaces at this step, both $p$ and $q$ share factor 2. The proof's elegance is in how the lowest-terms assumption is precisely the seed of its own destruction.
Multiple choice, then short answer under exam conditions.
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. State the structure of a proof by contradiction in four numbered steps. (2 marks)
Q2. Prove by contradiction that $\sqrt{2}$ is irrational. (3 marks)
Q3. Prove by contradiction that there are infinitely many prime numbers. Be explicit about what is contradicted. (3 marks)
Activity answers:
1. Assume $\sqrt{3} = p/q$ with $\gcd(p,q)=1$. Then $3q^2 = p^2$, so $3 \mid p^2$, hence $3 \mid p$. Write $p = 3k$: $3q^2 = 9k^2 \Rightarrow q^2 = 3k^2$, so $3 \mid q^2$ and $3 \mid q$. Both divisible by 3 contradicts $\gcd(p,q) = 1$. $\therefore \sqrt{3}$ is irrational.
2. Suppose $N \in \mathbb{N}$ is the largest. Then $N + 1 \in \mathbb{N}$ and $N + 1 > N$, contradicting the assumption that $N$ is largest. $\therefore$ no largest natural exists.
3. Assume $n^2$ odd but $n$ even. Then $n = 2k$, so $n^2 = 4k^2 = 2(2k^2)$, which is even, contradicting $n^2$ odd. $\therefore$ $n$ must be odd.
4. Let $r$ rational, $x$ irrational. Assume $r + x = s$ is rational. Then $x = s - r$; since rationals are closed under subtraction, $x$ is rational, contradicting $x$ irrational. $\therefore r + x$ is irrational.
5. Suppose only finitely many primes $\equiv 3 \pmod 4$: $p_1, \ldots, p_n$. Let $N = 4 p_1 \cdots p_n - 1 \equiv -1 \equiv 3 \pmod 4$. Since $N$ is odd, all its prime factors are odd. Not every odd prime factor can be $\equiv 1 \pmod 4$ (product of such is $\equiv 1$, but $N \equiv 3$); so some prime factor $q \equiv 3 \pmod 4$. But $q \neq p_i$ for any $i$ (else $q \mid 1$). Contradiction.
Q1 (2 marks): (1) Assume the negation $\neg P$ [1]; (2) deduce consequences; (3) reach a contradiction $A \wedge \neg A$; (4) conclude $P$ holds [1].
Q2 (3 marks): Assume $\sqrt{2} = p/q$ in lowest terms, $\gcd(p,q) = 1$ [1]. Then $p^2 = 2q^2$, so $p^2$ even, so $p$ even; write $p = 2k$: $q^2 = 2k^2$, so $q$ even [1]. Both $p$ and $q$ even contradicts $\gcd = 1$, hence $\sqrt{2}$ irrational [1].
Q3 (3 marks): Assume finitely many primes $p_1, \ldots, p_n$ [1]. Let $N = p_1 \cdots p_n + 1$; $N > 1$ has a prime factor $q$ [1]. Since $p_i \mid p_1 \cdots p_n$ but $p_i \nmid 1$, $p_i \nmid N$, so $q \neq p_i$, contradicts the list being complete [1].
Sit the module quiz, then close the lesson off.
A full module quiz covering every lesson in this module, not just this one. Set aside a decent block of time and treat it like a real assessment.
Start the module quiz →Tick when you've finished the practice and review.
Work through this topic 1-on-1 with an experienced HSC tutor.
Book a free session →