There are an infinite number of integers, so there must be an infinite number of primes.
This is the main thing I am going to retain from this post (sorry, Lakshmi).
Until now, if asked to prove why there are infinite prime numbers, I would have answered “because Euclid’s Theorem” (Euclid’s proof is very easy to remember and explain verbally without formal notation). It never occurred to me that I could have just answered “because there are infinite integers, duh”.
What really shocks me is that I’ve just spent 20 minutes digging “infinite primes” results, and no one points out this. Every “infinite prime numbers” page I found reports either Euclid’s Theorem or something even more complicated (it seems that people still publish 1-page papers proving the infinitude of primes). I’m very confused. I mean, “infinite integers imply infinite primes” is not a fully-fledged formal proof, but it shouldn’t be difficult to write an actual formal proof from that statement… am I failing to see some obvious things? (like, maybe that proof boils down to Euclid’s Theorem?)
I was actually wrong about this!!! After reading your comment, I thought about it more. We can create an infinite number of integers by exponentiating a single prime, like 2, an arbitrary number of times. So we could do 2^2, 2^(2^2), 2^(2^(2^2))), etc. Of course, we can easily find numbers, like 3, that can’t be created in this manner. But without a proof, it’s not immediately obvious that we couldn’t create all the integers by multiplying a finite set of primes an arbitrary number of times. Even if we’ve proven than every integer greater than 1 has a unique prime factorization, we need a separate proof to show that infinite primes are needed to construct all integers greater than one, rather than just one more prime than we currently have in the set. This is the proof that Euclid’s Theorem provides.
The fact that there are infinite integers can only let us deduce that there are infinite primes if we’ve already proved that every integer greater than 1 has a unique prime factorization (the Fundamental Theorem of Algebra). This point might be a little less obvious :)
This is the main thing I am going to retain from this post (sorry, Lakshmi).
Until now, if asked to prove why there are infinite prime numbers, I would have answered “because Euclid’s Theorem” (Euclid’s proof is very easy to remember and explain verbally without formal notation). It never occurred to me that I could have just answered “because there are infinite integers, duh”.
What really shocks me is that I’ve just spent 20 minutes digging “infinite primes” results, and no one points out this. Every “infinite prime numbers” page I found reports either Euclid’s Theorem or something even more complicated (it seems that people still publish 1-page papers proving the infinitude of primes). I’m very confused. I mean, “infinite integers imply infinite primes” is not a fully-fledged formal proof, but it shouldn’t be difficult to write an actual formal proof from that statement… am I failing to see some obvious things? (like, maybe that proof boils down to Euclid’s Theorem?)
I was actually wrong about this!!! After reading your comment, I thought about it more. We can create an infinite number of integers by exponentiating a single prime, like 2, an arbitrary number of times. So we could do 2^2, 2^(2^2), 2^(2^(2^2))), etc. Of course, we can easily find numbers, like 3, that can’t be created in this manner. But without a proof, it’s not immediately obvious that we couldn’t create all the integers by multiplying a finite set of primes an arbitrary number of times. Even if we’ve proven than every integer greater than 1 has a unique prime factorization, we need a separate proof to show that infinite primes are needed to construct all integers greater than one, rather than just one more prime than we currently have in the set. This is the proof that Euclid’s Theorem provides.
The fact that there are infinite integers can only let us deduce that there are infinite primes if we’ve already proved that every integer greater than 1 has a unique prime factorization (the Fundamental Theorem of Algebra). This point might be a little less obvious :)