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.

  • 1
    $\begingroup$ Very simple and nice question $\endgroup$ Mar 11, 2015 at 19:05
  • $\begingroup$ Thanks, but proving is probably not that simple! :) $\endgroup$
    – Atvin
    Mar 11, 2015 at 19:11
  • 2
    $\begingroup$ @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$ $\endgroup$ Mar 11, 2015 at 19:15
  • 2
    $\begingroup$ I like the idea of a prime with an attitude. $\endgroup$
    – Théophile
    Mar 11, 2015 at 19:23
  • 1
    $\begingroup$ p=5 works, a has 4 as remainder, but b as 0. $\endgroup$
    – Atvin
    Mar 11, 2015 at 21:33

1 Answer 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 $

  • 1
    $\begingroup$ 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. $\endgroup$
    – Arthur
    Mar 11, 2015 at 21:22
  • $\begingroup$ @Arthur: Your point is well taken. I just need one to have a prime factor greater than $a$, but need a better argument. $\endgroup$ Mar 11, 2015 at 21:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .