# On Euclid's proof of the infinitude of primes and generating primes

So looking at Euclid's proof he says 1)take a finite family of primes (F) 2)multiply all the primes and add one 3)this new number has at least 1 new prime factor

So I was wondering about what kind of primes you get by recursively feeding this process into it self.

Since the number you must factor grows exponentially, it's hard to get a lot of numerical evidence for what happens.
I calculated a few:

[2]-> [2,3]-> [2,3,7]->[2,3,7,43]->[2,3,7,43,13,139]->[2,3,7,43,13,139,3263443] ->[2,3,7,43,13,139,3263443,547,607,1033,31051]-> cannot factor 113423713055421844361000443

[5] (x5)-> [5,2,3,31,7,19,37,3343,79,193662529] -> cannot factor 234069798025176583891

Obviously quite a few primes are missing, 5,11,19,etc from the first list, but could show up later.

So my question is does a finite family of primes exist that eventually generates all the primes? I figure this probably doesn't have an easy answer, but any information related to this process would be appreciated, or even why it can't be done.

-
If you run into a number with prime factors of some multiplicity, do you add them to your list with that multiplicity or just once? (I think the problem will be easier if you add them in with multiplicity.) –  Qiaochu Yuan Nov 10 '09 at 20:34
So obviously they can cause different sequences. I am interested in know why adding multiplicity would make the sequence more manageable. The first time I saw a change was for [11] without multiplicity [11] (x5)-> [11,2,3,67,4423,43,454849,7,37,2029,727929913] with multiplicty [11] (x5)-> [11,2,2,3,7,19,97,181,103,139,21529,13,7308166138386889] –  paarshad Nov 10 '09 at 20:48
I should add this is the Sylvester sequence, and at the Polymath Project I made the conjecture that any primorial number p_n (where n is the product of the first n primes) works as an initial term so the sequence only generates primes. polymathprojects.org/2009/08/09/… –  Jason Dyer Nov 10 '09 at 21:38

Here's the reason why keeping primes with multiplicity makes the answer "no." If $p_n$ denotes the product of all the numbers you have so far, where $p_1$ is the product of the primes you start with, then $p_n = p_1 ... p_{n-1} + 1$. But we can rewrite this as $p_n = p_{n-1}(p_{n-1} - 1) + 1 = f(p_{n-1})$ where $f(x) = x^2 - x + 1$, and it is well-known that any prime divisor of $f(n)$ for an integer $n$ must be $2, 3$, or congruent to $1 \bmod 3$, i.e. the primes $5, 11, 17, ...$ will never appear (unless they divide $p_1$ to start with.)

(Sketch: if $q | x^2 - x + 1$ then $q | x^3 + 1$, hence $x$ has order $6 \bmod q$ or $q = 2, 3$. Since the multiplicative group $\bmod q$ has order $q - 1$, this is possible if and only if $6 | q-1$.)

-
@Qiaochu: Do you have an argument to show that not all primes $\equiv1\mod3$ will appear? –  Wadim Zudilin May 17 '10 at 22:39

Many have considered this question, and variants of this question, in their study of number theory. It's a good question in that it's easy to pose and fun to think about. It's not such a good question in that very little seems to be known about it.

Perhaps the most common variant of your construction is to at each stage not throw in all the prime factors of p1*...*pn + 1 but only the smallest prime factor. I call this a "Euclid sequence" with "seed" the initial, nonempty finite set of primes you start with. If your seed is {2}, this is called the Euclid-Mullin sequence. See

http://en.wikipedia.org/wiki/Euclid%E2%80%93Mullin_sequence

for some information and further links.

See Problem 6 of

http://math.uga.edu/~pete/NT2009HW1.pdf

for some questions, mostly unsolved, about these sequences. (The link is to the first problem set from an advanced undergraduate course in number theory that I teach periodically at UGA.)

-
Going with what Qiaochu Yuan said about f(x), it follows that we will never get those primes unless we start, even if we don't include multiplicities. Since we're starting with 'n', then we're taking the prime factors of 'n+1', then we're taking the prime factors of f(n+1), then f(f(n+1)), then f(f(f(n+1))) etc, even if we get, say, a 72 in there, our number is [f(f(f(n+1)))] / 7, which then goes into f(x). So no, unless you start with the infinite product $p_1 = \prod_{n=1}^\infty 6n-1$, you will never get any of those numbers.