How many primes?

One of the first proofs I ever learnt was that there are an infinitely large number of prime numbers. It seems obvious that there should be such because when you build up you go 1,2,3,5,7,13 etc and you get larger and larger…why should it stop? But there isn’t actually a polynomial with linear coefficients which evaluates all primes and as mathematicians we don’t like to rely on intuition. So what do you do?

Proof of this is derived by contradiction – the mathematical method in which you prove something by assuming the opposite.

So here we go. Suppose there are a finite number of prime numbers, say n prime numbers which you can therefore denote p(1), p(2),….p(n), p(n+1). Now if we take a new number and call it p. Let p be the product of all the prime numbers with one added to it. So p(1) x p(2) x p(3) x… x p(n+1) +1. Clearly p is both larger than all of the primes and not equal to any of them. Now p cannot be prime (namely it is bigger than our finite set of all primes) – it must be divisible by one of our primes, say p(m) with m between 1 and m.

However when we divide p by p(m) we have a problem – we have a remainder 1. Hence we cannot divide p by p(m).

Reductio ad absurdum.

Now of course this requires a little bit of studying. But when you get down into the nitty gritty, you realise how the proofs work. We simply take a statement which we want to be true, and then using known mathematical truths assume the opposite and show we are “reduced to the absurd”.

Neat.

Advertisements

2 responses to “How many primes?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s