0

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.

Julio César JX
  • 1
  • 2
  • 1
    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$. – plop Jun 14 '21 at 02:54
  • 1
    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$. – plop Jun 14 '21 at 03:00
  • 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$ – Prasun Biswas Jun 14 '21 at 03:16
  • 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$ – Prasun Biswas Jun 14 '21 at 03:18
  • Ok, let me check the assumptions, I did not see that issue – Julio César JX Jun 14 '21 at 04:44
  • Thanks a lot, both of you; what a simple and nice proof. I need a lot of training – Julio César JX Jun 14 '21 at 06:06

0 Answers0