## Proof by Contradiction

The aim of proof by contradiction is to prove a statement is true by assuming it is false and showing that this leads to a contradiction so that the statement must be true. This is often easier than proving the statement directly.

For example consider the proof √2 is irrational that follows

Assume root 2 is rational, ie that it can be written as r/s where s≠0 and r and s are both integers. We can choose r and s such that they have no common factors, since any common factors can be cancelled out.

then 2=r2/s2

so r2 = 2s2 —(1)

hence 2 is a factor of r2 and since 2 is prime 2 must also be a factor of r so we can write r = 2k where k is an integer.

From (1) we can now write

4k2=2s2

so s = 2k2

so 2 is also a factor of s

But we assumed r and s had no common factors, Contradiction therefore root 2 must be irrational.

So to conclude, here we have taken the statement root 2 is irrational, assumed it to be false, shown this leads to a contradiction and therefore concluded that root 2 must be irrational.

## Proof there are infinitley many prime numbers

**Introduction**

Prime numbers are natural numbers (1,2,3 etc) whose only factors are one and themselves. The first few primes are:

2,3,5,7,11,13……

note that 1 isn’t a prime.

Primes are important because every number can be written uniquely as a product of primes. This idea can also be used to prove that there infinitely many primes. The proof which follows is an example of proof by contradiction.

**Proof**

Assume that there are a finite number of primes.

Then all these primes can be written in a list

P0, P1, P2 … Pn

Then we could multiply all these numbers together and add one to get a new number Q

Q = P0P1P2…Pn + 1

This means that Q doesn’t have any of the primes as a factor as it will leave a remainder of one when divided by any of the primes, because that was how it was constructed. But every number can be written as a product of primes. Therefore Q is either a new prime or there is a prime which isn’t on the list which is a factor of Q. So the list doesn’t contain all the primes because it doesn’t contain this new prime. This is a contradiction because we assumed that the list contained all the primes, therefore there cant be a finite number of prime so there must be an infinite number of them, hence they cannot be written in a list.

**By David Woodford**

## Comments