McIntyre MathsMathematics Extension 2
Extension 2 › Proof › Lesson 4

Lesson 4 · Proof by contrapositive and contradiction

Mathematics Extension 2 · Proof · Outcome ME2-12-01 · Term 4 · Week 2
Learning intentionTo prove results indirectly, by proving the contrapositive or by showing that the negation leads to a contradiction.
Success criteria · I can…
  • decide when proving the contrapositive is easier, and set it out correctly
  • set out a proof by contradiction: assume the negation, reach a contradiction, conclude
  • prove that numbers such as 2\sqrt{2} and log⁡25\log_2 5 are irrational
  • combine methods, for example a lemma by contrapositive inside a contradiction proof

Lesson flow

LaunchWarm-up · Negations for proofsSlide 2DefinitionsProof by contrapositiveSlide 3ExamplesExample 2 · Proof by contrapositiveSlide 4ExamplesExample 3 · Contrapositive with “or”Slide 5HSC practiceHSC practice · Proof by contrapositiveSlide 6DefinitionsProof by contradictionSlide 7ExamplesExample 5 · Proof by contradictionSlide 8ExamplesExample 6 · A logarithmSlide 9HSC practiceHSC practice · Irrational logarithmsSlide 10HSC practiceHSC practice · Another surdSlide 11ExamplesExample 7 · Infinitely many primes (Euclid)Slide 12ExamplesExample 8 · Combining methodsSlide 13HSC practiceHSC practice · Converse by contrapositiveSlide 14ThinkSpot the flaw · ContradictionSlide 15Exit ticketExit ticketSlide 16

Warm-up · Negations for proofs

Slide 2

Write each of these.

(a) The contrapositive of: if n2n^2 is odd, then nn is odd.
Show answerHide answer
Answer
If nn is even, then n2n^2 is even.
Why
The contrapositive of P⇒QP\Rightarrow Q is ¬Q⇒¬P\neg Q\Rightarrow\neg P: negate both statements and swap them.
(b) The negation of: 2\sqrt2 is rational.
Show answerHide answer
Answer
2\sqrt2 is irrational.
Why
For a real number, “not rational” means irrational.
(c) The definition: xx is rational means …
Show answerHide answer
Answer
x=pqx=\dfrac{p}{q} with p,q∈Zp,q\in\mathbb{Z}, q≠0q\neq0. We may also take pq\dfrac pq in lowest terms (pp and qq coprime).
Why
Cancelling any common factor gives lowest terms. This is the key fact used in proofs of irrationality.
(d) The negation of: there are finitely many primes.
Show answerHide answer
Answer
There are infinitely many primes.
Why
The negation of “finitely many” is “infinitely many”.

Proof by contrapositive

Slide 3
Key idea
To prove P⇒QP\Rightarrow Q by contrapositive
  1. Write the contrapositive ¬Q⇒¬P\neg Q\Rightarrow\neg P.
  2. Prove ¬Q⇒¬P\neg Q\Rightarrow\neg P directly.
  3. Conclude: an implication is logically equivalent to its contrapositive, so P⇒QP\Rightarrow Q is true.

When? When ¬Q\neg Q gives you something concrete to work with (“nn is odd” gives n=2k+1n=2k+1) but QQ does not.

Example 1

Prove that if n2n^2 is even, then nn is even.
Show answerHide answer
Answer
Contrapositive: if nn is odd, then n2n^2 is odd.
Let n=2k+1n=2k+1, k∈Zk\in\mathbb{Z}. Then n2=4k2+4k+1=2(2k2+2k)+1n^2=4k^2+4k+1=2(2k^2+2k)+1, which is odd.
Hence if n2n^2 is even, then nn is even.
Why
A direct proof is awkward: “n2=2mn^2=2m” gives no handle on nn. The contrapositive starts from “nn is odd”, which gives a usable form. We will use this result as a lemma later in the lesson.

Example 2 · Proof by contrapositive

Slide 4
For integers nn, prove that if n2−6n+5n^2-6n+5 is even, then nn is odd.
Show answerHide answer
Answer
Contrapositive: if nn is even, then n2−6n+5n^2-6n+5 is odd.
Let n=2kn=2k. Then n2−6n+5=4k2−12k+5=2(2k2−6k+2)+1n^2-6n+5=4k^2-12k+5=2(2k^2-6k+2)+1, which is odd.
Hence if n2−6n+5n^2-6n+5 is even, then nn is odd.
Why
The negation of “nn is odd” is “nn is even”, which gives n=2kn=2k to substitute.

Example 3 · Contrapositive with “or”

