Saturday, August 27, 2011

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 p1, p2, ..., pn. 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 = 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.