Misunderstanding Euclid

Category: things you thought you knew that are wrong
Today's entry is from mathoverflow:

Many students believe that 1 plus the product of the first n primes is always a prime number. They have misunderstood the contradiction in Euclid's proof that there are infinitely many primes. (By the way, 2 * 3 * 5 * 7 * 11 * 13 + 1 is not prime.)

Let's ask Python:

from math import sqrt def f(N): N += 1 print 'N', N n = int(sqrt(N)) for i in range(2, n+1): if not N % i: print i, N/i >>> N = 2*3*5*7*11*13 >>> f(N) N 30031 59 509 >>> N *= 17 >>> f(N) N 510511 19 26869 97 5263 277 1843 >>> N *= 19 >>> f(N) N 9699691 347 27953

What the theorem actually says (wikipedia):

Take any finite list of prime numbers p₁, p₂, ..., p_n. It will be shown that at least one additional prime number not in this list exists. Let P be the product of all the prime numbers in the list: P = p₁p₂...p_n. Let q = P + 1.

Then, q is either prime or not:

If q is prime then there is at least one more prime than is listed.

If q is not prime then some prime factor p divides q. This factor p is not on our list: if it were, then it would divide P (since P is the product of every number on the list); but as we know, p divides P + 1 = q. Then p would have to divide the difference of the two numbers, which is (P + 1) − P or just 1. But no prime number divides 1 so there would be a contradiction, and therefore p cannot be on the list. This means at least one more prime number exists beyond those in the list.