$ 0 < a < b\,\Rightarrow\, b\bmod p\, <\, a\bmod p\ $ for some prime $p$

If $\,a < b\,$ are natural numbers then a prime $\,p\,$ exists such that $\ a\bmod p\, >\, b\bmod p.$

The task seems understandable, but I have no idea how to prove this statement.

Solution 1:

If there is some prime that divides $b$ and not $a$, that prime $p$ will have $a \pmod p \gt 0, b \pmod p = 0$.

Assuming that all factors of $a$ also divide $b$:

If $a=2$ there is some odd prime $p$ that divides $b-1$ and $a \pmod p = 2 \gt b\pmod p = 1$

If $a=3$ there is some odd prime $p$ that divides either $b-2$ or $b-1$ and $a \pmod p = 3 \gt b\pmod p $

If $a = 4$, one of $b-1, b-3$ must have a prime factor $p$ greater than $3$ as they cannot both be powers of three. We have $a \pmod p=4 \gt b \pmod p$

If $a \ge 5$, consider the interval $[b-a+1,b-1]$ It consists of $a-1$. As there are less than $a-1$ primes less than $a$, one of these numbers will have a prime factor $p$ greater than $a$. I haven't justified this, but the idea is that not enough of them can only have factors smaller than $a$. We will have $a \pmod p = a \gt b\pmod p $