Inequality mod p for all primes implies equality.

Question

Let $n$, $m$ positive ($n,m>0$) integers such that $n \le m\bmod{p}$ for all primes $p$, prove that $n=m$. To clarify, the above inequality is taken using the representatives $\{0,1...,p-1\}$ of the class of remainders modulo $p$

Answer 1

We will prove the contrapositive; if $m > n$ (the case $m < n$ is rather trivial), then there is a prime $p$ such that $m \pmod{p} < n \pmod{p}$.

If $m \le 2n$, then one of $n+1, n+2, .., m$, let's say $n+a$, is divisible by a prime $p > m-n$, by Sylvester's Theorem. Then $m \pmod{p} = m-(n+a) < p-a$, while $n \pmod{p}$ either equals $n$ (if $p > n$) or it equals $p-a$ (if $p < n$). Since $n = (n+a) -a \ge p-a$, in both cases we get $m \pmod{p} < p-a \le n \pmod{p}$.

If $m \ge 2n$, then, again by Sylvester's Theorem, one of $m-n+1, m-n+2, .., m$ is divisible by a prime $p > n$. In this case $m \pmod{p} < n = n \pmod{p}$.

There is also a short note here detailing a different, self-contained proof by Szegedy.