STEP 1 OF 23 · Lesson Opening

Today: Proof by Contradiction — the 4-step framework

Pass 1 of proof writing. We add a single, devastating move: "Suppose the conclusion is false." From there, every great irrationality proof, every "infinitely many primes" argument, every $p^2 \text{ even} \Rightarrow p \text{ even}$ collapse follows the same 4-step shape.

📌 What you will learn today

Topic: Proof by contradiction. The 4-step framework (assume / derive / contradict / conclude). Classic targets: $\sqrt{2}$ irrational, infinitude of primes, contrapositive transformation.
Category: Proof writing (Pass 1) — sub-topic Proof by Contradiction Basics.
Solves these AIMO problems: 2018 Q9 (partial)
Plus the synthesis problem at Step 22 — proving that in $a^2+b^2=c^2$, at least one of $a,b$ is even.
AoPS Reference: Introduction to Number Theory by Mathew Crawford and Art of Problem Solving Vol. 2, chapter on logic and proof methods.
Why this matters: Roughly half of all hard AIMO Q9 problems begin with the phrase "Prove that…", and a large fraction of those cannot be attacked head-on. Contradiction lets you assume the conclusion is wrong, then ride to a clearly absurd statement (like an integer equalling a fraction). Pass 1 target: write the setup + several cases on AIMO 2018 Q9 and lock in 2–3 of 5 partial marks.
Time required: About 80–95 minutes for the full lesson, plus practice papers.

How this lesson is structured

Phase 0 (Steps 2–3): Prerequisites — the contrapositive law, and what counts as a "contradiction".
Phase 1 (Steps 4–5): Two visual pictures — the "assume wrong → derive nonsense → therefore right" flowchart, and the four-route map.
Phase 1.5 (Step 6): Formula handbook — sentence templates plus the four standard contradiction routes.
Phase 2 (Steps 7–8): Two guided derivations — full $\sqrt{2}$ irrationality proof, and Euclid's infinite primes proof.
Phase 3 (Steps 9–13): Five worked examples ⭐⭐⭐ → ⭐⭐⭐⭐⭐.
Phase 4 (Step 14): Four practice problems (P1–P4) with Hint / Answer / Solution.
Phase 5 (Step 15): AIMO 2018 Q9 — partial-mark target with gradeProof rubric scoring.
Phase 5.5 (Step 16): Synthesis problem — Pythagorean triples mod 4.
Steps 17–18: Atomic-skill matrix + 4 micro-validations.
Steps 19–21: Cheat sheet, ⭐ self-assessment, error book.
Steps 22–23: Wrap-up + bridge to Part 3 (Geometric Proof Writing).

Pedagogy: Pass 1 — assumes Part 1 (Mathematical Induction Basics) is comfortable. We deliberately defer strong induction, double-induction, and the extremal principle to W15 Pass 2. Today the goal is the 4-step shape: state assumption clearly, derive a clean consequence, hit a contradiction, write the conclusion sentence. Even half-finished, the structure carries marks.

STEP 2 OF 23 · Phase 0 · Prerequisite

Prerequisite ① — The contrapositive law

Every "if $P$ then $Q$" statement has a logical twin: "if not-$Q$ then not-$P$". They are equivalent. This is the engine behind contradiction.

The dictionary

Statement: $P \Rightarrow Q$. ("If it rains, the ground is wet.")
Contrapositive: $\neg Q \Rightarrow \neg P$. ("If the ground is not wet, it did not rain.")
Converse (NOT equivalent!): $Q \Rightarrow P$. ("If the ground is wet, it rained." — could be a sprinkler.)
Negation of $P \Rightarrow Q$: $P$ is true and $Q$ is false. (To disprove an implication, find one such case.)

The contrapositive is logically identical to the original. So proving "if not-$Q$ then not-$P$" is the same as proving "if $P$ then $Q$" — just a different way in.

The contrapositive law

$(P \Rightarrow Q) \;\Longleftrightarrow\; (\neg Q \Rightarrow \neg P)$

Example

"If $n^2$ is even, then $n$ is even." ⇔ "If $n$ is odd, then $n^2$ is odd." (Easier to prove the right side directly!)

🔑 Why contradiction works. "Suppose for contradiction $P$ is true and $Q$ is false." Then derive a known-false statement (like $0 = 1$). The only way out is that the supposition was wrong — i.e. $P \Rightarrow Q$ holds. Contradiction = contrapositive in the special case where "$\neg P$" is something already known to be true (an axiom, a definition, a previous theorem).

"If $x > 0$ then $x^2 > 0$." Which of these is the contrapositive?
(A) If $x \le 0$ then $x^2 \le 0$. (B) If $x^2 \le 0$ then $x \le 0$. (C) If $x^2 > 0$ then $x > 0$.
Enter A, B, or C as 1, 2, 3.

STEP 3 OF 23 · Phase 0 · Prerequisite

Prerequisite ② — What counts as a "contradiction"?

A contradiction is any statement of the form $A \wedge \neg A$ — something you have proved is both true and false simultaneously. In olympiad practice, four routes show up overwhelmingly often.

The four standard contradiction routes

