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?

  • 8
    $\begingroup$ 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\}$. $\endgroup$ – François Brunault Dec 26 '11 at 13:30
  • 7
    $\begingroup$ When you say "still open": do you know of anyone asking the question before you? $\endgroup$ – Igor Rivin Dec 26 '11 at 14:54
  • $\begingroup$ 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$? $\endgroup$ – 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.

  • 1
    $\begingroup$ 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)$? $\endgroup$ – Gjergji Zaimi Dec 27 '11 at 2:23
  • 1
    $\begingroup$ 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. $\endgroup$ – Mark Sapir Dec 27 '11 at 2:54
  • 1
    $\begingroup$ 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). $\endgroup$ – Mark Sapir Dec 27 '11 at 3:06
  • 1
    $\begingroup$ I have posted a separate question mathoverflow.net/questions/84374/… . $\endgroup$ – 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.

  • 2
    $\begingroup$ If you're the same JC who posted the question, you might want to ask one of the moderators to merge the two accounts $\endgroup$ – 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) $$


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

  • 1
    $\begingroup$ I don't see why a solution to James Currie's original question would imply a solution to this well known open question $\endgroup$ – Yemon Choi Jan 3 '12 at 4:47
  • $\begingroup$ 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. $\endgroup$ – Shahrooz Janbaz Jan 3 '12 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.