Figure 1.2: Logical Anatomy of Reductio ad Absurdum (Proof by Contradiction)

Goal Statement Prove Proposition P Step 1: Assumption Assume Negation ¬P Step 2: Strict Deductions Algebraic Consequences Step 3: Contradiction (⊥) Violates Coprimality / Parity / Q ∧ ¬Q Step 4: Conclusion ¬P False ⇒ P True [R1]

By the Law of Excluded Middle, a statement $P$ is either true or false. Showing that assuming $\neg P$ leads inexorably to an impossibility proves that $\neg P$ is false, establishing $P$ as necessarily true.

AHL 1.15

The Logical Mechanics of Reductio ad Absurdum

  • Core Logical Axiom: In classical mathematics, the Law of Excluded Middle guarantees that for any proposition $P$, exactly one of $P$ or $\neg P$ is true. If assuming $\neg P$ leads to a contradiction ($C \land \neg C$), then $\neg P$ is impossible; hence $P$ is true.
  • Crucial Distinction: Contradiction vs. Contrapositive:
    • Contrapositive: Proves the implication $P \implies Q$ directly by proving its logical equivalent: $\neg Q \implies \neg P$. It begins only with $\neg Q$ and concludes with $\neg P$.
    • Contradiction: Proves $P \implies Q$ by assuming both $P$ AND $\neg Q$ simultaneously, deriving an impossibility from their combined coexistence.
  • Precise Negation Formulations (The IB Markscheme Test):
    • Rationality: To prove $x$ is irrational, the assumption MUST state: "Assume $x$ is rational, so $x = \frac{p}{q}$ where $p, q \in \mathbb{Z}, q \neq 0$, and $\gcd(p, q) = 1$ (coprime / in lowest terms)." Omitting the coprime condition $\gcd(p, q) = 1$ forfeits the method mark `[M1]`!
    • Quantifiers: The negation of $\forall x \in S, P(x)$ is $\exists x \in S \text{ such that } \neg P(x)$. The negation of $\exists x \in S, P(x)$ is $\forall x \in S, \neg P(x)$.
    • Inequalities: The negation of $A > B$ is $A \le B$ (never forget the equality condition!).
AHL 1.15

