# 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

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
• I have posted a separate question mathoverflow.net/questions/84374/… . – Mark Sapir Dec 27 '11 at 13:25

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.

Dear Currie

The below problem is still open:

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 Janbaz Jan 3 '12 at 14:48