Slide 5
(a) For integers aa and bb, prove that if abab is even, then aa is even or bb is even.
Show answerHide answer
Answer
Contrapositive: if aa and bb are both odd, then abab is odd. This was proved in Lesson 3, Example 1: (2j+1)(2k+1)=2(2jk+j+k)+1(2j+1)(2k+1)=2(2jk+j+k)+1.
Why
Negating “or” gives “and”: ¬(A∨B)≡¬A∧¬B\neg(A\vee B)\equiv\neg A\wedge\neg B. So the negation of “aa is even or bb is even” is “aa is odd and bb is odd”.
(b) For x>0x>0, prove that if xx is irrational, then x\sqrt x is irrational.
Show answerHide answer
Answer
Contrapositive: if x\sqrt x is rational, then xx is rational.
Let x=pq\sqrt x=\dfrac pq with p,q∈Zp,q\in\mathbb{Z}, q≠0q\neq0. Then x=p2q2x=\dfrac{p^2}{q^2}, a ratio of integers with q2≠0q^2\neq0, so xx is rational.
Why
The negation of “irrational” is “rational”, and a rational number has a concrete form p/qp/q to work with. That is why the contrapositive is easier.

HSC practice · Proof by contrapositive

Slide 6
Adapted from 2022 HSC Q13(a)Let n≥3n\geq3 be an integer. Prove by contrapositive that if 2n−12^n-1 is prime, then nn is odd.
Show answerHide answer
Answer
Contrapositive: if n≥3n\geq3 is even, then 2n−12^n-1 is not prime.
Let n=2kn=2k with k≥2k\geq2. Then 2n−1=(2k)2−1=(2k−1)(2k+1)2^n-1=(2^k)^2-1=(2^k-1)(2^k+1).
Since k≥2k\geq2, 2k−1≥32^k-1\geq3 and 2k+1≥52^k+1\geq5, so 2n−12^n-1 is a product of two integers greater than 1, and is not prime.
Hence if 2n−12^n-1 is prime, then nn is odd.
Why
The difference of two squares factorises 2n−12^n-1 when nn is even. Discussion: why n≥3n\geq3? For n=2n=2, 22−1=32^2-1=3 is prime, so the result would fail.

Proof by contradiction

Slide 7
Key idea
To prove PP by contradiction
  1. Suppose, for contradiction, that ¬P\neg P is true.
  2. Reason logically from this assumption.
  3. Reach something impossible (it contradicts a known fact or the assumption).
  4. Conclude ¬P\neg P is false, so PP is true. □\square

Lemma we use: if n2n^2 is even, then nn is even (Example 1).

Example 4

Prove that 2\sqrt2 is irrational.
Show answerHide answer
Answer
Suppose, for contradiction, that 2=pq\sqrt2=\dfrac pq with p,q∈Zp,q\in\mathbb{Z}, q≠0q\neq0, in lowest terms (no common factor).
Then p2=2q2p^2=2q^2, so p2p^2 is even and hence pp is even (lemma). Let p=2mp=2m.
Then 4m2=2q24m^2=2q^2, so q2=2m2q^2=2m^2, which is even, so qq is even.
Both pp and qq are even, contradicting lowest terms. Hence 2\sqrt2 is irrational.
Why
Markers look for the explicit assumption (“Suppose, for contradiction, that …”) and an explicit statement of the contradiction. Lowest terms is what makes “both even” impossible.

Example 5 · Proof by contradiction

Slide 8
(a) Prove that there are no integers aa and bb such that 4a+6b=134a+6b=13.
Show answerHide answer
Answer
Suppose, for contradiction, that such integers exist. Then 4a+6b=2(2a+3b)4a+6b=2(2a+3b) is even, but 13 is odd. This is a contradiction, so no such integers exist.
Why
Whenever the claim is “there are no …”, assume that there is one and see what goes wrong.
(b) For positive reals xx and yy, prove that if xy>25xy>25, then x>5x>5 or y>5y>5.
Show answerHide answer
Answer
Suppose, for contradiction, that xy>25xy>25 and x≤5x\leq5 and y≤5y\leq5. Since x,y>0x,y>0, xy≤5×5=25xy\leq5\times5=25. This contradicts xy>25xy>25. Hence if xy>25xy>25, then x>5x>5 or y>5y>5.
Why
To contradict P⇒QP\Rightarrow Q we assume P∧¬QP\wedge\neg Q (Lesson 1). Here ¬Q\neg Q is “x≤5x\leq5 and y≤5y\leq5”. Positivity is needed to multiply the inequalities.

Example 6 · A logarithm

Slide 9
Prove that log⁡25\log_2 5 is irrational.
Show answerHide answer
Answer
Suppose, for contradiction, that log⁡25=pq\log_2 5=\dfrac pq with p,qp,q positive integers (valid since log⁡25>0\log_2 5>0).
Then 2p/q=52^{p/q}=5, so 2p=5q2^p=5^q.
The left side is even and the right side is odd. This is a contradiction, so log⁡25\log_2 5 is irrational.
Why
Rewrite the logarithm as a power and raise both sides to the power qq to remove the fraction. Any positive power of 2 is even and any power of 5 is odd.