Classical Irrationality: Radicals & Logarithms

  • The Prime Divisor Lemma (Euclid's Lemma): For any prime $p$ and integer $a$: $$p \mid a^2 \implies p \mid a$$ Proof Lemma: If $a$ were not divisible by $p$, in prime factorization $a = q_1 q_2 \cdots q_k$ where $q_i \neq p$. Then $a^2 = q_1^2 \cdots q_k^2$, which does not contain $p$ by uniqueness of prime factorization, contradicting $p \mid a^2$.
  • General Radical Proof Protocol ($\sqrt{p}$ is irrational for prime $p$):
    1. Assume $\sqrt{p} = \frac{a}{b}$ with $a, b \in \mathbb{Z}^+, \gcd(a, b) = 1$.
    2. Square both sides: $p b^2 = a^2 \implies p \mid a^2 \implies p \mid a \implies a = p k$ for $k \in \mathbb{Z}^+$.
    3. Substitute back: $p b^2 = (pk)^2 = p^2 k^2 \implies b^2 = p k^2 \implies p \mid b^2 \implies p \mid b$.
    4. Both $a$ and $b$ share a common factor $p > 1$, which directly contradicts $\gcd(a, b) = 1$.
    5. Therefore, the initial assumption is false, and $\sqrt{p}$ is irrational.
  • Logarithmic Irrationality via the Fundamental Theorem of Arithmetic: To prove $\log_2(3)$ is irrational: Assume $\log_2(3) = \frac{p}{q}$ for $p, q \in \mathbb{Z}^+$. Then $2^{p/q} = 3 \implies 2^p = 3^q$. The LHS is always even ($2 \mid 2^p$), while the RHS is always odd ($2 \nmid 3^q$), or by uniqueness of prime factorizations $2^p = 3^q$ has no positive integer solutions. Contradiction! Hence $\log_2(3)$ is irrational.
AHL 1.15

Infinitude of Primes & Diophantine Parity Proofs

  • Euclid's Infinitude of Primes: Assume there exists a finite number of primes, enumerated as $\mathcal{P} = \{p_1, p_2, \dots, p_N\}$. Construct Euclid's number: $$M = (p_1 \cdot p_2 \cdots p_N) + 1$$ Since $M > 1$, by the Fundamental Theorem of Arithmetic $M$ must possess at least one prime divisor $q$.
    • If $q \in \mathcal{P}$, then $q \mid (p_1 \cdots p_N)$ and $q \mid M$.
    • Therefore, $q$ must divide the difference: $q \mid (M - p_1 \cdots p_N) \implies q \mid 1$.
    • Since no prime divides $1$, this is an absolute contradiction!
    • Thus, $q \notin \mathcal{P}$, proving the set of primes cannot be finite.
    Critical Examiner Note: Never write "$M$ must be prime"! $M$ can be composite (e.g., $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \times 509$). The proof only requires that $M$ has a prime factor not on the finite list.
  • Diophantine Impossibility via Modulo / Parity: Equations like $x^2 - 4y = 2$ or $a^2 + b^2 = 3c^2$: Analyze both sides modulo an appropriate modulus $m \in \{2, 3, 4, 8\}$: Quadratic residues modulo 4: $x^2 \equiv 0 \text{ or } 1 \pmod 4$. In $x^2 - 4y = 2$, LHS $\equiv x^2 \equiv 0 \text{ or } 1 \pmod 4$, while RHS $\equiv 2 \pmod 4$. Since $0 \neq 2$ and $1 \neq 2$, no integer solutions can exist.

Authentic IB HL Worked Exemplars (Full Markscheme Rubrics)

Exemplar 1 · Paper 1 (6 Marks)

Proving $\sqrt{5}$ is Irrational

Prove by contradiction that $\sqrt{5}$ is an irrational number.

Full Markscheme & Method:

  1. Step 1: State the Logical Negation Assumption Assume that $\sqrt{5}$ is a rational number. Then $\sqrt{5} = \frac{a}{b}$, where $a, b \in \mathbb{Z}^+$, $b \neq 0$, and $\gcd(a, b) = 1$ (the fraction is in simplest form with no common factors). $\mathbf{[M1][A1]}$
  2. Step 2: Algebraic Manipulation & Divisibility of $a$ Squaring both sides: $$5 = \frac{a^2}{b^2} \implies a^2 = 5b^2 \quad \mathbf{[M1]}$$ Since $b^2$ is an integer, $5 \mid a^2$. Since $5$ is a prime number, $5 \mid a^2 \implies 5 \mid a$. $\mathbf{[A1]}$ Therefore, we can write $a = 5k$ for some integer $k \in \mathbb{Z}^+$.
  3. Step 3: Divisibility of $b$ & The Contradiction Substitute $a = 5k$ back into the equation: $$(5k)^2 = 5b^2 \implies 25k^2 = 5b^2 \implies b^2 = 5k^2 \quad \mathbf{[M1]}$$ This implies that $5 \mid b^2$, and since $5$ is prime, $5 \mid b$. $\mathbf{[A1]}$
  4. Step 4: Formal Contradiction & Conclusion Both $a$ and $b$ are divisible by $5$, which means $\gcd(a, b) \ge 5$. This directly contradicts the initial assumption that $\gcd(a, b) = 1$. Therefore, the initial assumption is false, and $\sqrt{5}$ is irrational. $\mathbf{[R1]}$
Examiner Advice: If you omit the premise that $a$ and $b$ are coprime ($\gcd(a, b) = 1$), you cannot claim a contradiction when showing both are multiples of 5! That single phrase secures the foundational `[A1]` mark.
Exemplar 2 · Paper 1 (6 Marks)

Proving $\log_2(3)$ is Irrational

Prove by contradiction that $\log_2(3)$ is an irrational number.

Full Markscheme & Method:

  1. Step 1: Assume the Negation Assume that $\log_2(3)$ is a rational number. Since $3 > 1$ and $2 > 1$, $\log_2(3) > 0$. Therefore, $\log_2(3) = \frac{p}{q}$ for some positive integers $p, q \in \mathbb{Z}^+$. $\mathbf{[M1][A1]}$
  2. Step 2: Convert to Exponential Form By the definition of logarithms: $$2^{\frac{p}{q}} = 3 \quad \mathbf{[M1]}$$ Raise both sides to the power $q$: $$(2^{\frac{p}{q}})^q = 3^q \implies 2^p = 3^q \quad \mathbf{[A1]}$$
  3. Step 3: Establish the Arithmetic Contradiction Since $p \ge 1$, $2^p$ is a positive power of 2, so $2^p$ is an even integer (divisible by 2). $\mathbf{[M1]}$ Since $q \ge 1$, $3^q$ is a product of odd numbers, so $3^q$ is an odd integer (not divisible by 2). Alternatively, by the Fundamental Theorem of Arithmetic (uniqueness of prime factorizations), the prime factorization of the LHS contains only the prime 2, whereas the RHS contains only the prime 3. An even number cannot equal an odd number ($2^p \neq 3^q$). $\mathbf{[R1]}$
  4. Step 4: Conclusion This is a contradiction. Hence our assumption that $\log_2(3)$ is rational is false, and $\log_2(3)$ is irrational. $\mathbf{[R1]}$
Exemplar 3 · Paper 1 (6 Marks)

Linear Combination of Rational and Irrational

Given that $\sqrt{2}$ is irrational, prove by contradiction that for any rational numbers $a, b \in \mathbb{Q}$ with $b \neq 0$, the number $a + b\sqrt{2}$ is irrational.

Full Markscheme & Method:

  1. Step 1: Assumption Assume that $a + b\sqrt{2}$ is a rational number. Then $a + b\sqrt{2} = r$, where $r \in \mathbb{Q}$. $\mathbf{[M1][A1]}$
  2. Step 2: Algebraic Rearrangement for $\sqrt{2}$ Subtract $a$ from both sides: $$b\sqrt{2} = r - a \quad \mathbf{[M1]}$$ Since $b \neq 0$, divide both sides by $b$: $$\sqrt{2} = \frac{r - a}{b} \quad \mathbf{[A1]}$$
  3. Step 3: Deduce Closure Impossibility Since $r \in \mathbb{Q}$ and $a \in \mathbb{Q}$, the difference $r - a \in \mathbb{Q}$ by closure of rational numbers under subtraction. Since $b \in \mathbb{Q}$ with $b \neq 0$, the quotient $\frac{r - a}{b} \in \mathbb{Q}$ by closure of rational numbers under division. $\mathbf{[M1]}$ This implies that $\sqrt{2} \in \mathbb{Q}$ (that $\sqrt{2}$ is rational).
  4. Step 4: Contradiction & Conclusion This contradicts the given fact that $\sqrt{2}$ is irrational. Therefore, the assumption that $a + b\sqrt{2}$ is rational is false, and $a + b\sqrt{2}$ must be irrational. $\mathbf{[R1]}$
Exemplar 4 · Paper 2 (7 Marks)

Diophantine Parity Impossibility: $x^2 - 4y = 2$

Prove by contradiction that the equation $x^2 - 4y = 2$ has no integer solutions for $x, y \in \mathbb{Z}$.

Full Markscheme & Method:

  1. Step 1: Assume an Integer Solution Exists Assume there exist integers $x, y \in \mathbb{Z}$ satisfying $x^2 - 4y = 2$. $\mathbf{[M1]}$
  2. Step 2: Deduce Parity of $x$ Rearrange the equation: $$x^2 = 4y + 2 = 2(2y + 1) \quad \mathbf{[A1]}$$ Since $2y+1 \in \mathbb{Z}$, $x^2$ is divisible by 2, so $x^2$ is an even integer. If $x$ were odd, $x = 2k+1 \implies x^2 = 4k^2 + 4k + 1 = 2(2k^2+2k) + 1$, which is odd. Therefore, $x$ must be even, so $x = 2k$ for some integer $k \in \mathbb{Z}$. $\mathbf{[M1][A1]}$
  3. Step 3: Substitute and Examine Modulo 4 Substitute $x = 2k$ into the equation: $$(2k)^2 - 4y = 2 \implies 4k^2 - 4y = 2 \quad \mathbf{[M1]}$$ Divide both sides by 2: $$2k^2 - 2y = 1 \implies 2(k^2 - y) = 1 \quad \mathbf{[A1]}$$
  4. Step 4: Establish the Contradiction Since $k, y \in \mathbb{Z}$, $k^2 - y$ is an integer. The LHS $2(k^2 - y)$ is an even integer, but the RHS is $1$, which is an odd integer. An even integer cannot equal an odd integer ($2(k^2 - y) \neq 1$). $\mathbf{[R1]}$ This is a contradiction. Hence, no integer solutions $(x, y)$ can exist.
Exemplar 5 · Paper 1 (8 Marks)

Euclid's Infinitude of Primes

Prove by contradiction that there are infinitely many prime numbers.

Full Markscheme & Method:

  1. Step 1: Assume the Negation (Finite List) Assume that there are only finitely many prime numbers. Then all prime numbers can be listed in ascending order as: $$\mathcal{P} = \{p_1, p_2, p_3, \dots, p_N\} \quad \mathbf{[M1][A1]}$$ where $p_N$ is the largest existing prime number.
  2. Step 2: Construct Euclid's Integer $M$ Consider the integer formed by multiplying all listed primes and adding 1: $$M = (p_1 \cdot p_2 \cdot p_3 \cdots p_N) + 1 \quad \mathbf{[M1]}$$ Since $p_1 = 2$, $M \ge 2 + 1 = 3 > 1$.
  3. Step 3: Prime Factor Deduction By the Fundamental Theorem of Arithmetic, every integer strictly greater than 1 has at least one prime divisor. Let $q$ be a prime divisor of $M$. $\mathbf{[M1]}$ Since $\mathcal{P}$ contains all existing primes, $q$ must be one of the primes in the list $\mathcal{P}$: $$q = p_k \quad \text{for some } k \in \{1, 2, \dots, N\} \quad \mathbf{[A1]}$$
  4. Step 4: Derive the Divisibility Contradiction Since $q = p_k$, $q$ divides the product: $q \mid (p_1 \cdot p_2 \cdots p_N)$. $\mathbf{[M1]}$ By definition of $q$, $q$ also divides $M$. Therefore, $q$ must divide their difference: $$q \mid [M - (p_1 \cdot p_2 \cdots p_N)] \implies q \mid 1 \quad \mathbf{[A1]}$$ However, every prime number $q \ge 2$, so no prime can divide 1.
  5. Step 5: Conclusion This is a contradiction. Hence the initial assumption that there are finitely many primes is false, and there must be infinitely many prime numbers. $\mathbf{[R1]}$
Tier 1: Core Parity & Rationality Foundations (Questions 1–4)
Exercise 1 Paper 1 · 4 Marks

Prove that the square of an odd integer is always odd, and deduce that if $n^2$ is even, $n$ must be even.

View Complete Solution & Markscheme
  1. Let $n$ be an odd integer, so $n = 2k + 1$ for some integer $k \in \mathbb{Z} \quad \mathbf{[M1]}$.
  2. Square the expression: $$n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1 \quad \mathbf{[A1]}$$ Since $k \in \mathbb{Z}$, $2k^2 + 2k$ is an integer, so $n^2$ is in the form $2M + 1$, which is odd $\mathbf{[A1]}$.
  3. Deduction by Contrapositive / Contradiction: Assume $n^2$ is even, but $n$ is odd. By the lemma just proven, if $n$ is odd, then $n^2$ must be odd. This contradicts that $n^2$ is even. Hence, $n$ must be even $\mathbf{[R1]}$.

Final Conclusion: Proven directly and contrapositively.

Exercise 2 Paper 1 · 5 Marks

Prove by contradiction that $\sqrt{3}$ is an irrational number, given that for any integer $n$, $3 \mid n^2 \implies 3 \mid n$.

View Complete Solution & Markscheme
  1. Assume $\sqrt{3}$ is rational: $\sqrt{3} = \frac{a}{b}$ where $a, b \in \mathbb{Z}^+, \gcd(a, b) = 1 \quad \mathbf{[M1]}$.
  2. Square both sides: $3b^2 = a^2 \implies 3 \mid a^2 \implies 3 \mid a \quad \mathbf{[A1]}$. So $a = 3k$ for some $k \in \mathbb{Z}$.
  3. Substitute back: $3b^2 = (3k)^2 = 9k^2 \implies b^2 = 3k^2 \implies 3 \mid b^2 \implies 3 \mid b \quad \mathbf{[M1][A1]}$.
  4. Both $a$ and $b$ are divisible by 3, contradicting $\gcd(a, b) = 1$. Hence $\sqrt{3}$ is irrational $\mathbf{[R1]}$.

Final Conclusion: $\sqrt{3}$ is irrational.

Exercise 3 Paper 1 · 4 Marks

Prove by contradiction that there are no integers $x, y \in \mathbb{Z}$ satisfying $2x + 4y = 7$.

View Complete Solution & Markscheme
  1. Assume there exist integers $x, y \in \mathbb{Z}$ such that $2x + 4y = 7 \quad \mathbf{[M1]}$.
  2. Factor out 2 from the left-hand side: $$2(x + 2y) = 7 \quad \mathbf{[A1]}$$
  3. Since $x, y \in \mathbb{Z}$, $x + 2y$ is an integer. Thus the LHS is an even integer $\mathbf{[M1]}$.
  4. The RHS is 7, which is an odd integer. An even integer cannot equal an odd integer, yielding an arithmetic contradiction. Hence no integer solution exists $\mathbf{[R1]}$.

Final Conclusion: No integer solution exists.

Exercise 4 Paper 1 · 5 Marks

Prove by contradiction that the sum of any rational number and any irrational number is irrational.

View Complete Solution & Markscheme
  1. Let $q \in \mathbb{Q}$ be rational and $x \notin \mathbb{Q}$ be irrational. Assume their sum $S = q + x$ is rational: $S \in \mathbb{Q} \quad \mathbf{[M1]}$.
  2. Rearrange for the irrational number: $$x = S - q \quad \mathbf{[A1]}$$
  3. Since $S \in \mathbb{Q}$ and $q \in \mathbb{Q}$, by the closure of rational numbers under subtraction, $S - q \in \mathbb{Q} \quad \mathbf{[M1][A1]}$.
  4. This implies that $x \in \mathbb{Q}$, directly contradicting the premise that $x$ is irrational. Therefore, $q + x$ must be irrational $\mathbf{[R1]}$.

Final Conclusion: Sum is irrational.

Tier 2: Logarithms, Diophantine & Prime Multiples (Questions 5–8)
Exercise 5 Paper 1 · 6 Marks

Prove by contradiction that $\log_{10}(5)$ is irrational.

View Complete Solution & Markscheme
  1. Assume $\log_{10}(5)$ is rational. Since $1 < 5 < 10$, $0 < \log_{10}(5) < 1$. Write $\log_{10}(5) = \frac{p}{q}$ where $p, q \in \mathbb{Z}^+$ and $p < q \quad \mathbf{[M1][A1]}$.
  2. Convert to exponential form: $$10^{\frac{p}{q}} = 5 \implies 10^p = 5^q \quad \mathbf{[M1]}$$
  3. Express 10 as $2 \times 5$: $$(2 \times 5)^p = 5^q \implies 2^p \times 5^p = 5^q \implies 2^p = 5^{q-p} \quad \mathbf{[A1]}$$
  4. Since $p \ge 1$, $2^p$ is an even number divisible by 2. Since $q > p$, $q - p \ge 1$, so $5^{q-p}$ is an odd number divisible by 5. By unique prime factorization, $2^p = 5^{q-p}$ has no integer solution $\mathbf{[R1]}$.
  5. This contradiction proves that $\log_{10}(5)$ is irrational $\mathbf{[R1]}$.

Final Conclusion: $\log_{10}(5)$ is irrational.

Exercise 6 Paper 1 · 6 Marks

Prove by contradiction that there are no integers $x, y \in \mathbb{Z}$ such that $x^2 - y^2 = 2$.

View Complete Solution & Markscheme
  1. Assume there exist integers $x, y \in \mathbb{Z}$ satisfying $x^2 - y^2 = 2 \quad \mathbf{[M1]}$.
  2. Factor the difference of squares: $$(x - y)(x + y) = 2 \quad \mathbf{[A1]}$$
  3. Notice that $(x + y) - (x - y) = 2y$, which is always an even integer. This means $(x + y)$ and $(x - y)$ must have the same parity (both even or both odd) $\mathbf{[M1][R1]}$.
  4. However, to multiply to 2, the integer factors must be $(\pm 1, \pm 2)$ or $(\pm 2, \pm 1)$. In every pair, one factor is odd and the other is even (different parity) $\mathbf{[A1]}$.
  5. This contradiction shows $(x - y)(x + y)$ can never equal 2 for integers. Hence no integer solution exists $\mathbf{[R1]}$.

Final Conclusion: No integer solution exists.

Exercise 7 Paper 1 · 5 Marks

Prove by contradiction that there is no smallest positive rational number.

View Complete Solution & Markscheme
  1. Assume there exists a smallest positive rational number, denoted by $q \in \mathbb{Q}^+ \quad \mathbf{[M1]}$.
  2. Consider the number $r = \frac{q}{2} \quad \mathbf{[A1]}$.
  3. Since $q > 0$, $r = \frac{q}{2} > 0$. Since $q \in \mathbb{Q}$, $r = \frac{q}{2} \in \mathbb{Q}$ by closure of rationals under division $\mathbf{[M1]}$.
  4. Furthermore, since $q > 0$, $\frac{q}{2} < q$, so $r < q \quad \mathbf{[A1]}$.
  5. Thus $r$ is a positive rational number strictly smaller than $q$, directly contradicting that $q$ is the smallest positive rational. Hence, no smallest positive rational exists $\mathbf{[R1]}$.

Final Conclusion: Proven by contradiction.

Exercise 8 Paper 1 · 6 Marks

Prove by contradiction that if $n$ is an integer and $n^2$ is divisible by 5, then $n$ is divisible by 5.

View Complete Solution & Markscheme
  1. Assume $n^2$ is divisible by 5, but $n$ is NOT divisible by 5 $\mathbf{[M1]}$.
  2. Since $n$ is not divisible by 5, by the Division Algorithm $n$ must take one of the forms: $$n = 5k + 1, \quad 5k + 2, \quad 5k + 3, \quad \text{or} \quad 5k + 4 \quad (k \in \mathbb{Z}) \quad \mathbf{[M1]}$$
  3. Compute $n^2$ modulo 5 for each case:
    • $n = 5k \pm 1 \implies n^2 = 25k^2 \pm 10k + 1 = 5(5k^2 \pm 2k) + 1 \equiv 1 \pmod 5$ $\mathbf{[A1]}$
    • $n = 5k \pm 2 \implies n^2 = 25k^2 \pm 20k + 4 = 5(5k^2 \pm 4k) + 4 \equiv 4 \pmod 5$ $\mathbf{[A1]}$
  4. In all cases, the remainder when $n^2$ is divided by 5 is either 1 or 4. Therefore, $n^2$ is never divisible by 5 when $n$ is not divisible by 5 $\mathbf{[R1]}$.
  5. This contradicts the premise that $n^2$ is divisible by 5. Hence, $n$ must be divisible by 5 $\mathbf{[R1]}$.

Final Conclusion: $5 \mid n^2 \implies 5 \mid n$.

Tier 3: Paper 3 Style Extended Deductions (Questions 9–10)
Exercise 9 Paper 3 Extended Deduction · 8 Marks

(a) Show that the product of any two integers of the form $4k + 1$ is also of the form $4k + 1$. [2 marks]
(b) Hence prove by contradiction that there are infinitely many primes of the form $4k - 1$ (or $4k + 3$). [6 marks]

View Complete Solution & Markscheme
  1. Part (a): Let $u = 4a + 1$ and $v = 4b + 1$ for $a, b \in \mathbb{Z}$. $$uv = (4a + 1)(4b + 1) = 16ab + 4a + 4b + 1 = 4(4ab + a + b) + 1 \quad \mathbf{[M1]}$$ Since $4ab + a + b \in \mathbb{Z}$, $uv$ is of the form $4k + 1 \quad \mathbf{[A1]}$.
  2. Part (b): Assume there are only finitely many primes of the form $4k - 1$: $$\{q_1, q_2, \dots, q_m\} \quad \text{where } q_1 = 3, q_2 = 7, \dots \quad \mathbf{[M1]}$$
  3. Construct $N = 4(q_1 q_2 \cdots q_m) - 1 \quad \mathbf{[M1]}$. Notice that $N$ is an integer of the form $4k - 1$, and $N > q_m$.
  4. All odd primes are either of the form $4k + 1$ or $4k - 1$. If all prime factors of $N$ were of the form $4k + 1$, by part (a) their product $N$ would be of the form $4k + 1$. However, $N$ is of the form $4k - 1$. Therefore, $N$ must have at least one prime factor $p$ of the form $4k - 1 \quad \mathbf{[R1]}$.
  5. Since $p$ is of the form $4k - 1$, $p$ must be in the finite list: $p = q_i$ for some $i$. Then $p \mid (4q_1 \cdots q_m)$ and $p \mid N$. Thus $p \mid [4(q_1 \cdots q_m) - N] \implies p \mid 1 \quad \mathbf{[A1]}$.
  6. No prime divides 1. Contradiction! Therefore, there are infinitely many primes of the form $4k - 1 \quad \mathbf{[R1]}$.

Final Conclusion: Infinitude proven.

Exercise 10 Paper 1 / Paper 3 · 7 Marks

Prove by contradiction that $\sqrt{2} + \sqrt{3}$ is an irrational number.

View Complete Solution & Markscheme
  1. Assume that $\sqrt{2} + \sqrt{3}$ is rational, so $\sqrt{2} + \sqrt{3} = x \in \mathbb{Q} \quad \mathbf{[M1]}$. Since $\sqrt{2} > 0$ and $\sqrt{3} > 0$, $x > 0$.
  2. Isolate one radical and square: $$x - \sqrt{2} = \sqrt{3} \implies (x - \sqrt{2})^2 = 3 \quad \mathbf{[M1]}$$ $$x^2 - 2x\sqrt{2} + 2 = 3 \implies x^2 - 1 = 2x\sqrt{2} \quad \mathbf{[A1]}$$
  3. Since $x > 0$, divide by $2x$: $$\sqrt{2} = \frac{x^2 - 1}{2x} \quad \mathbf{[M1][A1]}$$
  4. Since $x \in \mathbb{Q}$, by closure of the field $\mathbb{Q}$ under multiplication, addition, and division (with $2x \neq 0$), the quantity $\frac{x^2 - 1}{2x} \in \mathbb{Q} \quad \mathbf{[R1]}$.
  5. This implies that $\sqrt{2}$ is rational, which directly contradicts the established theorem that $\sqrt{2}$ is irrational $\mathbf{[R1]}$. Hence, the assumption is false, and $\sqrt{2} + \sqrt{3}$ is irrational.

Final Conclusion: $\sqrt{2} + \sqrt{3}$ is irrational.

Syllabus AHL 1.15

Logical Equivalences & Negations

  • Implication Negation: $$\neg(P \implies Q) \iff P \land \neg Q$$
  • Contrapositive Equivalence: $$(P \implies Q) \iff (\neg Q \implies \neg P)$$
  • De Morgan's Laws: $$\neg(A \land B) \iff \neg A \lor \neg B, \qquad \neg(A \lor B) \iff \neg A \land \neg B$$
  • Quantifier Negations: $$\neg(\forall x \in S, P(x)) \iff \exists x \in S, \neg P(x)$$ $$\neg(\exists x \in S, P(x)) \iff \forall x \in S, \neg P(x)$$
Must Memorize

Standard Definitions & Lemmas

  • Rational Definition: $x \in \mathbb{Q} \iff x = \frac{p}{q}$ with $p, q \in \mathbb{Z}, q \neq 0$, and $\gcd(p, q) = 1$.
  • Euclid's Prime Lemma: For prime $p$, $p \mid ab \implies p \mid a \lor p \mid b$. In particular, $p \mid a^2 \implies p \mid a$.
  • Euclid's Construction: $M = \prod_{i=1}^N p_i + 1$ has a prime divisor not in the finite list.

Critical IB Examination Pitfalls in Contradiction Proofs

  • Forgetting Coprimality in Rationality Proofs: Writing $x = \frac{a}{b}$ without stating $\gcd(a, b) = 1$ makes the final step ("$a$ and $b$ are both multiples of $p$") inconclusive rather than contradictory.
  • Asserting Euclid's Number $M$ is Prime: Writing "$M = p_1 \cdots p_N + 1$ is prime" is mathematically false and forfeits accuracy marks. You must state: "$M > 1$, so it has a prime divisor $q$".
  • Confusing Contradiction with Contrapositive: Contradiction assumes the negation of the entire statement. Contrapositive directly proves $\neg Q \implies \neg P$.
  • Incomplete Negation of Inequalities: The negation of $A > B$ is $A \le B$, NOT $A < B$. Omitting the equality case invalidates your proof.

Section A: Diagnostic Check

4 core concept check questions. Immediate feedback and scoring.

Score: 0 / 4

Question 1

What is the very first step in a proof by contradiction?

Correct! In Reductio ad Absurdum, you assume the negation $\neg P$ and demonstrate that this leads to an impossibility.

Question 2

Why must a proof of the irrationality of $\sqrt{3}$ specify that $\sqrt{3} = \frac{a}{b}$ is in lowest terms ($\gcd(a, b) = 1$)?

Correct! Without $\gcd(a, b) = 1$, finding a common factor of 3 is perfectly normal and does not produce a contradiction.

Question 3

In Euclid's proof of the infinitude of primes, what property of $M = (p_1 p_2 \cdots p_N) + 1$ produces the contradiction?

Correct! Since $M$ leaves remainder 1 when divided by any prime on the list, any prime factor of $M$ must be outside the list.

Question 4

What is the exact logical negation of the inequality statement: "For all $x > 0$, $f(x) > 5$"?

Correct! Negating $\forall x \in S, P(x)$ yields $\exists x \in S, \neg P(x)$, and the negation of $f(x) > 5$ is $f(x) \le 5$.

Section B: Examination-Style Free Response Questions

Question 5 (Paper 1 Style · 6 marks)

Prove by contradiction that the equation $a^2 - 8b = 7$ has no integer solutions for $a, b \in \mathbb{Z}$.

Show Full Markscheme

Step 1: Assumption [1 mark]
Assume there exist integers $a, b \in \mathbb{Z}$ such that $a^2 - 8b = 7$. [M1]

Step 2: Modulo 8 Analysis [2 marks]
Rearrange: $a^2 = 8b + 7 \equiv 7 \pmod 8$. [M1]
Since $a^2$ is odd, $a$ must be odd, so write $a = 2k + 1$ (or $4k \pm 1, 4k \pm 3$) for $k \in \mathbb{Z}$. [A1]

Step 3: Square of an Odd Number Modulo 8 [2 marks]
$a^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 4k(k + 1) + 1$. [M1]
Since $k(k+1)$ is the product of two consecutive integers, it is always even, so $k(k+1) = 2m$.
Thus $a^2 = 4(2m) + 1 = 8m + 1 \equiv 1 \pmod 8$. [A1]

Step 4: Contradiction & Conclusion [1 mark]
The LHS $a^2 \equiv 1 \pmod 8$, while the RHS is $8b + 7 \equiv 7 \pmod 8$.
Since $1 \neq 7 \pmod 8$, this is a contradiction. Hence no integer solutions exist. [R1]

Question 6 (Paper 1 Style · 7 marks)

Prove by contradiction that $\log_3(2)$ is irrational.

Show Full Markscheme

Step 1: Assumption [2 marks]
Assume $\log_3(2)$ is rational. Since $1 < 2 < 3$, $0 < \log_3(2) < 1$.
Therefore $\log_3(2) = \frac{p}{q}$ for positive integers $p, q \in \mathbb{Z}^+$. [M1][A1]

Step 2: Exponential Form [2 marks]
By definition of logarithm: $3^{p/q} = 2$. [M1]
Raising both sides to the power $q$: $3^p = 2^q$. [A1]

Step 3: Parity / Unique Prime Factorization [2 marks]
Since $p \ge 1$, $3^p$ is a product of odd numbers, so $3^p$ is odd. [M1]
Since $q \ge 1$, $2^q$ is a positive power of 2, so $2^q$ is even.
Alternatively, by the Fundamental Theorem of Arithmetic, the prime factorization of $3^p$ contains only 3, while $2^q$ contains only 2. [A1]

Step 4: Contradiction & Conclusion [1 mark]
An odd number cannot equal an even number ($3^p \neq 2^q$). Contradiction!
Hence $\log_3(2)$ is irrational. [R1]