Is this olympiad-like question about remainders an open problem?

Question

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

$$x \bmod p \leqslant y \bmod p$$

for each prime number $p$. (Here, $x \bmod p,\; y \bmod 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.

Answer 1

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!!!

Answer 2

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$

Answer 3

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$.

Answer 4

(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