Proof by contradiction – Year 13 A level maths revision notes to download as PDF

Worked example 1

Prove that \(\sqrt{2}\) is irrational.

Assume \(\sqrt{2}\) is rational. Then \(\sqrt{2}=\tfrac{a}{b}\) where \(a,b\) are integers with no common factor (lowest terms) and \(b\ne0\). Squaring gives \(a^2=2b^2\). Hence \(a^2\) is even, so \(a\) is even and \(a=2k\). Then \(4k^2=2b^2\), so \(b^2=2k^2\), hence \(b^2\) is even and \(b\) is even. Now both \(a\) and \(b\) are even, so they have a common factor 2. This contradicts the assumption that \(\tfrac{a}{b}\) was in lowest terms. Therefore \(\sqrt{2}\) is irrational. \(\blacksquare\)

Worked example 2

Prove that there are infinitely many primes.

Assume there are finitely many primes \(p_1,p_2,\dots,p_k\). Let \(N=p_1p_2\cdots p_k+1\). Then \(N>1\), so \(N\) has a prime factor, which must be one of the \(p_i\). That prime divides \(p_1p_2\cdots p_k\) and also \(N\), so it divides \(N-p_1\cdots p_k=1\). No prime divides 1. This is a contradiction, so there are infinitely many primes. \(\blacksquare\)

Worked example 3

Prove that if \(x\) is rational and \(y\) is irrational then \(x+y\) is irrational.

Assume \(x+y\) is rational: \(x+y=\tfrac{p}{q}\) and \(x=\tfrac{r}{s}\) with integers \(p,q,r,s\), \(q,s\ne0\). Then \(y=\tfrac{p}{q}-\tfrac{r}{s}=\tfrac{ps-qr}{qs}\), a ratio of integers with \(qs\ne0\), so \(y\) is rational. This contradicts \(y\) being irrational. Hence \(x+y\) is irrational. \(\blacksquare\)

Worked example 4

Prove that there are no integers \(m,n\) with \(14m+21n=1\).

Assume there are. Then \(7(2m+3n)=1\), so \(2m+3n=\tfrac{1}{7}\), but \(2m+3n\) is an integer. This is a contradiction. \(\blacksquare\)

Worked example 5: irrationality of the square root of 3

Prove that \(\sqrt3\) is irrational.

Assume \(\sqrt3=\dfrac ab\) with integers \(a,b\) in lowest terms, \(b\ne0\). Then \(a^2=3b^2\), so \(3\mid a^2\). If \(3\nmid a\) then \(a=3k\pm1\) and \(a^2=9k^2\pm6k+1\) leaves remainder 1 when divided by 3, a contradiction, so \(3\mid a\). Write \(a=3k\): \(9k^2=3b^2\), so \(b^2=3k^2\) and \(3\mid b\) by the same argument. So 3 divides both \(a\) and \(b\), contradicting lowest terms. Hence \(\sqrt3\) is irrational. \(\blacksquare\)

Worked example 6: there is no smallest positive rational

Prove that there is no smallest positive rational number.

Assume there is a smallest positive rational number \(r\). Then \(\dfrac r2\) is also rational and positive. But \(\dfrac r2\lt r\) since \(r>0\). This contradicts \(r\) being the smallest. Hence there is no smallest positive rational number. \(\blacksquare\) The same idea shows there is no largest integer: if \(n\) were the largest, \(n+1\) would be larger.

Worked example 7: a logarithm that is irrational

Prove that \(\log_23\) is irrational.

Assume \(\log_23=\dfrac pq\) with positive integers \(p,q\). Then \(2^{p/q}=3\), so \(2^p=3^q\). The left-hand side is even, since \(p\ge1\), and the right-hand side is odd, being a product of odd numbers. An integer cannot be both even and odd, so this is a contradiction. \(\blacksquare\)

Worked example 8: a cubic with no rational root

Prove that \(x^3+x+1=0\) has no rational roots.

Assume the root is \(\dfrac pq\) in lowest terms. Multiply by \(q^3\): \(p^3+pq^2+q^3=0\). At least one of \(p,q\) is odd. If both are odd, the three terms are odd, and their sum is odd. If \(p\) is even and \(q\) is odd, the terms are even, even, odd, so the sum is odd. If \(p\) is odd and \(q\) is even, the terms are odd, even, even, so the sum is odd. The sum is never 0, a contradiction. \(\blacksquare\)

Worked example 9: contradiction with an inequality

Prove that there are no real numbers \(x\) with \(x^2-6x+10<0\).

Assume there is such an \(x\). Complete the square: \(x^2-6x+10=(x-3)^2+1\). Then \((x-3)^2+1<0\) gives \((x-3)^2<-1\). But the square of a real number is never negative. This is a contradiction. \(\blacksquare\) In fact \(x^2-6x+10\ge1\) for all real \(x\).

Worked example 10: a flaw spotted in a proof

A student argues: "Assume there is a largest prime \(P\). Let \(N=P+1\). Then \(N\) is bigger than \(P\), so \(N\) is not prime, so there is a contradiction." Explain what is wrong.

The student has not shown that \(N\) is composite or has a prime factor larger than \(P\). For example, if \(P=2\) then \(N=3\) is prime. In Euclid’s proof \(N\) is built as \(p_1p_2\cdots p_k+1\) so that it has remainder 1 on division by every listed prime, which forces a new prime factor. Always check that every step follows from the previous one.