127 is probably the LAST / LARGEST prime number p such that $p^2$ mod q has an odd residue, where q is the previous prime number right before p. I have checked it up to $10^6$ , and it turned out to have been checked up to 4×10^18 by Charles R Greathouse(?). Is 127 the last prime with this property? But WHY ? Is there a reason for this phenomenon?

  • $\begingroup$ I wonder why this has even be posted on Mathematica Stack Exchange because it is not a question about Mathematica but about the evidence for a conjecture and the reason why it might be true. It is well suited here ! $\endgroup$ – Peter Aug 25 at 12:41

Let $q=p-d$, where $d$ is the prime gap between $p$ and the previous prime $q$. Then $p^2-d^2 =(p-d)(p+d) \equiv 0 \bmod q$, so $p^2 \equiv d^2 \bmod q$. If $d^2<q$, then the residue is $d^2$, which is even because prime gaps are even.

The only way to get an odd residue is to have a prime gap $d$ with $d^2>q$. So we need a prime $q$ so that the next prime is greater than $q+\sqrt q$.

In general, the prime gap grows as $\ln q$, so to have one as exceptionally large as $\sqrt q$ is improbable, and I think it gets more improbable for larger $q$.

| cite | improve this answer | |
  • $\begingroup$ This explains the astronomical search limit (+1) $\endgroup$ – Peter Aug 25 at 12:28
  • $\begingroup$ Although $c\cdot \ln(q)$ is not enough for an upper bound of a prime gap no matter how large $c$ is, the prime gaps are probably much smaller than the best known bounds. In particular, the maximum possible value is probably about $\ln(q)^2$ for large enough $q$. So chances are very good that the conjecture is true. $\endgroup$ – Peter Aug 25 at 12:36
  • 5
    $\begingroup$ It's a conjecture of long standing that there's always a prime between consecutive squares, which would imply there's always a prime between $q$ and $q+2\sqrt q$. So this is a little stronger than a notorious unproved conjecture, but it's still much weaker than what people believe to be true. $\endgroup$ – Gerry Myerson Aug 25 at 12:49
  • $\begingroup$ From Prime gap on wikipedia: "As a result, under Oppermann's conjecture – there exists $m$ (probably $m=30$) for which every natural $n > m$ satisfies $g_n <\sqrt p_n$." If I'm reading this correctly, there won't be any gaps as large as $\sqrt p$ after the 30th prime? (If the conjecture is true) $\endgroup$ – Ross Presser Aug 25 at 18:06

Your Answer

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