Prime Time: Reductio Ad Absurdum

Last week (7/7) we discussed the intuitionist philosophy, and it came up that the rejected Reductio Ad Absurdum. The example John used was the proof that there are infinitely many prime numbers (personally I think the irrationality of the square root of two is a little cooler).

Anyways, we didin't actually go over the proof, so here it is.

A quick refresher: A prime number is a number that can only be divided by one and itself. So 3 is prime (only 1 and 3 divide 3) and so is 7, but 9 us not (can be divided by 3) nor is 24 (2, 3, 4, 6, 8 and 12 all divide 24). The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19...

As you get higher and higher up on the number line, there are less and less prime numbers, so the natural question to ask is, do the prime numbers ever run out?

Well let's assume they do. Let's assume we eventually run out prime numbers. That must mean that there's a biggest prime number, right? Let's call our biggest prime number P. Now let's make another number, we'll call it Q. Where going to make Q but multiplying all of the prime numbers together, then adding one. Symbolically:

Q = (2*3*5*7*11*13*...*P) +1

So we do we know about Q? For starters, we know that Q can not be divided by any number between 1 and P. How do we know that? Well, Q is divided by any number between 1 and P, then the remainder will always be 1.

For the sake of comprehension, lets assume 7 is the biggest prime number (P). then:

Q = (2*3*5*7) +1 = 211

Q can't be divided evenly by 2, 3, 5 or 7 (try it, remainder 1 every time, right?). That means that there's either a number bigger than 7 (our "biggest prime") or 211 is prime (it's prime, trust me).

In general, every time we pick a P, we can always find a Q that's either prime, or has a prime factor larger than P. Therefore there's no largest prime number, and our original assumption (that P is the largest prime) is shown to be absurd. This is called Reductio Ad Absurdum (Reduction to the absurd, we say it in Latin because it reminds us that we are better than other people).

I'm not sure this is really a great outline, but I imagine most of you reading this have already seen this a few times before. If I'm wrong, and if it needs to be cleared up a little (or if you notice a mistake I've made) please leave a comment.