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.
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.Sign up to join this community
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 $