Conjecture: smallest missing mod value always yields previous prime

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

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.