On Euclid's proof of the infinitude of primes and generating primes - MathOverflow

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

2009-11-10T20:27:04Z

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.

Answer by Qiaochu Yuan for On Euclid's proof of the infinitude of primes and generating primes

2009-11-10T21:23:56Z

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

Answer by Pete L. Clark for On Euclid's proof of the infinitude of primes and generating primes

2009-11-11T04:03:13Z

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 p₁...p_n + 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.)

Answer by Gabriel Benamy for On Euclid's proof of the infinitude of primes and generating primes

2009-11-24T14:35:25Z

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 7² 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.

It's funny, though; I'd had a whole demonstration started to show that you'll never get a multiplicity when taking f(f(...f(2)...)), but this is simpler. As for the Euclid-Mullin sequence, I have no idea.