4

$127$ is probably the LAST / LARGEST prime number $p$ such that $p^2\pmod{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\cdot10^{18}$ by Charles R Greathouse(?). Is $127$ the last prime with this property? But WHY ? Is there a reason for this phenomenon?

Thirdy Yabata
  • 558
  • 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 ! – Peter Aug 25 '20 at 12:41

1 Answers1

7

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

Jaap Scherphuis
  • 13,660
  • This explains the astronomical search limit (+1) – Peter Aug 25 '20 at 12:28
  • 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. – Peter Aug 25 '20 at 12:36
  • 5
    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. – Gerry Myerson Aug 25 '20 at 12:49
  • 1
    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) – Ross Presser Aug 25 '20 at 18:06