24
$\begingroup$

For any positive integer $n$, define $s(n)$ as the smallest positive integer $m$ such that the $n$ distinct numbers $$ (p_1-1)^2,\ (p_2-1)^2,\ \ldots,\ (p_n-1)^2$$ are pairwise incongruent modulo $m$, where $p_k$ denotes the $k$-th prime. It is easy to check that $$s(1) = 1,\ s(2) = 2,\ s(4) = 9\ \text{and}\ s(9) = 25.$$

My recent computation on the values of $s(n)$ led me to formulate the following surprising conjecture.

Conjecture A. For any integer $n>2$ with $n\not=4,9$, we have $s(n)=p_{n+1}$.

This has been verified for $n\le55000$. The conjecture indicates that for every $n=10,11,\ldots$ we can compute the $(n+1)$-th prime $p_{n+1}$ in terms of the first $n$ primes $p_1,\ldots,p_n$. Thus I'd like to view the conjecture as a mysterious recurrence for primes.

Clearly $s(n) \le s(n+1)$ for any positive integer $n$. Note that $s(n)\not= p_k$ for every $k=1,\ldots,n$ since $$(p_k-1)^2 \equiv (p_1-1)^2 = 1\pmod{p_k}.$$ We also have $s(n) \le p_{n+1}$ since $ p_{n+1}$ does not divide $$(p_k-1)^2 - (p_j-1)^2 = (p_k-p_j)(p_k+p_j-2) $$ for any $1\le j<k\le n$. Note that if $p_{n+1}=p_k+p_j-2$ with $1\le j<k\le n$ then we must have $p_j=2$ (as $p_{n+1}$ is odd) and hence $p_k=p_{n+1}$ which is impossible.Thus, we have reduced the conjecture to the following one.

Conjecture B. For any composite number $m > 5$ with $m\not=9,25$, there are distinct primes $p$ and $q$ smaller than $m$ such that $$ (p-1)^2 - (q-1)^2 = (p-q)(p+q-2)\equiv0\pmod m.$$

If $m$ is a positive even number with $m+2 = p+q$ for some distinct primes $p$ and $q$, then $(p-1)^2\equiv (q-1)^2\pmod{m}$. Thus Conjecture B with $m$ even can be explained in the spirit of Goldbach's conjecture. However, I don't have any reasonable explanation for Conjecture B with $m$ odd.

For some related data, one may consult https://oeis.org/A387959 and https://oeis.org/A387947.

QUESTION. Are Conjectures A and B really correct? Any ideas to prove the mysterious recurrence in Conjecture A? Can one provide a reasonable explanation (even not rigorious) for Conjecture B in the case $2\nmid m$?

Your comments (including further check of the conjectural recurrence) are welcome!

Improve this question
$\endgroup$
6
  • 6
    $\begingroup$ While the conjecture is interesting, I am not sure why it is surprising that your conjecture expresses $p_{n+1}$ in terms of $p_1, \ldots, p_n$. After all, the former is the smallest number not divisible by any of the latter. $\endgroup$ Commented Oct 13 at 18:50
  • 1
    $\begingroup$ @Reinstate Monica $s(n)$ is the smallest positive number $m$ not dividing some numbers, while $p_{n+1}$ is the smallest number not divided by previous primes. Please note the difference. $\endgroup$ Commented Oct 14 at 0:04
  • 3
    $\begingroup$ I am not trying to say that your conjecture follows from or otherwise closely relates to my trivial statement about primes. I am merely stating that there is precedent for a prime being determined by some rule applied to previous primes so that aspect alone is not surprising. $\endgroup$ Commented Oct 15 at 0:17
  • 1
    $\begingroup$ Of course, there is a trivial recurrence for primes, e.g., $p_{n+1}$ is the first integer after $p_n$ satisfying the prime definition. I use "the following surprising conjecture" to mean that the conjecture is somewhat surprising. $\endgroup$ Commented Oct 15 at 3:46
  • $\begingroup$ Conjecture A has been verified for $n\le 10^6$ by Nie Chen at the First Middle School of Nanjing via C++. $\endgroup$ Commented Oct 20 at 11:36

1 Answer 1

Reset to default
28
$\begingroup$

If Conjecture B is true, then it will be very hard to prove. If $r>5$ is a prime and $m=r^2$, then Conjecture B says that there exist at least two primes up to $r^2$ which are congruent to $1$ modulo $r$. Even if we assume GRH, we cannot currently guarantee the existence of such a prime. BTW Schinzel conjectured at the end of his famous paper with Sierpiński that the primes up to $n^2$ represent every reduced residue class modulo $n$. GRH implies a slightly weaker upper bound in place of $n^2$, while bolder conjectures (implying the above special case of Conjecture B) also exist in the literature.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.