On Euclid's proof of the infinitude of primes and generating primes - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T13:13:59Z http://mathoverflow.net/feeds/question/4917 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/4917/on-euclids-proof-of-the-infinitude-of-primes-and-generating-primes On Euclid's proof of the infinitude of primes and generating primes paarshad 2009-11-10T20:27:04Z 2010-09-13T05:05:51Z <p>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</p> <p>So I was wondering about what kind of primes you get by recursively feeding this process into it self.</p> <p>Since the number you must factor grows exponentially, it's hard to get a lot of numerical evidence for what happens.<br /> I calculated a few:</p> <p>[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</p> <p>[5] (x5)-> [5,2,3,31,7,19,37,3343,79,193662529] -> cannot factor 234069798025176583891</p> <p>Obviously quite a few primes are missing, 5,11,19,etc from the first list, but could show up later.</p> <p>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.</p> http://mathoverflow.net/questions/4917/on-euclids-proof-of-the-infinitude-of-primes-and-generating-primes/4928#4928 Answer by Qiaochu Yuan for On Euclid's proof of the infinitude of primes and generating primes Qiaochu Yuan 2009-11-10T21:23:56Z 2009-11-11T00:42:14Z <p>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 <strong>never</strong> appear (unless they divide $p_1$ to start with.)</p> <p>(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$.)</p> http://mathoverflow.net/questions/4917/on-euclids-proof-of-the-infinitude-of-primes-and-generating-primes/4977#4977 Answer by Pete L. Clark for On Euclid's proof of the infinitude of primes and generating primes Pete L. Clark 2009-11-11T04:03:13Z 2009-11-11T04:03:13Z <p>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.</p> <p>Perhaps the most common variant of your construction is to at each stage not throw in all the prime factors of p<sub>1</sub><em>...</em>p<sub>n</sub> + 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</p> <p><a href="http://en.wikipedia.org/wiki/Euclid%E2%80%93Mullin_sequence" rel="nofollow">http://en.wikipedia.org/wiki/Euclid%E2%80%93Mullin_sequence</a></p> <p>for some information and further links. </p> <p>See Problem 6 of</p> <p><a href="http://math.uga.edu/~pete/NT2009HW1.pdf" rel="nofollow">http://math.uga.edu/~pete/NT2009HW1.pdf</a></p> <p>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.) </p> http://mathoverflow.net/questions/4917/on-euclids-proof-of-the-infinitude-of-primes-and-generating-primes/6692#6692 Answer by Gabriel Benamy for On Euclid's proof of the infinitude of primes and generating primes Gabriel Benamy 2009-11-24T14:35:25Z 2009-11-24T14:35:25Z <p>Going with what Qiaochu Yuan said about f(x), it follows that we will <em>never</em> get those primes unless we start, even if we <em>don't</em> 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<sup>2</sup> 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.<p></p> <p>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.</p>