Euler’s Proof

I was reminded of Euler’s proof that there are infinitely many prime numbers in reading my new (used) copy of Karl Popper’s book “The Logic of Scientific Discovery”. My synopsis of that book should be coming soon. Euler is an inspiring figure on all accounts, a pioneer of most of the mathematics I use today.

First, a silly related proof, to get us in the mood.

Statement: All numbers are interesting.

Proof: Assume not. If so, there would be a smallest uninteresting number, and to some standards, that would be interesting.

Now the real thing:

Statement: There is an infinite number of prime numbers.

Proof (from Euler): Take all primes p_i and assume that i is a finite number. We can make a new number which is the product of all primes, call it P, plus one: q = \prod\limits_{i=1}^i p_i +1 = P+1. If our new number is prime, we are done. We have given a prescription for making new big primes. If not, our new number must be divisible by our old building blocks, the finite primes.

We have reached a contradiction. Let’s see why. If for some special prime divides q , we also know that the special prime divides P. We can rewrite the first expression by adding zero as P-P so that we know p_s divides (q+P-P). Sneakily, our prime divides q-P, as we can write (q-P)/p_s + P/p_s. Looking above, we recall q-P = 1 so that our special prime has an impossible task: to divide 1, and thus cannot exist. That means that all along q was indeed not divisible by any of the finite primes, and thus is prime itself.

Within this proof, we also have shown that any number that divides two numbers, also divides their difference.

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 )

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