Conjecture: smallest missing mod value always yields previous prime

Question

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<m<n/2$ 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.

Answer 1

The following statements are equivalent:

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

Answer 2

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.