Episode: 1517
Title: HPR1517: The set of prime numbers is infinite
Source: https://hub.hackerpublicradio.org/ccdn.php?filename=/eps/hpr1517/hpr1517.mp3
Transcribed: 2025-10-18 04:33:29

---

.
Hello everybody, my name is Johan Verflut, I submitted two shows for Hacker Public Radio
some months ago and because there is now a show shortage, I decided to submit a tour
one today. In this show, I want to talk about prime numbers, in particular about the fact
that there exists an infinite number of prime numbers. This has been proven more than
two thousand years ago, but I noticed that a lot of my friends that don't have a mathematical
background aren't aware of this. Yet it is rather easy to prove, so that is what I will
be doing in this episode. If you are afraid of math, don't worry, it won't take more
than ten 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 two positive
divisors, one and a number itself. So the first prime numbers are two, three, five, seven,
and so on. 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 one is either a prime number itself, or it can be written
as a product of prime numbers. This product of prime numbers 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, two times three times seven. Apart from the order of the factors two,
three and seven, there is no other way to write 42 as a product of prime numbers. And
this can be done for every integer greater than one. This seems a trivial thing, but in
fact, it is not. Nevertheless, to keep this discussion on topic, I will assume that a
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 a set
of all prime numbers must be infinite. So, let's go. We take a random set of n prime
numbers. And we call those prime numbers P1, P2, P3, and so on. The last one is called
Pn. Now, we construct a new number. Let's say Q. We construct Q by multiplying all those
prime numbers P1, P2, et cetera, and add one. Now, it's P1, a divisor of Q. When we divide
Q by P1, the quotient equals P2 times P3 times P4 and so on, times Pn, and the remainder
is one. This is how we construct Q. So, P1 is not a divisor of Q. The same is true for
P2, P3, and so on. None of our n prime numbers is a divisor of Q. All will have remainder
one. Now, 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
in our product is contained in our original set of n prime numbers. Because all those prime
numbers are divisors of Q and the prime numbers in our original set are no divisors of Q,
like we just saw. So, there exists at least one prime number, not in our finite set P1, P2,
till Pn, that is a divisor of Q. There we are. We just proved that if you can 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 last 10 years. So,
if you have any comments, please let me know. You can find my contact info on my website,
which is Johanv.org, that is J-O-H-A-N-V.org. I want to thank HackerperbyGradio for hosting
my show. And I want you to send in a show as well, because HackerperbyGradio is running
short on shows. Just talk about anything that might be of interest to Hacker's in general,
just like I did. All information you need can be found on HackerperbyGradio.org.
HackerperbyGradio is founded by the Digital Dog Pound and the Infonomicom Computer Club.
HBR is funded by the Binary Revolution at binref.com. All binref projects are crowd-responsive
by lunar pages. From shared hosting to custom private clouds, go to lunarpages.com for all
your hosting needs. Unless otherwise stasis, today's show is released under a creative
commons, attribution, share a life, read those own license.