I am trying to prove the next statement.

For $r$ different primes such that the product $p_{1}\cdot p_{2}\cdots p_{k}>n^{2}$ and $a,b\in \{-n^{2},...,n^{2}\}$ $a=b \iff \forall r : a \mod p_{r}=b \mod p_{r}$

I made a table to build a numbering system applying mod on the naturals for each prime, I get sequences of numbers that I can put in my table, in such a way that the columns are coordinates and the new elements of my counting system, but I think that this is not a proof at all. I am stuck with this problem and I can't see how to proceed, especially the return.

  • 1
    $\begingroup$ Look at $a-b$. It is divisible by $p_1,p_2,...,p_k$. Since these are different primes, it follows that $a-b$ is divisible by $p_1p_2\dotsm p_k$. Now, $|a-b|\leq 2n^2<2p_1p_2\dotsm p_k$. $\endgroup$
    – plop
    Commented Jun 14, 2021 at 2:54
  • 1
    $\begingroup$ So, it looks like you could still have $a-b=p_1p_2\dotsm p_k$. For example, $k=1$, $p_1=5$, $n=2$, $a=4$ and $b=-1$, seem to satisfy the condition, but $a\neq b$. $\endgroup$
    – plop
    Commented Jun 14, 2021 at 3:00
  • $\begingroup$ I think you need that both $a,b\geq 0$ for the claim to work, so that $|a-b|\leq n^2\lt p_1p_2\cdots p_k$ and you can use the argument given by plop to conclude $a=b$. Otherwise, constructing a counterexample is easy. Consider primes $p_1,\ldots, p_k$ and choose $n$ as the greatest positive integer for which $n^2$ is less than $p_1p_2\cdots p_k$ and take $a=n^2$, $b=n^2-p_1p_2\cdots p_k$ $\endgroup$ Commented Jun 14, 2021 at 3:16
  • $\begingroup$ As an explicit counterexample, consider the primes $2,3,5,7,11$ and $n=\lfloor\sqrt{2\times 3\times 5\times 7\times 11}\rfloor=48$ and $a=48^2$, $b=-6$ $\endgroup$ Commented Jun 14, 2021 at 3:18
  • $\begingroup$ Ok, let me check the assumptions, I did not see that issue $\endgroup$ Commented Jun 14, 2021 at 4:44


You must log in to answer this question.

Browse other questions tagged .