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.
Best Answer
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$.)