I don't like that proof...
I'm not ashamed of it - I love maths. Well more specificially I love numbers.
Ever since I was a kid, I've loved asking questions about numbers. I remember from any early age being irked by the fact that 2 is the only even prime number. Of course, my adult mind can rationalise that even means "is divisible by 2" and hence 2 is no different to any other prime number - the difference is a semantic one because we've given a label to the concept "divisible by 2". It's trivial, of course, that every prime is the only prime divisible by itself.
There are a lot of prime numbers. An awful lot. In fact, there's an infinity of them. Even at school we were taught an easy proof that there are an infinite number of prime numbers. It went like this...
Presume there's a largest prime number and call it P. Take all of the prime numbers up-to and including P and multiply them together and add one. Voila - another prime which is bigger than P. Hence a contradiction and there is no largest prime.
Of course, there are a couple of problems with this proof which you tend to gloss over at school. The first is that this misses out a lot of prime numbers because between P and this much bigger prime we've constructed, there are probably lots of other prime numbers. In fact, we know that there are primes between P and it's larger cousin (for those who care about such things, there are other proofs of the infinity of primes which put a bound on the nth prime lower than this proof I've given above, hence showing that there is at least one prime larger than P but lower than it's big cousin).
At school, I accepted this proof without question and at the time thought it was one of the "best things ever" but my adult mind questions it. I'm not convinced that it's trivial that the new number you construct in this way is definitely a prime. With my adult mind, I have always prefered a slightly adapted and belt-and-braces approach to this proof as follows.
Interestingly, you don't need to go very far to find a case where N in the example above isn't prime. 2 x 3 x 5 x 7 x 11 x 13 = 59 x 509 is the first, according to the wonderful internet :-)
Ever since I was a kid, I've loved asking questions about numbers. I remember from any early age being irked by the fact that 2 is the only even prime number. Of course, my adult mind can rationalise that even means "is divisible by 2" and hence 2 is no different to any other prime number - the difference is a semantic one because we've given a label to the concept "divisible by 2". It's trivial, of course, that every prime is the only prime divisible by itself.
There are a lot of prime numbers. An awful lot. In fact, there's an infinity of them. Even at school we were taught an easy proof that there are an infinite number of prime numbers. It went like this...
Presume there's a largest prime number and call it P. Take all of the prime numbers up-to and including P and multiply them together and add one. Voila - another prime which is bigger than P. Hence a contradiction and there is no largest prime.
Of course, there are a couple of problems with this proof which you tend to gloss over at school. The first is that this misses out a lot of prime numbers because between P and this much bigger prime we've constructed, there are probably lots of other prime numbers. In fact, we know that there are primes between P and it's larger cousin (for those who care about such things, there are other proofs of the infinity of primes which put a bound on the nth prime lower than this proof I've given above, hence showing that there is at least one prime larger than P but lower than it's big cousin).
At school, I accepted this proof without question and at the time thought it was one of the "best things ever" but my adult mind questions it. I'm not convinced that it's trivial that the new number you construct in this way is definitely a prime. With my adult mind, I have always prefered a slightly adapted and belt-and-braces approach to this proof as follows.
- Presume there is a largest prime P.
- Multiply together all of the prime numbers up-to and including P and add one to the product. Call this number N.
- N has a unique set of prime factors by the Fundamental Theorem of Arithmetic. (N may, of course, be the only prime factor of N)
- Each of the primes up-to and including P is a factor of N-1 and as each of them is larger than 1, they cannot also be a factor of N.
- So, all of the prime factors of N - whether N itself is the only such one or not - must be larger than P.
- Hence we have a contradiction.
Interestingly, you don't need to go very far to find a case where N in the example above isn't prime. 2 x 3 x 5 x 7 x 11 x 13 = 59 x 509 is the first, according to the wonderful internet :-)