# Conjecture: smallest missing mod value always yields previous prime

I've come up with a conjecture that seems similar in strength to Legendre's or Oppermann's, but maybe subtly different.

Let $$a_n$$ be the smallest nonnegative value such that there is no $$m$$ in $$1 where $$n \equiv a_n \pmod m$$. Then for all $$n>2$$, we have $$n-a_n=p_{\pi(n)-1}$$, the closest previous prime to $$n$$.

Take $$n=16$$ as an example:

$$\begin{eqnarray} 16 &\equiv 0 \pmod 2 \\ &\equiv 1 \pmod 3 \\ &\equiv 0 \pmod 4 \\ &\equiv 1 \pmod 5 \\ &\equiv 4 \pmod 6 \\ &\equiv 2 \pmod 7 \end{eqnarray}$$

The smallest value not seen is $$a_n=3$$, and $$16-3=13$$ is the previous prime. In cases where $$n$$ itself is prime, e.g. $$17$$ yielding the values $$\{1,2,1,2,5,3,1\}$$, you can either interpret $$0$$ as the missing value and $$17$$ as the prime, or $$4$$ giving $$17-4=13$$. (I'm not sure which is the more consistent interpretation.)

I've verified this empirically through $$10^5$$, but cannot come up with a proof. In fact, I suspect a proof would be very difficult since what this seems to come down to is whether there is always a prime in the interval $$(n,n+d)$$ for a composite $$n$$, where $$d$$ is the largest proper divisor of $$n$$. This has its worst case for forms of $$p^2$$, which seem to require a prime in $$\left(p^2, p(p+1)\right)$$.

Note that when $$a_n < \lfloor \sqrt{n} \rfloor$$, it is easily provably true; the problem is you can't guarantee it will be in that range, despite the fact that it almost certainly is for all $$n \geq 127$$.

I'm curious whether this conjecture already exists somewhere or is actually equivalent to one of the better-known prime gap conjectures. Better yet would be a proof, but that's obviously wishful thinking.

• $\pi_n:=\vert\{p: 1<p\leq n, p\in\mathbb{P}\}\vert$ in a lot of programming languages.
– user645636
Nov 29, 2019 at 17:30
• You say $m <n/2$ but in the example $n=16$, you let $\max \{m\}=n/2$. Is the inequality strict or not? Dec 26, 2019 at 0:40
• @MrPie Whoops, fixed. Jan 9, 2020 at 9:37

$$a$$ is the smallest number such that $$n \not\equiv a \mod 2 \dots\frac{n-1}{2}$$.
$$a$$ is the smallest number such that $$n-a \not\equiv 0 \mod 2\dots\frac{n-1}{2}$$.
$$a$$ is the smallest number such that $$n-a$$ is not divisible by $$2\dots\frac{n-1}{2}$$.
$$a$$ is the smallest number such that $$n-a$$ is prime.
$$n-a$$ is the largest prime below $$n$$.
It's incredibly simple. Every composite needs a factor at most half of itself (more accurately its square root). It follows that since half of $$n$$ is greater than half of anything below it, any composite below it will have to have a divisor in the range. The fact you can't shift down any remainder to hit 0 for that number, shows it's prime.
Using the sqrt method, remembering $$m\equiv 0\bmod m$$ we can use $$16\equiv 2\bmod 2$$$$16\equiv 1\bmod 3$$$$\implies 2,3\nmid 16-3$$ and be done. We also only need to check prime moduli.