19
$\begingroup$

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.

$\endgroup$
  • 9
    $\begingroup$ 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. $\endgroup$ – Crostul Apr 14 '15 at 11:07
  • 4
    $\begingroup$ Related. $\endgroup$ – A.P. Apr 14 '15 at 11:45
  • 4
    $\begingroup$ There is no counterexample with $y \le 10000$. $\endgroup$ – Reinstate Monica Apr 14 '15 at 21:51
  • 2
    $\begingroup$ @user17762 It seems that the least non-negative residue is intended. $\endgroup$ – Mark Bennet Apr 15 '15 at 18:36
  • 1
    $\begingroup$ 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? $\endgroup$ – marty cohen Apr 15 '15 at 19:25
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Great, thanks a lot! $\endgroup$ – Tomek Kania Jul 26 '17 at 18:16
3
$\begingroup$

(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

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
-3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This is false, 6 has the same prime factors as 36. $\endgroup$ – jgon Jun 1 '15 at 22:30
  • $\begingroup$ Thank you for the correction! $\endgroup$ – Aulo Jun 1 '15 at 22:33
  • $\begingroup$ 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$. $\endgroup$ – Christopher Jun 1 '15 at 22:39
  • $\begingroup$ "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$. $\endgroup$ – Christopher Jun 2 '15 at 13:09

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.