# Primes and proofs

1) Are there infinitely many primes of the form $a_n$? if $p_1 = 2 < p_2 = 3 <\cdots$ is the sequence of primes then are there infinitely many $n$ for which $p_1p_2\dots p_n + 1$ is prime? For which $p_1p_2\dots p_n - 1$ is prime? Let us determine an infinite sequence of primes by starting with prime $q_1$ and then letting $q_n$ be some prime divisor of $q_1 q_2 \cdots q_{n-1} +1$. Can this be arranged so that the sequence $q_1,q_2,\ldots$ is a re-arrangement of the set of all primes? what if $q_n$ is the smallest prime divisor of $q_1 q_2\cdots q_{n-1} +1$

2) Also, as per Euclid proof for primes, $3 (5) + 1 = 16$ is not prime. How you can say the Euclid proof is great for infinite primes?

Generalize the both questions.

-
If it's homework, please also tag it homework. –  user12205 Oct 2 '11 at 8:53
On (2), while $3\times 5 +1$ is not prime, any prime factor of it is neither $3$ nor $5$, which is the type of result you want for Euclid's proof when you multiply together all primes (assuming there are a finite number) and add $1$. –  Henry Oct 2 '11 at 8:53
As Henry says, Euclid's proof is that $p_1\cdots p_n+1$ is divisible by none of $p_1,p_2,\dots,p_n$, therefore must have a prime factor not among them, hence no finite list of primes can contain them all. I don't know if it's known whether $p\#+1$ (see primorial) is prime infinitely often. I'm not sure if we have theoretical machinery powerful enough to handle any of question (1). (Also, if you're this Gadhi and you want to, you could request your accounts get merged.) –  anon Oct 2 '11 at 9:00
I recommend you to look at the Euclid-Mullin sequence, en.wikipedia.org/wiki/Euclid%E2%80%93Mullin_sequence There you'll see that the second part of pint 1) is not so trivial. –  Josué Tonelli-Cueto Oct 2 '11 at 9:02
Ok. I got it. What about my first question? –  gandhi Oct 2 '11 at 12:03

Do not speak of "infinite primes" unless you mean "primes, each one of which, by itself, is infinite". If you're talking about what Euclid proved, that can be expressed by speaking of "infinitely many primes".

Euclid wrote that if you take any finite set of primes and multiply them and then add 1, then the prime factors of the number you get are not among those you started with. For example $$2\cdot3\cdot5\cdot7\cdot11\cdot13 + 1 = 59\cdot509.$$ The primes we started with were 2, 3, 5, 7, 11, 13; the ones we got were 59 and 509.

Another example: $$5\cdot7+1 = 2\cdot2\cdot3\cdot3.$$ The primes we started with were 5 and 7; the ones we got were 2 and 3.

Another example: $$3\cdot5 + 1 = 2\cdot2\cdot2\cdot2.$$ The primes we started with were 3 and 5; the one we got was 2.

That's was Euclid wrote about: multiply finitely many primes; add 1; factor the result. He said the primes you get will never be among the ones you started with; so you'll always end up with more primes than you started with.

The questions in your first paragraph may require some difficult original research, I think.

-
Thank you very much and I need analysis to my first question of this post. –  gandhi Oct 3 '11 at 5:11
So how many primes are there that are themselves, infinite? :D –  PyRulez Feb 15 '13 at 0:07
@PyRulez : None, among the natural numbers $1,2,3,4,\ldots$. There are some among the non-standard reals. I believe they would form an uncountable set. But they are in internal one-to-one correspondence with the non-standard natural numbers. In other contexts than these two, I don't know. –  Michael Hardy Feb 15 '13 at 12:08
What, there are prime numbers considered infinite! Where do I found out more? –  PyRulez Feb 15 '13 at 14:26
Guy writes $p\#$ for the product of the primes up to $p$, and discusses the primality of $p\#\pm1$ in problem A2 of Unsolved Problems In Number Theory.