# A mysterious prime number 127

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?

• 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 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, 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$$.
• 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 at 12:36
• 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 at 12:49
• 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 at 18:06