HSC practice · Irrational logarithms

Slide 10
2020 HSC Q14(d)Let n≥2n\geq2 be an integer. Prove that log⁡n(n+1)\log_n(n+1) is irrational.
Show answerHide answer
Answer
Since n+1>n>1n+1>n>1, log⁡n(n+1)>1>0\log_n(n+1)>1>0. Suppose, for contradiction, that log⁡n(n+1)=ab\log_n(n+1)=\dfrac ab with a,ba,b positive integers.
Then na/b=n+1n^{a/b}=n+1, so (n+1)b=na(n+1)^b=n^a.
One of nn and n+1n+1 is even and the other is odd. Any positive power of an even number is even and of an odd number is odd, so one side is even and the other is odd. This is a contradiction.
Hence log⁡n(n+1)\log_n(n+1) is irrational.
Why
You must say why aa and bb can be taken positive: the logarithm is positive. This step is often missed. Then the parity argument is the same as in Example 6.

HSC practice · Another surd

Slide 11
2023 HSC Q12(a)Prove by contradiction that 23\sqrt{23} is irrational.
Show answerHide answer
Answer
Suppose, for contradiction, that 23=pq\sqrt{23}=\dfrac pq with p,q∈Zp,q\in\mathbb{Z}, q≠0q\neq0, coprime.
Then p2=23q2p^2=23q^2, so 23∣p223\mid p^2. Since 23 is prime, 23∣p23\mid p. Let p=23xp=23x.
Then 232x2=23q223^2x^2=23q^2, so q2=23x2q^2=23x^2 and 23∣q223\mid q^2, so 23∣q23\mid q.
Then 23 divides both pp and qq, contradicting that they are coprime. Hence 23\sqrt{23} is irrational.
Why
The step “23∣p2⇒23∣p23\mid p^2\Rightarrow23\mid p” uses that 23 is prime. Compare Example 8(a) for 3, where the same fact was proved by contrapositive.

Example 7 · Infinitely many primes (Euclid)

Slide 12

Suppose, for contradiction, that there are finitely many primes p1,p2,…,pnp_1,p_2,\ldots,p_n. Let N=p1p2⋯pn+1N=p_1p_2\cdots p_n+1.

(a) Explain why NN is not divisible by any of p1,p2,…,pnp_1,p_2,\ldots,p_n.
Show answerHide answer
Answer
Dividing NN by any pip_i leaves remainder 1.
Why
The product p1p2⋯pnp_1p_2\cdots p_n is divisible by each pip_i, so adding 1 leaves remainder 1.
(b) Explain why this gives a contradiction, and complete the proof.
Show answerHide answer
Answer
N>1N>1, so NN has a prime factor (or is itself prime). That prime is not in the list, contradicting the assumption that the list contains all the primes. Hence there are infinitely many primes.
Why
Common error: claiming NN itself must be prime. For example, 2⋅3⋅5⋅7⋅11⋅13+1=30031=59×5092\cdot3\cdot5\cdot7\cdot11\cdot13+1=30031=59\times509. What matters is that NN has a prime factor outside the list.

Example 8 · Combining methods

Slide 13
(a) Prove by contrapositive that if 3∣n23\mid n^2, then 3∣n3\mid n. (Use n=3k+1n=3k+1, 3k+23k+2.)
Show answerHide answer
Answer
Contrapositive: if 3∤n3\nmid n, then 3∤n23\nmid n^2. If 3∤n3\nmid n then n=3k+1n=3k+1 or n=3k+2n=3k+2.
n=3k+1⇒n2=3(3k2+2k)+1n=3k+1\Rightarrow n^2=3(3k^2+2k)+1.
n=3k+2⇒n2=3(3k2+4k+1)+1n=3k+2\Rightarrow n^2=3(3k^2+4k+1)+1.
Neither is divisible by 3. Hence if 3∣n23\mid n^2, then 3∣n3\mid n.
Why
An integer not divisible by 3 leaves remainder 1 or 2, which gives exactly the two cases.
(b) Hence prove by contradiction that 3\sqrt3 is irrational.
Show answerHide answer
Answer
Suppose 3=pq\sqrt3=\dfrac pq in lowest terms, p,q∈Zp,q\in\mathbb{Z}, q≠0q\neq0. Then p2=3q2p^2=3q^2, so 3∣p23\mid p^2 and, by (a), 3∣p3\mid p. Let p=3mp=3m. Then 9m2=3q29m^2=3q^2, so q2=3m2q^2=3m^2, so 3∣q23\mid q^2 and 3∣q3\mid q. This contradicts lowest terms. Hence 3\sqrt3 is irrational.
Why
The proof follows the pattern of Example 4, with part (a) acting as the lemma in place of “n2n^2 even ⇒n\Rightarrow n even”.
(c) Given that 6\sqrt6 is irrational, prove that 2+3\sqrt2+\sqrt3 is irrational.
Show answerHide answer
Answer
Suppose, for contradiction, that 2+3=r\sqrt2+\sqrt3=r with rr rational. Squaring, r2=5+26r^2=5+2\sqrt6, so 6=r2−52\sqrt6=\dfrac{r^2-5}{2}, which is rational. This contradicts the fact that 6\sqrt6 is irrational. Hence 2+3\sqrt2+\sqrt3 is irrational.
Why
Squaring produces the surd 6\sqrt6, which is the quantity we are given information about. Rational numbers are closed under addition, multiplication and division by non-zero rationals.

