11
$\begingroup$

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.

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

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 $

$\endgroup$
  • 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 '15 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$ – Ross Millikan Mar 11 '15 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.