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

• Very simple and nice question – Konstantinos Gaitanas Mar 11 '15 at 19:05
• Thanks, but proving is probably not that simple! :) – Atvin Mar 11 '15 at 19:11
• @BillDubuque: I would think for all natural $a,b$ such that $a \lt b$, there is a prime $p$ such that $a \pmod p \gt b \pmod p$ – Ross Millikan Mar 11 '15 at 19:15
• I like the idea of a prime with an attitude. – Théophile Mar 11 '15 at 19:23
• p=5 works, a has 4 as remainder, but b as 0. – Atvin Mar 11 '15 at 21:33

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$

• It's not true that the numbers in $[b-a+1,b-1]$ are coprime to $a$, or even that they are divisible by primes that don't divide $a$. For example when $a = 12, b = 24$, the number $18$ is in that interval. – Arthur Mar 11 '15 at 21:22
• @Arthur: Your point is well taken. I just need one to have a prime factor greater than $a$, but need a better argument. – Ross Millikan Mar 11 '15 at 21:29