HSC practice · Converse by contrapositive

Slide 14
2020 HSC Q15(a)(ii)–(iii)Let kk be an integer. In Lesson 3 you proved: if 3∣(k+1)3\mid(k+1), then 3∣(k3+1)3\mid(k^3+1).
(i) Write the contrapositive of this statement.
(ii) Write the converse, and prove it is true by proving its contrapositive.
Show answerHide answer
Answer
(i) If k3+1k^3+1 is not divisible by 3, then k+1k+1 is not divisible by 3.
(ii) Converse: if 3∣(k3+1)3\mid(k^3+1), then 3∣(k+1)3\mid(k+1). Its contrapositive: if 3∤(k+1)3\nmid(k+1), then 3∤(k3+1)3\nmid(k^3+1).
If 3∤(k+1)3\nmid(k+1), then k+1=3p+1k+1=3p+1 or k+1=3p+2k+1=3p+2.
Case 1, k+1=3p+1k+1=3p+1: k=3pk=3p, so k3+1=27p3+1=3(9p3)+1k^3+1=27p^3+1=3(9p^3)+1.
Case 2, k+1=3p+2k+1=3p+2: k=3p+1k=3p+1, so k3+1=27p3+27p2+9p+2=3(9p3+9p2+3p)+2k^3+1=27p^3+27p^2+9p+2=3(9p^3+9p^2+3p)+2.
Neither is divisible by 3, so the converse is true. Hence 3∣(k+1)⇔3∣(k3+1)3\mid(k+1)\Leftrightarrow3\mid(k^3+1).
Why
The contrapositive of the converse is the inverse of the original statement. Take care to work with the expression k3+1k^3+1, not (k+1)3(k+1)^3: the quantity that must be shown not divisible by 3 is k3+1k^3+1.

Spot the flaw · Contradiction

Slide 15

A student wrote this. Find the flaw, explain why it matters, then write a correct version.

Claim

2+3\sqrt2+\sqrt3 is irrational.

  1. Suppose, for contradiction, that 2+3\sqrt2+\sqrt3 is rational.
  2. But 2\sqrt2 and 3\sqrt3 are both irrational, and the sum of two irrational numbers is irrational.
  3. So 2+3\sqrt2+\sqrt3 is irrational, which contradicts line 1. □\square
Task Find the flaw, explain why it matters, and write a correct version.
Show answerHide answer
Answer
Flaw 1: “the sum of two irrational numbers is irrational” is false: 2+(2−2)=2\sqrt2+(2-\sqrt2)=2.
Flaw 2: the assumption in line 1 is never used. Line 2 simply asserts the result, so there is no real contradiction.
Correct version (Example 8(c)): suppose 2+3=r∈Q\sqrt2+\sqrt3=r\in\mathbb{Q}. Then r2=5+26r^2=5+2\sqrt6, so 6=r2−52∈Q\sqrt6=\dfrac{r^2-5}{2}\in\mathbb{Q}, contradicting that 6\sqrt6 is irrational.
Why
A proof by contradiction must use the assumption to reach something impossible. Here the final line only restates the claim, and it relies on a false general statement.

Exit ticket

Slide 16
(a) Prove by contradiction that there is no largest even integer.
Show answerHide answer
Answer
Suppose, for contradiction, that NN is the largest even integer. Then N+2N+2 is even and larger than NN. This is a contradiction, so there is no largest even integer.
Why
State the assumption, produce a larger even integer, and state the contradiction.
(b) Prove by contrapositive that for integers nn, if 4∣n24\mid n^2, then nn is even.
Show answerHide answer
Answer
Contrapositive: if nn is odd, then 4∤n24\nmid n^2. Let n=2k+1n=2k+1. Then n2=4k2+4k+1=4(k2+k)+1n^2=4k^2+4k+1=4(k^2+k)+1, which leaves remainder 1 on division by 4. Hence 4∤n24\nmid n^2, and the original statement is true.
Why
Assume nn is odd and write n=2k+1n=2k+1. The remainder of 1 shows n2n^2 is not a multiple of 4.