R1. Integer = non-integer. "We derived that some quantity equals a non-integer fraction $p/q$ with $q \ne \pm 1$, but the same quantity was set to be an integer." (Powers $\sqrt{2}$ proof.)
R2. $p \mid a$ and $p \nmid a$. "We derived that some prime $p$ divides $a$ from one chain of reasoning, and does not divide $a$ from another." (Powers Euclid's primes proof.)
R3. Finite vs infinite. "We assumed only finitely many objects exist, then constructed a new one outside the list." (Powers infinitude of primes.)
R4. Min/max contradiction. "We assumed $n$ is the minimal counterexample, then constructed a smaller one." (Powers Fermat-style descent.)

Pass 1 today focuses on R1, R2, R3. R4 (descent / extremal) is deferred to W15 Pass 2.

Four standard contradiction routes. Today (Pass 1) we drill R1, R2, R3. R4 (extremal / descent) is the deeper Pass 2 technique.

🔑 The "smell test" for contradiction problems. If a problem says "Prove that no such $x$ exists" or "Prove that $\sqrt{n}$ is irrational" or "Prove that there are infinitely many…" — these are classic contradiction triggers. The negation of the goal is concrete and useful.

Which contradiction route would you use to prove $\sqrt{5}$ is irrational? Answer 1=R1, 2=R2, 3=R3, 4=R4.

STEP 4 OF 23 · Phase 1 · Visual Intuition

Visual ① — "假定我们错了 → 推出荒唐 → 所以我们是对的"

The whole machinery of contradiction in one flowchart. Memorise the shape — every proof you write today follows it.

The 4-step contradiction framework. Steps 1, 3, 4 are mostly writing: opening line, contradiction line, closing line. Step 2 is where the real maths lives.

🔑 Mark allocation insight. AIMO Q9 markers give partial credit by step. Writing Step 1 ("Suppose for contradiction…") earns 1 mark even with no further work. Step 4 ("Therefore… ∎") earns another. So just by setting up the right scaffold you bank 2/5 — even before any algebra.

STEP 5 OF 23 · Phase 1 · Visual Intuition

Visual ② — Map of the four routes

Once you have assumed the negation, the real question is: which contradiction will you ride to? The four routes are not equally common — and recognising which one fits is half the battle.

From a single assumption, four diverging routes. In Pass 1 we focus on R1 (irrationality), R2 (divisibility), and R3 (Euclid). R4 (descent / minimal-counterexample) is the W15 specialty.

Pattern recognition shortcut. If the goal mentions √, irrational, ratio → R1. If it mentions divides, multiple, modulo, even/odd → R2. If it mentions infinitely many, no largest, unbounded → R3. If it mentions smallest counterexample, descent → R4 (Pass 2).

STEP 6 OF 23 · Phase 1.5 · Formula Handbook

Sentence templates + four contradiction routes

These are the exact sentences you will paste into your proofs today. Memorise them — they are worth marks even when the algebra is incomplete.

F1 · The opening sentence (Step 1)

"Suppose, for contradiction, that $\neg Q$."

Variants

"Assume the contrary..." · "Suppose not, so..." · "Suppose to the contrary that $\sqrt{2} = p/q$ in lowest terms."

F2 · The derivation linker (Step 2)

"Then ... · So ... · Hence ... · It follows that ..."

Style note

Use one connector per logical step. Markers love seeing the chain. Avoid burying derivations inside long sentences.

F3 · The contradiction line (Step 3)

"This contradicts ⟨known fact⟩."

Common known facts to invoke

"...contradicts $\gcd(p, q) = 1$." · "...contradicts $n$ being an integer." · "...contradicts the assumption that the list was complete."

F4 · The closing sentence (Step 4)

"Therefore $Q$. ∎"

Variants

"Hence $\sqrt{2}$ is irrational. ∎" · "Therefore there are infinitely many primes. ∎" · "Thus the assumption fails, so $Q$ holds. ∎"

The four standard contradiction routes — when to use each

Route	Trigger words in goal	Negation produces	Ride to
R1 · int = frac	"irrational", "$\sqrt{n}$", "ratio cannot equal..."	$\sqrt{n} = p/q$ in lowest terms	$p, q$ both even ⇒ contradicts lowest-terms
R2 · $p \mid a$ and $p \nmid a$	"divides", "even / odd", "multiple of $k$"	some integer relation	derive both $p \mid x$ and $p \nmid x$ for the same $x$
R3 · finite vs infinite	"infinitely many", "no largest", "unbounded"	"only finitely many: $a_1, \dots, a_N$"	construct $a_{N+1}$ outside the list
R4 · min/max (W15)	"smallest counterexample", "descent"	"let $n$ be minimal..."	build a smaller counterexample $n' < n$

F5 · Contrapositive transformation (the silent twin)

F5 · Equivalence

$(P \Rightarrow Q) \;\Longleftrightarrow\; (\neg Q \Rightarrow \neg P)$

When to use

If $\neg Q$ is concrete (e.g. "$n$ is odd") and $\neg P$ is easy to derive directly (e.g. "$n^2$ is odd"), prove the contrapositive instead. This is technically not contradiction — it's a direct proof of the equivalent statement — but it shares the same "negate the conclusion" entry.

For "Prove that the cube root of 2 is irrational", which route fits best? (1=R1, 2=R2, 3=R3, 4=R4)

STEP 7 OF 23 · Phase 2 · Guided Derivation

Derivation ① — $\sqrt{2}$ is irrational (route R1)

The most famous contradiction proof in mathematics. We walk through every line so you can re-execute it from memory.

Goal

Prove that $\sqrt{2}$ is irrational, i.e. cannot be written as $p/q$ with $p, q$ integers.

Step 1 — Assume the contrary

Sentence: "Suppose, for contradiction, that $\sqrt{2}$ is rational. Then we may write $\sqrt{2} = p/q$ where $p, q$ are positive integers with $\gcd(p, q) = 1$ (lowest terms)."

Step 2 — Derive a clean consequence

Squaring: $2 = p^2 / q^2$, so $p^2 = 2q^2$. (*) From (*), $p^2$ is even. Lemma: if $p^2$ is even then $p$ is even. (See WE 3 — contrapositive proof.) Write $p = 2k$ for some integer $k$. Substitute into (*): $(2k)^2 = 2q^2$, so $4k^2 = 2q^2$, so $q^2 = 2k^2$. Hence $q^2$ is even, so $q$ is even (same lemma).

Step 3 — Hit the contradiction (R1: divisibility clash with assumption)

Both $p$ and $q$ are even. So $2 \mid \gcd(p, q)$. But we assumed $\gcd(p, q) = 1$. Contradiction.

Step 4 — Conclude

Sentence: "The supposition that $\sqrt{2}$ is rational is therefore false. Hence $\sqrt{2}$ is irrational. ∎"

$\sqrt{2}$ is irrational. ∎

🔑 The shape of the win. All R1 irrationality proofs follow this exact 4-step skeleton: assume $\sqrt{n} = p/q$ in lowest terms, square, derive that some prime divides both $p$ and $q$, contradict lowest-terms. WE 1 (next-but-one step) replays it for $\sqrt{3}$.

Common slip. Forgetting to write "in lowest terms" / "$\gcd(p,q) = 1$" in Step 1 destroys the proof. Without that assumption, "$p$ even and $q$ even" is just a statement, not a contradiction. Always include the lowest-terms condition.

STEP 8 OF 23 · Phase 2 · Guided Derivation

Derivation ② — There are infinitely many primes (Euclid, route R3)

The most elegant contradiction in number theory. Same 4-step shape, this time riding route R3 (finite vs infinite).

Goal

Prove that there are infinitely many prime numbers.

Step 1 — Assume the contrary

Sentence: "Suppose, for contradiction, that there are only finitely many primes, namely $p_1, p_2, \dots, p_N$ (the complete list)."

Step 2 — Derive a clean consequence (the construction)

Define $M = p_1 \cdot p_2 \cdots p_N + 1$. $M$ is a positive integer with $M \ge 2$. By the fundamental theorem of arithmetic, $M$ has at least one prime factor — call it $q$. By our (assumed-complete) list, $q$ must equal one of $p_1, \dots, p_N$.

Step 3 — Hit the contradiction (R2-flavoured: $q \mid M$ and $q \nmid M$)

$q \mid p_1 p_2 \cdots p_N$ (since $q$ is one of them). $q \mid M = p_1 p_2 \cdots p_N + 1$ (just established). Subtracting: $q \mid (M - p_1 p_2 \cdots p_N) = 1$. But $q$ is prime, so $q \ge 2$. A prime cannot divide $1$. Contradiction.

Step 4 — Conclude

Sentence: "The supposition that the list of primes was finite is therefore false. Hence there are infinitely many primes. ∎"

There are infinitely many primes. ∎

🔑 Subtle point. The argument does not claim that $M$ is itself prime. (Often it isn't — e.g. $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509$.) The argument only requires that $M$ has some prime factor, and that this prime cannot be on the original list. WE 2 will replay this in detail with care about the construction step.

STEP 9 OF 23 · Phase 3 · Worked Example 1

WE 1 — Prove $\sqrt{3}$ is irrational

⭐⭐⭐ · P2-A1 + P2-A2 · mirror $\sqrt{2}$

Prove that $\sqrt{3}$ is irrational.

Read the structure

Goal of the form "$\sqrt{n}$ is irrational" → route R1, mirror the $\sqrt{2}$ proof. The key lemma changes from "$p^2$ even ⇒ $p$ even" to "$3 \mid p^2 \Rightarrow 3 \mid p$".

Step 1 — Assume

Suppose, for contradiction, that $\sqrt{3} = p/q$ where $p, q$ are positive integers with $\gcd(p, q) = 1$.

Step 2 — Derive

Squaring: $3 = p^2/q^2$, so $p^2 = 3q^2$. (*) $3 \mid p^2$. By the lemma below, $3 \mid p$. Write $p = 3k$. Substitute: $9k^2 = 3q^2$, so $q^2 = 3k^2$. $3 \mid q^2$, so $3 \mid q$.

Lemma: If $3 \mid p^2$ then $3 \mid p$. Proof (contrapositive): if $3 \nmid p$ then $p \equiv \pm 1 \pmod 3$, so $p^2 \equiv 1 \pmod 3$, so $3 \nmid p^2$. ✓

Step 3 — Contradict

Both $p$ and $q$ are divisible by $3$. So $3 \mid \gcd(p, q)$. But we assumed $\gcd(p, q) = 1$. Contradiction.

Step 4 — Conclude

Therefore $\sqrt{3}$ is irrational. ∎

Self-check (using gradeProof): Re-write the proof in the box below. Award yourself one mark per keyword the rubric finds (max 5).

Your $\sqrt{3}$ irrational proof:

Rubric — keywords sought

suppose, contradiction, assume, derive, contradict, therefore, thus, hence, qed. Score = number of distinct keywords matched (max 5).

$\sqrt{3}$ is irrational. ∎

STEP 10 OF 23 · Phase 3 · Worked Example 2

WE 2 — Prove no largest prime exists (Euclid full)

⭐⭐⭐⭐ · P2-A2 · Euclid construction

Prove that there is no largest prime number.

Read the structure

Equivalent to "infinitely many primes". Route R3 (finite vs infinite). Construct a number that forces a prime outside any supposed largest one.

Step 1 — Assume

Suppose, for contradiction, that there is a largest prime $P$. Then the complete list of primes is $p_1 = 2, p_2 = 3, \dots, p_N = P$ (some finite list ending at $P$).

Step 2 — Derive

Define $M = (2 \cdot 3 \cdot 5 \cdots P) + 1 = (\prod_{i=1}^{N} p_i) + 1$. $M \ge 2$ (in fact $M \ge 7$ since $2 \cdot 3 + 1 = 7$). $M$ has a prime factor $q$ (by the fundamental theorem of arithmetic). Either $q$ is in the list $\{p_1, \dots, p_N\}$, or $q$ is a new prime.

Step 3 — Contradict

Case A: $q \in \{p_1, \dots, p_N\}$. Then $q \mid \prod p_i$. Also $q \mid M = \prod p_i + 1$. Subtracting, $q \mid 1$. But $q$ is prime, so $q \ge 2$ — impossible. Contradiction.

Case B: $q$ is a prime not in the list. Then $q > P$ (since the list contained every prime up to $P$). So $q$ is a prime larger than $P$ — contradicting "$P$ is the largest prime". Contradiction.

Step 4 — Conclude

Either case gives a contradiction. Hence no largest prime exists; the primes are infinite. ∎

Self-check:

Your "no largest prime" proof:

No largest prime exists. ∎

🔑 Why the construction works. Adding $1$ to the product guarantees $M$ shares no prime factor with the list (by the divisibility-of-difference argument). So any prime factor of $M$ must be new — giving Case B directly, without needing to split. Many textbooks phrase it as "$M$'s prime factors are all new", which is the cleanest form.

STEP 11 OF 23 · Phase 3 · Worked Example 3

WE 3 — If $p^2$ is even then $p$ is even (contrapositive)

⭐⭐⭐⭐ · P2-A3 · contrapositive

Prove that for any integer $p$, if $p^2$ is even then $p$ is even.

Read the structure

Goal is "$P \Rightarrow Q$" where $P$ = "$p^2$ is even" and $Q$ = "$p$ is even". The direct proof is awkward (we'd have to factor an unknown $p^2$). The contrapositive $\neg Q \Rightarrow \neg P$ becomes: "if $p$ is odd, then $p^2$ is odd" — and this is a one-line algebra exercise.

Switch to the contrapositive

Sentence: "We prove the contrapositive: if $p$ is odd, then $p^2$ is odd."

Direct proof of the contrapositive

Suppose $p$ is odd. Write $p = 2k + 1$ for some integer $k$. $p^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$. This is of the form $2m + 1$, so $p^2$ is odd. ✓

Conclude (contrapositive logic)

Since "$p$ odd $\Rightarrow$ $p^2$ odd" is the contrapositive of "$p^2$ even $\Rightarrow$ $p$ even", and the contrapositive is logically equivalent to the original, we have proved: if $p^2$ is even then $p$ is even. ∎

Self-check:

Your contrapositive proof:

If $p^2$ even, then $p$ even. ∎ (proved via contrapositive)

Same lemma works mod $p$ for any prime. The pattern "$p \mid n^2 \Rightarrow p \mid n$" holds for every prime $p$. Proof is identical: contrapositive — if $p \nmid n$ then $p \nmid n^2$ (since $\mathbb{F}_p$ is a field). This single lemma underpins every $\sqrt{p}$ irrationality proof.

STEP 12 OF 23 · Phase 3 · Worked Example 4

WE 4 — Among 3 consecutive integers, at least one is divisible by 3

⭐⭐⭐⭐ · P2-A1 + pigeonhole · contradiction OR direct

Prove that among any three consecutive integers, at least one is divisible by 3.

Read the structure

Two valid approaches. Path A (contradiction): assume none is divisible by 3, then derive a contradiction via mod 3. Path B (direct, pigeonhole): the three consecutive residues $n, n+1, n+2$ mod 3 are $\{0, 1, 2\}$ in some order — one of them is $0$.

Path A — Contradiction

Step 1 (Assume): Let $n, n+1, n+2$ be three consecutive integers. Suppose, for contradiction, that none of them is divisible by 3.

Step 2 (Derive): Then $n \not\equiv 0 \pmod 3$, $n+1 \not\equiv 0 \pmod 3$, $n+2 \not\equiv 0 \pmod 3$.

From $n \not\equiv 0$: $n \equiv 1$ or $n \equiv 2 \pmod 3$. If $n \equiv 1$: then $n + 2 \equiv 3 \equiv 0 \pmod 3$. Contradicts $n + 2 \not\equiv 0$. If $n \equiv 2$: then $n + 1 \equiv 3 \equiv 0 \pmod 3$. Contradicts $n + 1 \not\equiv 0$.

Step 3 (Contradict): In every case, the supposition forces one of the three to be $\equiv 0$, contradicting the supposition.

Step 4 (Conclude): Therefore at least one of $n, n+1, n+2$ is divisible by 3. ∎

Path B — Direct via pigeonhole

The residues $\{n \bmod 3, (n+1) \bmod 3, (n+2) \bmod 3\}$ are three consecutive residues mod 3. They cover all three residue classes $\{0, 1, 2\}$ in some order. Hence exactly one of them is $\equiv 0 \pmod 3$, i.e. divisible by 3. ∎

Self-check (try Path A):

Your contradiction proof (Path A):

At least one of $n, n+1, n+2$ is divisible by $3$. ∎

🔑 Pattern. "Among any $k$ consecutive integers, at least one is divisible by $k$" is the general fact. Proof: residues mod $k$ are $\{0, 1, \dots, k-1\}$, exhausted by $k$ consecutive integers. This kills many AIMO factor / divisibility setups.

STEP 13 OF 23 · Phase 3 · Worked Example 5

WE 5 — Prove $\sqrt{2} + \sqrt{3}$ is irrational

⭐⭐⭐⭐⭐ · P2-A1 + P2-A2 · combined

Prove that $\sqrt{2} + \sqrt{3}$ is irrational.

Read the structure

This is the queen of irrationality proofs. We assume $\sqrt{2} + \sqrt{3}$ is rational, square to extract $\sqrt{6}$, then derive that $\sqrt{6}$ is rational — contradicting a fact we'll prove (or cite from the $\sqrt{2}$/$\sqrt{3}$ template).

Step 1 — Assume

Suppose, for contradiction, that $\sqrt{2} + \sqrt{3} = r$ for some rational number $r$.

Step 2 — Derive (square it!)

$r^2 = (\sqrt{2} + \sqrt{3})^2 = 2 + 2\sqrt{6} + 3 = 5 + 2\sqrt{6}$. Rearrange: $2\sqrt{6} = r^2 - 5$. $\sqrt{6} = (r^2 - 5)/2$. Since $r$ is rational, $r^2$ is rational, so $r^2 - 5$ is rational, so $(r^2 - 5)/2$ is rational. Hence $\sqrt{6}$ is rational.

Sub-lemma: $\sqrt{6}$ is irrational

Suppose for contradiction $\sqrt{6} = p/q$ in lowest terms. Squaring: $6q^2 = p^2$. So $2 \mid p^2$, hence $2 \mid p$. Write $p = 2k$: $6q^2 = 4k^2$, so $3q^2 = 2k^2$. Then $2 \mid 3q^2$. Since $\gcd(2, 3) = 1$, $2 \mid q^2$, hence $2 \mid q$. So $2 \mid \gcd(p, q)$, contradicting lowest terms. Hence $\sqrt{6}$ is irrational.

Step 3 — Contradict

We derived "$\sqrt{6}$ is rational" from the supposition. But the sub-lemma says $\sqrt{6}$ is irrational. Contradiction.

Step 4 — Conclude

The supposition that $\sqrt{2} + \sqrt{3}$ is rational is false. Therefore $\sqrt{2} + \sqrt{3}$ is irrational. ∎

Self-check:

Your $\sqrt{2}+\sqrt{3}$ irrational proof:

$\sqrt{2} + \sqrt{3}$ is irrational. ∎

🔑 The squaring trick. Whenever you see a sum of square roots like $\sqrt{a} + \sqrt{b}$, squaring exposes the hidden $\sqrt{ab}$ term. The full argument then reduces to showing $\sqrt{ab}$ is irrational. This pattern generalises: $\sqrt{2} + \sqrt{3} + \sqrt{5}$ requires squaring twice, but the technique is the same.

STEP 14 OF 23 · Phase 4 · Practice (4 problems)

Four practice problems

Mix of P2-A1 (4-step framework), P2-A2 (classics), P2-A3 (contrapositive). 8–15 minutes each.

P1 · ⭐⭐⭐ · P2-A1 + P2-A2

Prove that $\sqrt{5}$ is irrational.

Mirror the $\sqrt{2}$ / $\sqrt{3}$ proofs. Key lemma: $5 \mid p^2 \Rightarrow 5 \mid p$ (proved via contrapositive — if $p \equiv 1, 2, 3, 4 \pmod 5$, then $p^2 \equiv 1, 4, 4, 1 \pmod 5$, none zero).

$\sqrt{5}$ is irrational. ∎

Suppose $\sqrt{5} = p/q$ in lowest terms. Squaring: $p^2 = 5q^2$. So $5 \mid p^2 \Rightarrow 5 \mid p$ (lemma above). Write $p = 5k$: $25k^2 = 5q^2 \Rightarrow q^2 = 5k^2 \Rightarrow 5 \mid q^2 \Rightarrow 5 \mid q$. So $5 \mid \gcd(p, q)$, contradicting lowest terms. Hence $\sqrt{5}$ is irrational. ∎

P2 · ⭐⭐⭐ · P2-A3 · contrapositive

Prove: if $n^2$ is divisible by 3, then $n$ is divisible by 3.

Prove the contrapositive: if $3 \nmid n$ then $3 \nmid n^2$. The two non-zero residues mod 3 give $n \equiv 1$ or $2$.

$3 \mid n^2 \Rightarrow 3 \mid n$. ∎

Contrapositive: assume $3 \nmid n$. Then $n \equiv 1$ or $n \equiv 2 \pmod 3$. Squaring: $n^2 \equiv 1$ or $n^2 \equiv 4 \equiv 1 \pmod 3$. In both cases $n^2 \equiv 1 \pmod 3$, i.e. $3 \nmid n^2$. By contrapositive, $3 \mid n^2 \Rightarrow 3 \mid n$. ∎

P3 · ⭐⭐⭐⭐ · P2-A1 + R3

Prove that there is no smallest positive rational number.

Suppose $r$ is the smallest. Construct a smaller positive rational, e.g. $r/2$.

No smallest positive rational exists. ∎

Suppose, for contradiction, that there exists a smallest positive rational number $r > 0$. Consider $r/2$. Since $r$ is rational and $1/2$ is rational, $r/2$ is rational. Since $r > 0$, $r/2 > 0$. And $r/2 < r$ (as $r > 0$). So $r/2$ is a positive rational smaller than $r$ — contradicting the choice of $r$ as smallest. Therefore no smallest positive rational exists. ∎

P4 · ⭐⭐⭐⭐ · P2-A1 + parity

Prove that the sum of a rational number and an irrational number is irrational.

Let $r$ be rational, $x$ irrational. Suppose $r + x = s$ is rational. Then $x = s - r$. What is $s - r$?

Sum is irrational. ∎

Let $r$ be a rational number and $x$ an irrational number. Suppose, for contradiction, that $r + x$ is rational; call it $s$. Then $x = s - r$. But the difference of two rationals is rational (closure of $\mathbb{Q}$ under subtraction). So $x$ is rational — contradicting the assumption that $x$ is irrational. Therefore $r + x$ is irrational. ∎

STEP 15 OF 23 · Phase 5 · AIMO Past Paper

AIMO 2018 Q9 — Even integers as sum of two odd composites

Pass 1 target: write the setup + verify several even integers $\le 38$ are NOT expressible (and several $> 38$ ARE) → bank 2–3 of 5 partial marks. Full proof needs the "add 6" or "add 10" induction trick — we will outline both.

AIMO 2018 · Q9 · 5 marks · ⭐⭐⭐⭐⭐

Prove that 38 is the largest even integer that is not the sum of two positive odd composite numbers.

Suggested time: 25–30 minutes. No calculator. Pass 1 target: 2–3 / 5.

Your proof (write here, scored by rubric)

Your written proof:

Rubric — keywords sought (max 5)

suppose, composite, odd, 38, 40, 42, 44, add 6, induction, therefore, contradict. Score = $\min(\text{distinct matches}, 5)$.

Why this question? Q9 is the gateway to Q10 marks. The problem structure has two halves: (a) verify 38 is exceptional — a finite enumeration, easy to write; (b) prove all larger evens work — needs an induction-style "add 6" or "add 10" argument. Even just nailing (a) and writing the setup of (b) earns 2–3 marks.

Hints & Strategy (open as needed)

Observe — 5-step modelling:

Keywords: "largest even integer", "NOT the sum", "two positive odd composite numbers".
Translation: (a) show $38$ has no representation $38 = c_1 + c_2$ with $c_1, c_2$ odd composite; (b) show every even $n \ge 40$ has such a representation.
Knowns: Odd composites $< 38$: $9, 15, 21, 25, 27, 33, 35$. Smallest odd composite is $9$.
Equation candidates: For (b), express $n$ as a known small even minus 6, then peel off $6$ as $9 + (-3)$ (no!) — use the additive trick: $n = 6 + (n - 6)$, where $n - 6$ has a known representation with one summand divisible by 3.
Sanity: $40 = 15 + 25$, $42 = 9 + 33$, $44 = 9 + 35$. Three base cases, then "add 6" propagates.

Strategy:

Half (a): List all odd composites less than 38: $\{9, 15, 21, 25, 27, 33, 35\}$. Enumerate all pairs whose sum is 38: $9+29$ (29 prime), $15+23$ (23 prime), $21+17$ (17 prime), $25+13$ (prime), $27+11$ (prime), $33+5$ (5 prime), $35+3$ (3 prime). None work. So 38 is NOT a sum.
Half (b) base cases: $40 = 15 + 25$, $42 = 9 + 33$, $44 = 9 + 35$. Each summand odd composite, and at least one summand is a multiple of $3$.
Half (b) inductive step: If $n \ge 40$ is even and $n = a + b$ with $a, b$ odd composite and (say) $a$ a multiple of 3, then $n + 6 = (a + 6) + b$. Now $a + 6$ is also an odd multiple of 3 with $a + 6 \ge 9 + 6 = 15$, so $a + 6$ is an odd composite. Hence $n + 6$ has the same property. By induction (with base cases $40, 42, 44$ covering all residues mod 6 among evens), every even $n \ge 40$ is expressible.
Combine: 38 fails; all $n \ge 40$ succeed. Hence 38 is the largest exception.

Partial-mark recipe (Pass 1 — guaranteed 2–3 marks):

Always write: "The odd composites less than 38 are: 9, 15, 21, 25, 27, 33, 35." (+1 mark)
Always write: "We check all pairs summing to 38: $9+29, 15+23, 21+17, 25+13, 27+11, 33+5, 35+3$. Each second summand (29, 23, 17, 13, 11, 5, 3) is prime, not composite. So 38 is NOT a sum of two odd composites." (+1 mark)
Always write: "We verify 40 = 15+25, 42 = 9+33, 44 = 9+35 (each summand odd composite, at least one a multiple of 3)." (+1 mark)
If time: "By 'adding 6 to a multiple of 3' we propagate to every even integer $\ge 40$." (+1 mark)
If time: Full inductive write-up with mod-6 case split. (+1 mark, full 5/5)

Final hint (the inductive step): The crux is: if $a$ is an odd multiple of 3 (so $a \in \{9, 15, 21, 27, 33, \dots\}$) and $a$ is composite, then $a + 6$ is also an odd composite multiple of 3. Reason: $a + 6$ is odd (odd + even), divisible by 3 (mult+mult), and $a + 6 \ge 15 > 3$, so $a + 6$ is composite. So once we have $40, 42, 44$ as base cases, adding 6 repeatedly covers every even integer $\ge 40$ (since $40, 42, 44$ exhaust the three even residues mod 6).

After your attempt:

Full Solution (5 / 5)

Half (a) — 38 is not expressible

The odd composites less than 38 are $\{9, 15, 21, 25, 27, 33, 35\}$. We check each pair $(c, 38 - c)$ where $c$ is in this set:

$9 + 29$ — but $29$ is prime. ✗ $15 + 23$ — $23$ is prime. ✗ $21 + 17$ — $17$ is prime. ✗ $25 + 13$ — $13$ is prime. ✗ $27 + 11$ — $11$ is prime. ✗ $33 + 5$ — $5$ is prime. ✗ $35 + 3$ — $3$ is prime. ✗

No two odd composites sum to 38.

Half (b) — every even integer $\ge 40$ is expressible

Base cases (each summand odd composite, at least one is a multiple of 3):

$40 = 15 + 25$. $42 = 9 + 33$. $44 = 9 + 35$.

Inductive step. Suppose $n \ge 40$ is even and $n = a + b$ where $a, b$ are odd composite and $a$ is a multiple of 3. Then $a + 6$ is also an odd composite multiple of 3 (odd + even = odd; mult of 3 + mult of 3 = mult of 3; $a + 6 \ge 15 > 3$ ensures composite). So $n + 6 = (a + 6) + b$ has the same property. By induction starting from base cases $40, 42, 44$ (which cover the three even residues mod 6, namely $40 \equiv 4$, $42 \equiv 0$, $44 \equiv 2 \pmod 6$), every even integer $\ge 40$ is expressible.

Combining

From (a), 38 is NOT expressible. From (b), every even integer $\ge 40$ IS expressible. Hence 38 is the largest even integer not expressible as the sum of two positive odd composite numbers. ∎

38 is the largest even integer not the sum of two positive odd composites. ∎

Source: AIMO 2018, Question 9 (5 marks). Official solution offers two equivalent approaches — adding 6 (multiples of 3) or adding 10 (multiples of 5).

STEP 16 OF 23 · Phase 5.5 · Synthesis

Synthesis — Pythagorean triples mod 4

A combined contradiction + mod-4 analysis. Shows how the 4-step framework lands cleanly on a number-theory parity question.

Synthesis · ⭐⭐⭐⭐⭐ · P2-A1 + mod 4 · 6 marks (internal)

Prove that if $a^2 + b^2 = c^2$ with $a, b, c$ positive integers, then at least one of $a, b$ is even.

Read the structure

Goal: "at least one of $a, b$ is even". Negation: "both $a$ and $b$ are odd". So we suppose both are odd and ride to a mod-4 contradiction.

Step 1 — Assume

Suppose, for contradiction, that both $a$ and $b$ are odd.

Step 2 — Derive (mod 4 analysis)

Lemma: if $n$ is odd, then $n^2 \equiv 1 \pmod 4$. Proof: $n = 2k+1 \Rightarrow n^2 = 4k^2 + 4k + 1 = 4k(k+1) + 1 \equiv 1 \pmod 4$. ✓ Apply to $a, b$: $a^2 \equiv 1 \pmod 4$ and $b^2 \equiv 1 \pmod 4$. So $a^2 + b^2 \equiv 1 + 1 = 2 \pmod 4$. Hence $c^2 \equiv 2 \pmod 4$.

Step 3 — Contradict

What residues can a square take mod 4? If $c$ is even, $c = 2m \Rightarrow c^2 = 4m^2 \equiv 0 \pmod 4$. If $c$ is odd, $c^2 \equiv 1 \pmod 4$ (lemma). So $c^2 \in \{0, 1\} \pmod 4$ — never $2$.

But we derived $c^2 \equiv 2 \pmod 4$. Contradiction.

Step 4 — Conclude

The assumption that both $a$ and $b$ are odd is false. Therefore at least one of $a, b$ is even. ∎

Self-check:

Your synthesis proof:

In any primitive (or general) Pythagorean triple $(a, b, c)$, at least one of $a, b$ is even. ∎

🔑 Stronger fact (preview). In a primitive Pythagorean triple, exactly one of $a, b$ is even, and $c$ is odd. The proof extends today's argument: we showed both $a, b$ odd is impossible. A symmetric argument shows both even contradicts primitivity.

STEP 17 OF 23 · Atomic Skills

Atomic skill matrix + 4 micro-validations

Three new skills today. Each row gives the trigger, the proof shape, and an estimated mastery time. Below: 4 micro-validations to confirm pattern recognition.

ID	Skill	Trigger	Proof shape	Time
`P2-A1`	4-step contradiction framework	Goal phrased "Prove that...", direct attack hard	Assume ¬Q → Derive → Contradict → Conclude	15 min
`P2-A2`	Classic templates ($\sqrt{2}$, primes, Euclid)	"Irrational", "infinitely many", "no largest"	Apply standard 4-step skeleton; recognise the family	20 min
`P2-A3`	Contrapositive transformation	$P \Rightarrow Q$ where $\neg Q$ is concrete and $\neg P$ is easy	Replace with $\neg Q \Rightarrow \neg P$; prove that directly	10 min

Micro-validations

For "Prove $\sqrt{7}$ is irrational", which atomic skill leads? (1=P2-A1, 2=P2-A2, 3=P2-A3)

For "Prove if $7 \mid n^2$ then $7 \mid n$", which skill? (1=P2-A1, 2=P2-A2, 3=P2-A3)

If we suppose $\sqrt{2} = p/q$ in lowest terms and derive $2 \mid p$ and $2 \mid q$, which contradiction route is this? (1=R1 int=frac, 2=R2 div, 3=R3 finite/inf, 4=R4 min/max)

In Euclid's primes proof, $M = p_1 \cdots p_N + 1$. What does $M$ have to be (for the argument to land)? Enter: 1 = prime, 2 = at least one prime factor, 3 = a product of two new primes.

STEP 18 OF 23 · Pattern Drill

Quick drill — pick the contradiction route

For each goal, decide which route (R1–R4) is the cleanest entry. Spend 30 seconds per row.

Goal	Route?	Reasoning
"Prove $\sqrt{7}$ is irrational"	R1	"Irrational" → assume $= p/q$, derive prime divides both
"Prove there are infinitely many primes of the form $4k+3$"	R3	"Infinitely many" → assume finitely many, build a new one (a Euclid-style construction with a clever sign)
"Prove no integer $n$ satisfies $n^2 \equiv 3 \pmod 4$"	R2	Suppose such $n$ exists; squares mod 4 are only $\{0, 1\}$, contradiction
"Prove $\log_2 3$ is irrational"	R1	Assume $\log_2 3 = p/q$; rewrite as $2^p = 3^q$; left side even, right side odd — contradiction
"Prove the equation $x^2 - 3y^2 = -1$ has no integer solutions"	R2	Mod 3 analysis: $x^2 \equiv -1 \equiv 2 \pmod 3$, but squares mod 3 are $\{0, 1\}$ — contradiction
"Prove if $a + b\sqrt{2} = 0$ with $a, b \in \mathbb{Q}$ then $a = b = 0$"	R1	Suppose $b \ne 0$; then $\sqrt{2} = -a/b$ is rational — contradicts $\sqrt{2}$ irrational

🔑 Speed target. Reading any olympiad proof prompt, you should be able to call the route within 10 seconds. The trigger words (irrational / infinitely / divides / smallest) do almost all the work.

STEP 19 OF 23 · 📋 Cheat Sheet

Part 2 cheat sheet — five cards to live in your head

F1 · The 4-step framework

Assume ¬Q → Derive → Contradict → Conclude

Open with "Suppose, for contradiction…", close with "Therefore Q. ∎". The middle is where the algebra lives.

Trap: forgetting the closing line costs marks even if the contradiction is correct.

F2 · The four contradiction routes

R1 int=frac · R2 p|a vs p∤a · R3 finite/inf · R4 min/max

R1 = irrationality. R2 = parity / divisibility / mod $n$. R3 = Euclid-style infinitude. R4 = descent (Pass 2).

F3 · Contrapositive law

$(P \Rightarrow Q) \Leftrightarrow (\neg Q \Rightarrow \neg P)$

Use when $\neg Q$ is concrete (e.g. "$n$ odd") and $\neg P$ is easy to derive directly. Strictly speaking a direct proof, but shares the "negate the conclusion" entry.

F4 · The lowest-terms lemma

$\sqrt{n} = p/q$ in lowest terms ⇒ derive $p_0 \mid \gcd(p, q)$ for some prime $p_0$

All R1 irrationality proofs end here. Choice of prime $p_0$ depends on $n$: $\sqrt{2}$ uses $p_0 = 2$, $\sqrt{3}$ uses $p_0 = 3$, $\sqrt{6}$ uses $p_0 = 2$, etc.

F5 · Squares mod 4 are $\{0, 1\}$

$n^2 \pmod 4 \in \{0, 1\}$ for all $n \in \mathbb{Z}$

Even $n$: $n^2 \equiv 0$. Odd $n$: $n^2 \equiv 1$. Used heavily in R2-style parity contradictions (e.g. Pythagorean triples — synthesis).

Bonus · Partial-mark recipe for Q9 proofs

setup (1) + base cases (1-2) + inductive sketch (1) ≈ 2-3 / 5

When stuck on a full proof: write the negation, list the small cases by hand, sketch the induction step. Even half-finished, this banks 2-3 partial marks.

STEP 20 OF 23 · ⭐ Self-Assessment

How confident are you on each atomic skill?

Click stars (1–5). Aim for ≥ 4 on every row before you move to Part 3.

P2-A1. 4-step contradiction framework — Assume ¬Q / Derive / Contradict / Conclude. Sentence templates F1–F4 from Step 6.

P2-A2. Classic contradiction templates — $\sqrt{2}$ / $\sqrt{3}$ / $\sqrt{n}$ irrational, Euclid's infinitude of primes. Recognise and replay the standard skeleton.

P2-A3. Contrapositive transformation — switch $P \Rightarrow Q$ to $\neg Q \Rightarrow \neg P$ when easier. Powers the "$p^2$ even ⇒ $p$ even" lemma family.

⭐ 0 / 15 — click stars

STEP 21 OF 23 · 📒 Error Book

Your Part-2 error book

Every micro-validation, worked-example or AIMO problem you got wrong is logged here. Re-attempt them at the end of the week.

Errors logged this session

No errors yet — submit some questions to populate this list.

Errors are saved in sessionStorage.aimoErrors_W11_P2. They persist across page reloads in the same tab, but clear when the tab closes. Copy them somewhere if you want a permanent record.

STEP 22 OF 23 · 🎉 Wrap-up

Part 2 complete — what you nailed today

What you nailed today

The 4-step framework: Assume ¬Q → Derive → Contradict → Conclude. Worth marks even when the algebra is incomplete.
The four standard contradiction routes: R1 int=frac, R2 divisibility clash, R3 finite vs infinite, R4 min/max (deferred).
Two foundational classics: $\sqrt{2}$ irrational (Step 7) and Euclid's infinitude of primes (Step 8).
The contrapositive law $(P \Rightarrow Q) \Leftrightarrow (\neg Q \Rightarrow \neg P)$ — and the $p^2$-even-$\Rightarrow$-$p$-even lemma family it powers.
Five worked examples covering ⭐⭐⭐ → ⭐⭐⭐⭐⭐: $\sqrt{3}$, no-largest-prime, $p^2$ even, three-consecutive divisibility, $\sqrt{2} + \sqrt{3}$.
AIMO 2018 Q9 — the partial-mark recipe to bank 2-3 / 5 even without a full induction.
Synthesis: in any Pythagorean triple, at least one of $a, b$ is even — combining contradiction with mod-4 analysis.

Bridge to Part 3 — Geometric Proof Writing. Today's contradiction template carries straight into geometry: many synthetic proofs phrase as "Suppose two lines meet at $P$; derive that they must be parallel; contradiction." Part 3 adds the geometric vocabulary (Given / To Prove / Proof / Conclusion 4-format), the synthetic-vs-algebraic decision, and auxiliary-line recognition. Combined with today's 4-step framework, you'll be ready for AIMO 2002 Q10 and 2008 Q9 as partial-mark targets.

🎯 Before you move on. Re-do the $\sqrt{2}$ proof (Step 7), Euclid's argument (Step 8), and the $\sqrt{2} + \sqrt{3}$ proof (Step 13) on paper without scaffolding. If you cannot reproduce the 4-step skeleton from memory in under 10 minutes each, replay those steps. The AIMO 2018 Q9 partial-mark target should be reproducible end-to-end (setup + base cases + inductive sketch) in 25 minutes.

STEP 23 OF 23 · 🏁 Final wrap

Part 2 — sealed in. Onwards to Part 3.

Atomic skills consolidated today (3)

P2-A1 — 4-step contradiction framework (15 min mastery).
P2-A2 — classic templates: $\sqrt{2}$, $\sqrt{3}$, Euclid's primes (20 min).
P2-A3 — contrapositive transformation (10 min).

Reminder — Pass 1 philosophy. You are NOT required to write a full 5/5 Q9 proof on your first encounter. Banking 2-3 partial marks via the setup-plus-base-cases recipe is a complete success at this stage. Pass 2 (W15) layers on strong induction, descent, and extremal-principle techniques to push toward 4-5 / 5.

Looking ahead. After Part 3 (Geometric Proof) and Part 4 (Q9 Partial-Mark Strategy), the Sunday Mock (8 proof problems, 3 hours) and Past Paper Test will exercise the entire W11 toolkit on real AIMO Q4–Q10 problems.