# Generalizing Euclid's proof of the infinity of primes

Is the following problem still open? Let $S$ be a non-empty set of prime numbers such that whenever $p,q\in S$, all the prime factors of $pq+1$ are also elements of $S$. Is $S$ infinite?

-
If one replaces "all the prime factors" by the weaker condition "some prime factor" then the answer is no, an example is given by $\{2,5,11,23,47\}$. –  François Brunault Dec 26 '11 at 13:30
When you say "still open": do you know of anyone asking the question before you? –  Igor Rivin Dec 26 '11 at 14:54
It appears that $S$ is infinite, even when we restrict to the case $p=q$. Why did you focus on two elements of $S$? Is the result known if we allow some fixed number of elements of $S$? –  Pace Nielsen Jan 2 '12 at 18:52

Do we have infinite prime number of the form $2p+1$, where $p$ is prime?
One of interesting way to examine this problem is %Sandram$table. For further information about Sandram table, you can see the book " Ingenuity in Mathematics" by Ross Hansberger Also, with some calculation and using the Jacobi symbol, you will find this problem is equivalent to this problem: The polynomial$n^2+n-1$generate infinite prime number, that it is open problem. You can find some further information about this question in the Richard Guy's book with name: " Open problem in number theory". So I think your problem is a kind of open problem. - I don't see why a solution to James Currie's original question would imply a solution to this well known open question – Yemon Choi Jan 3 '12 at 4:47 Dear Choi, It is possible that we construct a sandram-like table that is equivalent to the original question in this post. I saw this problem when I was in India and some people worked on this problem. I don't know that they published their works or not. – Shahrooz Jan 3 '12 at 14:48 This was given as a problem in one of the MAA journals in the 1980's as a double-starred problem (no solution provided). I met it as a challenge problem on an assignment in John Poland's (Carleton University) modern algebra course. I worked on it for a few months, observing as Mark Sapir does that such a set contains 2, 5, 11, etc. - If you're the same JC who posted the question, you might want to ask one of the moderators to merge the two accounts – Yemon Choi Jan 2 '12 at 19:31 Not claiming to be a real number theorist or anything of that sort...Just wondering, is one possible approach to Mark Sapir's strong conjecture (assuming an answer isn't already known) to calculate $$\sum_{\substack{r,s < q\\ q| rs+1}}\Lambda(r)\Lambda(s)$$ by $$\int_0^1 \left(\sum_{r,s < q}\Lambda(r)\Lambda(s)e((rs+1)\alpha)\right)\left(\sum_{m <q}e(-qm \alpha)\right)d\alpha$$ where$e(x) = e^{2 \pi i x}$and then apply the circle method? If it can't be solved in this manner, perhaps it can still be made equivalent to a conjecture on some error terms. - The answer is most probably "It is always the set of all prime numbers or empty". Indeed, assume that$S$is not empty. First of all,$S$must contain$2$(if it contains$p>2$, then$p^2+1$is even). Then it also contains$2\cdot 2+1=5, 2\cdot 5+1=11, 7\mid 5\cdot 11+1, 3\mid 2\cdot 7+1,$etc. It looks like then$S$contains all prime numbers. I cannot prove it yet, but the proof should not be that difficult. Update Here is a stronger conjecture. Let$S$be the set of all primes from$2$to$p>17$. Let$q$be the next prime after$p$. Then$q$divides$rs+1$for some$r,s\in S$. This of course implies the statement above. I wonder if my conjecture is already known. I checked it for all$p<100,000$. I stop checking and will wait for an opinion of a real number theorist. - I wonder if this is known, it is related to your strong conjecture, let$q$be a large prime, let$A$be the set of primes less than$q$as a subset of$\mathbb Z/q\mathbb Z$and let$B$be the set of their inverses. is the sumset$A+B$large? Can we prove that it is of size$O(q)$? – Gjergji Zaimi Dec 27 '11 at 2:23 That is a question for Green and Tao:) The density of$A$is small, unfortunately, and so is the density of$B$. But I am not a specialist. I still think that my question has a chance to be less of a monster than, say, Goldbach's conjecture because it is about products, not sums. But I may be too naive. – Mark Sapir Dec 27 '11 at 2:54 Actually we need to show that$A\cdot A$contains$-1$. So the question is how large$A\cdot A\$ is. I think there were results like that for cyclic groups (and recently even for nilpotent groups). –  Mark Sapir Dec 27 '11 at 3:06