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.
$\begingroup$
$\endgroup$
9
-
1$\begingroup$ Very simple and nice question $\endgroup$– Konstantinos GaitanasMar 11, 2015 at 19:05
-
$\begingroup$ Thanks, but proving is probably not that simple! :) $\endgroup$– AtvinMar 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$– Ross MillikanMar 11, 2015 at 19:15
-
2$\begingroup$ I like the idea of a prime with an attitude. $\endgroup$– ThéophileMar 11, 2015 at 19:23
-
1$\begingroup$ p=5 works, a has 4 as remainder, but b as 0. $\endgroup$– AtvinMar 11, 2015 at 21:33
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
2
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 $
answered Mar 11, 2015 at 19:54
-
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$– ArthurMar 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