(This article is more or less a transcript of a show I sent to hacker public radio.)

In this short article I want to talk about prime numbers. In praticular: about the fact that there exist an infinite number of prime numbers. This has been proven more than 2000 years ago, but I noticed that a lot of my friends that don't have a mathematical background, aren't aware of this fact.

Yet it is rather easy to prove. So that is what I'll be doing in this article. If you are afraid of math, don't worry, it won't take more than 10 minutes.

First of all I am going to define a prime number. I won't go into technical details, but a positive integer is a prime number if it has exactly 2 positive divisors: 1 and the number itself.

For the proof that the sequence of prime numbers is infinite, I am going to cheat a little. I am going to use the fundamental theorem of arithmetic. This theorem states that every integer greater than 1 is either a prime number itself, or it can be written as the product of prime numbers. This product of prime number is unique, apart from the order of the factors.

An example. Take the number 42. 42 can be written as a product of prime numbers: 2x3x7. Apart from the order of the factors 2, 3 and 7, there is no other way to write 42 as a product of prime numbers. And this is true for every integer greater than 1.

This seems a trivial thing, but in fact it is not. Nevertheless, to keep this discussion on topic, I will assume that the fundamental theorem of arithmetic is valid.

Now. The proof that there are infinitely many prime numbers.

We will show that for any finite set of prime numbers, there exists at least one prime number not contained in this set. If I can prove this, it follows that the set of all prime numbers must be infinite.

So we take a random set of n prime numbers, we call those prime numbers p_1, p_2, p_3, and so on. The last one is called p_n.

Now we construct a new number, let's say q. We construct q by multiplying all those prime numbers, and add one.

Is p_1 is a divisor of q? When you divide q by p_1, the quotient equals p_2 times p_3 times p_4 and so on times p_n. The remainder is 1. This follows from how we constructed q. So p_1 is not a divisor of q.

The same is true for p_2, p_3, and so on. None of our n prime numbers is a divisor of q.

What if we apply the fundamental theorem of arithmetic to q? It says that we can write q as a product of prime numbers. So let's do that. None of those prime numbers is contained in our original set of n prime numbers, because the prime numbers in our product are divisors of q, and a_1, a_2 and so on are not. So there exists at least one other prime number, not in our finite set, which is a divisor of q.

There we are. We just proved that if you take a finite set of random prime numbers, there is always at least one prime number not contained in this set. This means the set of prime numbers is infinite.

I hope you enjoyed this proof. It is not impossible that I made a mistake, because I didn't do a lot of math for the last 10 years. If you have any comments, please let me know.