Same old, same old

So I suppose we should start with the “standard proof.” Take any finite collection of prime numbers p_1,p_2,\dots, p_n, and let

N=p_1\cdot p_2\cdot\dots p_n+1.

Write down all the factors of N. Notice that p_1, p_2,\dots, p_n cannot be factors, because then 1 would have to be divisible by these primes too. So N 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 p_1,\dots, p_n don’t divide N. All we need now is to say that N must be divisible by another prime. Whether or not we cite unique factorization, we need to know that N is not a unit. Instead of citing unique factorization, we can note that each non-unit is included in some maximal ideal, and that \mathbb Z 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.


3 Responses to Same old, same old

  1. Pingback: And one more similar one… « Andy Soffer

  2. Pingback: No proof today « Andy Soffer

  3. Pingback: A nonstandard proof « Andy Soffer

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s