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.