Proof by contradictionEdexcel A-Level Maths: Revision notes

In proof by contradiction you assume the opposite of what you want to prove, and then use correct logical steps to reach something impossible: a contradiction. Since every step was valid, the only faulty item must be the assumption, so the original statement is true. The write-up has four parts:

1. State the assumption clearly, for example 'Assume $\sqrt2$ is rational'.
2. Work logically from it.
3. Reach a contradiction, such as a number that is both even and odd, or a fraction not in lowest terms.
4. Conclude: 'this is a contradiction, so the assumption is false, and $\sqrt2$ is irrational'.

A rational number can be written as $\frac{a}{b}$ with $a,b$ integers and $b\neq0$. An irrational number cannot. Any rational number can be written in lowest terms, where $a$ and $b$ have no common factor other than 1. Contradiction proofs about irrationals rely on this. Useful facts about parity: $a^2$ is even $\Rightarrow$ $a$ is even (an odd number is $2k+1$ and its square $4k^2+4k+1$ is odd). The same idea works for multiples of 3: if $a$ is not a multiple of 3 then $a=3k\pm1$ and $a^2=3(3k^2\pm2k)+1$ is not a multiple of 3.

Assume $\sqrt2=\frac{a}{b}$ with $a,b$ integers in lowest terms. Square: $2=\frac{a^2}{b^2}$, so $a^2=2b^2$. Hence $a^2$ is even, so $a$ is even. Write $a=2k$. Then $4k^2=2b^2$, so $b^2=2k^2$, which is even, so $b$ is even. Now $a$ and $b$ are both even, so they have the common factor 2. This contradicts lowest terms. Hence $\sqrt2$ is irrational. The same pattern proves $\sqrt3$ irrational, using multiples of 3 in place of even numbers.

Assume there are finitely many primes $p_1,p_2,\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$. Either $N$ is prime, or it has a prime factor. In both cases there is a prime that is not in the list. This contradicts the assumption that the list contained all primes. Hence there are infinitely many primes.

Strategy for a new statement: (1) negate it carefully, (2) translate the assumption into algebra, (3) manipulate to a contradiction.

• Negation: the opposite of 'is irrational' is 'is rational'. The opposite of 'there are no integers $m,n$ with $15m+25n=1$' is 'there are integers $m,n$ with $15m+25n=1$'.
• Typical contradictions: even equals odd; a fraction not in lowest terms; an integer between 0 and 1; a number divisible by 5 that equals 1. Example: prove that $\log_2 3$ is irrational. Assume $\log_2 3=\frac{p}{q}$ with $p,q$ positive integers. Then $2^p=3^q$, but $2^p$ is even and $3^q$ is odd. Contradiction.