Proofs and Primes

Hello reader,

Following on from my post on Pythagoras, which turned into a post about proofs, I decided I should give an example of what I meant about how mathematicians can't use 'evidence', only pure logic.

Euclid (yep, him again) came up with this ingenious proof that there are an infinite number of prime numbers (if you don't know what prime numbers are, you have genuinely come to the wrong blog):

Firstly, as some groundwork, you must understand the fundamental theorem of arithmetic which is that every number can be uniquely written as the product of prime factors

For example:

236 = 2 x 2 x 59
113163 = 37 x 59 x 61
4398618 = 2 x 3 x 7 x 104729 (yes, 104729 is prime)

Prime numbers are like elements in chemistry (except there's an infinite amount of them, as we shall shortly prove). They can be multiplied together in different ways to make all the 'compound numbers' that exist, and every compound number can be broken down into its primes. But the primes cannot be 'split' / divided by any number (other than themselves and 1). Now, onto Euclid's proof

Let's first assume that there are in fact a finite number of primes. Lets say the 'set of all primes' is {2, 3, 5, 7, 11, 6th prime, 7th prime, prime8, prime9, p10.....and so on until the largest prime} In that case, we can multiply them all together to get the number P.

So P = p1 x p2 x p3 x p4 x p5..... x largest prime

then let's make a new number one bigger than P:      Q = P + 1

Now, if Q is a prime, then it is a prime existing outside the set which was meant to be the 'set of all primes'. This is a contradiction. Therefore, since we have seen a contradiction, we must assume our beginning assumption was incorrect ie. we assumed that there are a finite number of primes. This must be incorrect.

If Q is not prime, then as the fundamental theorem of arithmetic shows, it must be divisible into prime factors. In other words, it must be divisible by some prime number p. But this prime number p cannot be in the 'set of all primes'; if it were it would divide P and so cannot divide P + 1 (ie Q). Thus, once again, we have shown that there must exist a prime outside the set of all primes, which is a contradiction. Therefore (see above) it is incorrect to believe there are finite primes.

Therefore there are infinite primes.

Thanks for reading, and a special thanks to Zachary for recommending this proof which is a perfect example of what I was hoping to explain :)