Suppose that we are given two positive integers $x$ and $y$ such that

$$x \mod p \leqslant y \mod p$$

for each prime number $p$. (Here, $x \mod p,\; y \mod p$ stand for the least non-negative residua.) Does it follow that $x = y$?

The problem is seemingly easy as we have to test $x,y$ against finitely many primes only. However, after several attempts I begin to wonder whether this is an open problem...

Note that it seems to be an open problem whether there is a prime number between a pair of squares (a reference would be appreciated), so the case where $x$ and $y$ are squares themselves is hard enough. However, it may well happen that this doesn't require such an argument.

• Maybe this helps: if $y$ is squarefree, then every prime dividing $y$ divides $x$ as well, so $y|x$. On the other hand, if we take some prime $p\geq x, y$ we get $x \leq y$ so $x=y$. So the result is easy to prove in the case that $y$ is squarefree. – Crostul Apr 14 '15 at 11:07
• – A.P. Apr 14 '15 at 11:45
• There is no counterexample with $y \le 10000$. – Reinstate Monica Apr 14 '15 at 21:51
• @user17762 It seems that the least non-negative residue is intended. – Mark Bennet Apr 15 '15 at 18:36
• How important is it that the p's are the primes? Would them having a certain density be enough? How about the powers of 2? – marty cohen Apr 15 '15 at 19:25

This is a known theorem which is proved in this paper:

a(mod p) ≤ b(mod p) for all Primes p Implies a = b

Authors: P. Erdos, P. P. Palfy and M. Szegedy

The American Mathematical Monthly, Vol. 94, No. 2 (Feb., 1987), pp. 169-170.

Enjoy it!!!

• Great, thanks a lot! – Tomek Kania Jul 26 '17 at 18:16

(This is a comment, but is easier to enter as an answer.)

As Konstantinos Gaitanas pointed out, the result is in

a(mod p) ≤ b(mod p) for all Primes p Implies a = b

Authors: P. Erdos, P. P. Palfy and M. Szegedy

The American Mathematical Monthly, Vol. 94, No. 2 (Feb., 1987), pp. 169-170.

All of Erdos' publications are listed in https://www.renyi.hu/~p_erdos/Erdos.html and any of the papers can be downloaded from links there.

This particular paper is at https://www.renyi.hu/~p_erdos/1987-01.pdf

Some partial results:

By taking a large $p$, we see that $x\le y$. Let $d=y-x$. Assume $y>x$ (so certainly $y\ge 2$). If $p\mid y$ we obtain $x\bmod p\le y\bmod p=0$, hence $p\mid x$ and also $p\mid d$. Especially, $d\ge2$.

Now Let $p$ be a prime dividing $x+1$ (which is $\ge 2$). Then $x\bmod p=p-1$ implies $y\bmod p=p-1$, i.e. $p\mid y+1$. Hence $d$ is divisible by any prime dividing $x+1$. Especially, $d\ge 6$ because $x+1$ and $y$ have no prime in common.

Now let $p$ be any prime dividing $d+1$ (which is $\ge 7$). Then $y+1\bmod p=x\bmod p$ so that we can avoid the contradiction $y\bmod p<x\bmod p$ only by evading to $x\bmod p=0$, $y\bmod p=p-1$.

Now let $p$ be a prime dividing a number between $x$ and $y$, say $(r-1)p\le x<rp\le y$. Then $y-rp\ge y\bmod p\ge x\bmod p=x-(r-1)p$ implies $y\ge x+p$. Thus the $d$ consecutive numbers $x+1,\ldots, y$ are $d$-smooth (have only prime divisors $\le d$). In other words, ${y\choose d}\mid d!^m$ for suitable $m$

Taking any prime number greater than $x$ and $y$ leads to $x\leq y$.

Now, every $p$ dividing $y$ also divides $x$ because then $x \mod p \leq 0$, thus $y=kx$.

For any prime number $p$ such as $x(k-1)<p<kx=y$ we obtain $y\mod p <x$, with the condition that the primes dividing $k$ also divide $x$.

If we can prove there are always primes in such intervals then we have $x=y$.

• This is false, 6 has the same prime factors as 36. – jgon Jun 1 '15 at 22:30
• Thank you for the correction! – Aulo Jun 1 '15 at 22:33
• Two problems: firstly, 6 and 12 have the same prime factors but are not of the form you say; secondly, you seem to be claiming that if $y = x^n$ for $n$ some positive integer then they are a counterexample, this is false too, consider $y = 36$, $x=6$, and $p=7$. – Christopher Jun 1 '15 at 22:39
• "Now, every $p$ dividing $y$ also divides $x$ because then $x\mod p\leq0$, thus $y=kx$." This doesn't follow, consider $x=12$, $y = 18$. "If we can prove there are always primes in such intervals then we have $x=y$." There aren't always such primes, consider $x=2$, $y = 16$. – Christopher Jun 2 '15 at 13:09