For an introduction to this series see this article. Briefly, I show some beautiful math that can be understood with only the math learned in elementary school.
The prime numbers
The prime numbers are defined as integers (whole numbers) greater than 1 that can be evenly divided only by 1 and themselves. The first few primes are
2, 3, 5, 7, 11 …..
And, for example, 4 is not prime because it is 2*2.
The primes are basic to a lot of things in math; for example, every positive integer greater than 1 can be factored into prime numbers. (e.g. 28 = 2*2*7).
One of the most fascinating topics in math is the infinite. Formal and correct treatment of infinity didn’t take place until Georg Cantor (1845-1918) came along. I may cover some of the complicated topics in a later article. But on a much simpler level, one difference between letters and numbers is that the letters stop with Z while the numbers go on forever. Some children get interested in names for really large numbers (billion, trillion, google, googleplex and so on).
Are the primes infinite?
That the integers go on forever seems intuitive to most people. Name a number and I can always add 1 to it to get a bigger number. But what about the primes? They certainly get less common as they get larger – but do they ever stop? No, they don’t and there are many proofs that they don’t, which I will discuss below. First though, another question:
Why prove things multiple ways?
The first proof that the primes go on forever is due to Euclid around 300 BC. Given that that proof exists and is very elegant, why do mathematicians look for new ones? Mathematicians will give reasons such as “each proof illustrates some new feature of the theorem”. But I think the question itself betrays a misconception. One rejoinder would be “People have already written plays about two people falling in love. Why write another?” Math is not like a courtroom debate where the only goal is to prove your case to the judge and jury. It’s more like writing or painting where one goal is to create something beautiful.
Euclid’s proof of the infinitude of the primes
Euclid’s proof is a reductio ad absurdum proof. In this sort of proof, we first assume the opposite of what we want to show and then derive nonsense from it. So, we start by assuming there is a largest prime. Let’s call it p. Next, we find all the primes less than or equal to p and multiply them together. Then we add 1. This new number is clearly larger than p. Either it is prime (in which case p is not the largest prime) or it has prime factors. But none of its factors can be less than p either, since we added 1 to the product. Therefore, those factors must be prime numbers greater than p. Either way, p is not the largest prime.
For example, suppose we thought 5 was the largest prime. First, find all the primes less than or equal to 5. They are 2, 3 and 5. Multiply them together and you get 30. Add one and you get 31. 31 divided by any number in the list (2, 3, 5) leaves a remainder of 1. So, either 31 is prime (it turns out that this is the case) or it has some prime factor greater than 5,
Other proofs of the infinitude of the primes
The wonderful book Charming Proofs lists three other proofs, I give details of two of them. I give more detail than the authors of that book do, since I am writing for the math-phobic.
First, one by Ernst Edward Kummer, also a reductio proof, which starts the same way as Euclid’s but then varies:
Suppose there are only k primes. Multiply them all together and call the result and add one. We have assumed that N + 1 cannot be prime. Therefore, it must have a prime divisor in common with N (because that list had all the primes, remember?). Call this divisor pj . So far, we have found that pj is a divisor of both N and N + 1. But a number that divides two numbers also divides the difference between the larger number and the smaller one (for example, 2 divides both 10 and 14, it also divides the difference between them (4)) But the difference between N and N + 1 is 1 and nothing divides 1, including pj . Therefore our assumption is wrong and there are not only k primes.
Second, a recent proof by Filip Saidak that goes quite a bit farther than Euclid’s proof, showing that there are integers with an arbitrary number of prime factors:
Let N be some whole number greater than 1. Since N and N + 1 are consecutive, they are relatively prime (that is, they have no factors in common; see Kummer’s proof). Multiply them together and call the result N2. N2 must have at least two prime factors. (For example, 5*6 = 30 has prime factors 2, 3, 5). But we can then form another number N3 = N2 times N2 + 1. The factors of N3 must include those of N2 but they also have to have at least one more. This can be continued arbitrarily.