Proof by contradictionAQA A-Level Maths: Revision notes

To prove a statement $S$ by contradiction:

1. Assume that $S$ is false, that is, assume the negation of $S$.
2. Use correct logical steps from that assumption.
3. Reach something impossible, a contradiction: for example a number that is both odd and even, or a fraction in lowest terms with a common factor.
4. Conclude that the assumption was wrong, so $S$ is true. Write the conclusion explicitly: "this is a contradiction, so the assumption is false, hence ..." The contradiction may be with the assumption itself or with something already known.

'$x$ is irrational' has negation '$x$ is rational'. 'There are no integers with property $P$' has negation 'there exist integers with $P$'. 'There are finitely many primes' has negation 'there are infinitely many'. 'All $x$ satisfy $P$' has negation 'some $x$ does not satisfy $P$'. A rational number can be written as $\frac{p}{q}$ with $p$, $q$ integers, $q\neq0$, and in lowest terms $p$ and $q$ have no common factor greater than $1$. Taking lowest terms is what produces the contradiction in irrationality proofs.

Assume $\sqrt2=\frac{p}{q}$ with $p$, $q$ integers and no common factor. Then $p^2=2q^2$, so $p^2$ is even, so $p$ is even (an odd number squared is odd). Write $p=2k$: $4k^2=2q^2$, so $q^2=2k^2$, so $q^2$ is even and $q$ is even. Then $p$ and $q$ share the factor $2$, contradicting 'no common factor'. So $\sqrt2$ is irrational. The same method proves $\sqrt3$ irrational: $p^2=3q^2$ gives $3\mid p^2$, so $3\mid p$ (as $3$ is prime), and then $3\mid q$.

Assume there are finitely many primes $p_1,\ldots,p_n$. Let $N=p_1p_2\cdots p_n+1$. Dividing $N$ by any $p_i$ leaves remainder $1$, so no $p_i$ divides $N$. But $N>1$ is either prime or has a prime factor, which is not on the list. This contradicts the assumption that the list contains every prime. So there are infinitely many primes. Note that $N$ need not itself be prime. For example $2\times3\times5\times7\times11\times13+1=30031=59\times509$, with both factors new primes.

Typical approaches:

• Parity: odd and even numbers, or $2^p$ even and $3^q$ odd. To show $\log_23$ is irrational: assume $\log_23=\frac{p}{q}$, so $3^q=2^p$, an odd number equal to an even one.
• Using a known irrational: to show $3+2\sqrt2$ is irrational, assume it equals $\frac{a}{b}$, so $\sqrt2=\frac{a-3b}{2b}$, a rational number, which contradicts the irrationality of $\sqrt2$.
• Factorising: to show $a^2-b^2=1$ has no positive integer solutions, $(a-b)(a+b)=1$ forces $a+b=a-b=1$ and so $b=0$. In every case state the assumption, give each step with a reason, state the contradiction and state the conclusion.