Same old, same old
May 3, 2012 3 Comments
So I suppose we should start with the “standard proof.” Take any finite collection of prime numbers , and let
Write down all the factors of . Notice that cannot be factors, because then would have to be divisible by these primes too. So must be divisible by a prime not on our list. Hence, no finite list of primes can be complete, so there must be infinitely many primes.
This proof, or something more or less equivalent, was given by Euclid about 2300 years ago. That’s mind-boggingly long ago.
Those who know me well know that I prefer to avoid proof by contradiction if possible. Notice that this is not a proof by contradiction. I never assumed there were only finitely many primes (Euclid didn’t either). I just started with a finite list, and produced something not on the list. It’s a common belief that this proof is one by contradiction. It wasn’t. Now you know.
Warning: Technical Ring Theory Junk
Another common belief is that this proof requires unique factorization. This is also false. Certainly don’t divide . All we need now is to say that must be divisible by another prime. Whether or not we cite unique factorization, we need to know that is not a unit. Instead of citing unique factorization, we can note that each non-unit is included in some maximal ideal, and that is a principal ideal domain, so this maximal ideal is generated by some prime element. That is, it’s divisible by some prime.
Some may argue that being a principal ideal domain implies we have unique factorization. Yes, but the point is that I never needed to prove this fact.