Proof by Contradiction

Example 1: Proving Surds are Irrational

Prove by contradiction that $sqrt{2}$ is irrational.

[5 marks]

Assume that the statement is not true, and so $sqrt{2}$ can be written as $dfrac{textcolor{red}p}{textcolor{blue}q}$, where $textcolor{red}p$ and $textcolor{blue}q$ are both non-zero integers.

Also, assume that $textcolor{red}p$ and $textcolor{blue}q$ have no common factors.

Then,

$begin{aligned} sqrt{2} &= dfrac{textcolor{red}p}{textcolor{blue}q} textcolor{red}p &= sqrt{2} textcolor{blue}q end{aligned}$

If we square both sides,

$textcolor{red}p^2 = 2textcolor{blue}q^2$

Therefore, $textcolor{red}p^2$ is an even number.

If $textcolor{red}p^2$ is even, then $textcolor{red}p$ must be even also (you can prove this).

So, let $textcolor{red}p=2k$ for some integer $k$, and substitute this into the last step:

$begin{aligned} textcolor{red}p^2 = (2k)^2 = 4k^2 &= 2textcolor{blue}q^2 2k^2 &= textcolor{blue}q^2 end{aligned}$

Therefore $textcolor{blue}q^2$ is even and so $textcolor{blue}q$ is also even.

However, we assumed at the beginning that $textcolor{red}p$ and $textcolor{blue}q$ had no common factors, and since they are both even they must have at least one common factor. This contradicts our initial assumption.

Hence $sqrt{2}$ cannot be written as $dfrac{textcolor{red}p}{textcolor{blue}q}$, so it is not rational.

Therefore, the statement is true.

Example 2: Proving that there are Infinitely Many Prime Numbers

Prove by contradiction that there are infinitely many prime numbers.

[5 marks]

Assume that the statement is not true in that there are a finite number of primes ($n$ of them). Write them as

$p_1, p_2, p_3, … p_{n-1}, p_n$

where $p_1 = 2$ and $p_n$ is the largest prime number.

Multiply all of these primes together, and call it $textcolor{red}{N}$:

$textcolor{red}{N = p_1 times p_2 times p_3 times … times p_{n-1} times p_n}$

$textcolor{red}{N}$ is a multiple of every prime number in the list.

Now,

$textcolor{limegreen}{N+1} = textcolor{red}{p_1 times p_2 times p_3 times … times p_{n-1} times p_n} + textcolor{blue}{1}$

$textcolor{limegreen}{N+1}$ should not be a prime number, since there are no prime numbers other than $p_1, … p_n$.

If we divide $textcolor{limegreen}{N+1}$ by $p_n$, or any other prime $p_i$, this leaves a remainder of $textcolor{blue}{1}$. Since there are no integers that divide $textcolor{blue}{1}$ other than $1$ itself, $textcolor{limegreen}{N+1}$ must be a prime number, or be divisible by another prime greater than $p_n$.

This contradicts our original assumption.

Hence, there are infinitely many primes, and the statement is true.