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

Suppose that Q+1 had a prime factor, say p. The there exist natural numbers a and b such that Q=ap and Q+1 = bp since p divides both Q and Q+1, and a and b are distinct since Q and Q+1 are distinct. But this means
Q+1-Q = p(b-a) which implies divides 1 which in turn implies p = 1, since there are no other natural numbers which divide 1. But p is a prime so p doesn’t equal 1 which is a contradiction and therefore our assumption p divides Q+1 is wrong.

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