The study of whole numbers is one of the oldest lines of inquiry in mathematics which is still thriving today. After all, it is possible in pure mathematics for the relevance of work done thousands of years ago to be undiminished today. I want to talk today about what is possibly the prototypical example of such a piece of mathematics. I am referring to Euclid’s proof of the infinitude of prime numbers.
A divisor of a number n is another, smaller number, for which there is no remainder when n is divided by it. For example, three is a divisor of six, seven is a divisor of seven and thirty-nine is a divisor of one hundred and seventeen. A prime number is a number with exactly two divisors. Let’s think about what it means to have exactly two divisors. Firstly, we observe that every whole number has at least one divisor, namely the number itself. Secondly, every whole number except for ’1′ has at least two divisors: The number itself and the number ’1′. So, with the exception of the number ’1′, being prime expresses the quality of having the fewest possible divisors. Why must there must be infinitely many such numbers?
Primes Being Divisors
Now, although the definition of a prime number is a restriction on the number of divisors the number has, the most fundamental observation that can be made about primes is the way in which they arise as divisors of other numbers. I’m obviously not talking about primes dividing other primes, because this is impossible, but consider now a number which is not prime, but which is greater than ’1′. So, we are thinking about some number with more than two divisors. Is any of these divisors prime? The answer is always yes. This is the fundamental observation. How do I know that? Well, since this number has more than two divisors, it has a divisor which is different from ’1′ and the number itself. It has what is called a non-trivial divisor: A smaller number, but not ’1′, which divides the original number. For example, three is a non-trivial divisor of fifteen. There are two alternatives: The first is that this smaller number is itself prime (like in our example), in which case we have done what we set out to do. The second is that it is not prime, e.g. the divisor four of the number twelve. In this case, it too has more than two divisors. Importantly, anything which divides this smaller number also divides the original number (a divisor of a divisor is a divisor), so in order to demonstrate that one of the divisors of the original number is a prime, it is sufficient to demonstrate that one of the divisors of this smaller number is prime. We have `reduced’ the problem to a problem about a smaller number.
We can repeat our argument exactly: Pick a non-trivial divisor of the smaller number: This is a number which is smaller still. Again we have the two alternatives: Either it is prime or it too has a non-trivial divisor. If the first alternative holds, then we are done, but if not then we can repeat the argument again. And again, each time getting a non-prime number which is smaller than the previous one, but which is not equal to one. Aha! But this cannot go on forever! It cannot go on forever because numbers with non-trivial divisors cannot keep getting smaller and smaller. The smallest is 4. So, eventually we are forced to conclude that, at some point, the first alternative holds: We come across a number which is prime. And, by our observation that the divisor of a divisor is a divisor, we have therefore found a prime divisor of the original number.
We have argued that every number greater than ’1′ and which is not prime, has a prime divisor. Since prime numbers are divisble by themselves, we have in fact proved that every number except for ’1′ has a prime divisor. This is fantastic news.
The Infinitude of Primes
The hard part is done. We are ready for Euclid’s proof. The way Euclid demonstrated that there were infinitely many prime numbers was to give a reason as to why it is the case that for every prime number, there must be a larger prime number. Allow me to demonstrate exactly how he did so with an example. Let’s choose a prime number to `start at’, say seven. Is there a prime number larger than 7? We all know that there is (11, for example) but the point is to see the way in which Euclid did it, because his method can be generalised so that it works for any prime number: No matter which prime number you start at, there is always a larger prime number. Euclid thought about the number you get if you multiply together all of the prime numbers up to and including seven and then add one. This number is 211 and is certainly larger than seven. The reason why Euclid thought about this number is that it is not divisible by any of the primes up to and including seven. By writing it out in the way in which it was constructed, i.e. as 211 = 2 x 3 x 5 x 7 + 1, one can see immediately that it leaves a remainder of one when divided by two, three, five and seven. However, we know from the previous section that it must have a prime divisor. So there must be a prime larger than seven.
And that’s all there is to it. Once this idea is grasped, Euclid’s famous proof is one sentence long: Given any prime number p, if I multiply together all the prime numbers less than or equal to p and then add one, I get a number which leaves a remainder of one when divided by any of the prime numbers less than or equal to p and whence has a prime divisor greater than p.