Maybe a stupid question: Let $p_1,p_2,p_3$ be prime numbers and $0\leq x_1<p_2$, $0\leq x_2<p_1$,$0\leq x_3<p_3$. If $x_1$ is fixed, is there exist such $x_2,x_3$ satisfying that $x_1p_1+x_2p_2+x_3p_1p_2=kp_3 \mod p_1p_2p_3$ for some $k$ that $0\leq k<p_1p_2p_3$ ($k$ can be any value as you choose in the domain $0\leq k<p_1p_2p_3$). If so, i further need to know that, if $x_1$ is fixed, are $x_2,x_3,k$ fixed? Let me give a example: let $p_1=2,p_2=3,p_3=5$, then we set $x_1=1,x_2=1,x_3=0$, we have: $1\cdot2+1\cdot3+0\cdot6=5$. I wonder the above solution, i.e., $x_1=1,x_2=1,x_3=0$, when $x_1=1$ is fixed, is unique or not.

If above holds, could anyone give me a simplified proof (or proof sketch)? Thanks very much!


migrated from mathematica.stackexchange.com Jun 10 '16 at 2:22

This question came from our site for users of Wolfram Mathematica.

  • $\begingroup$ You should know, a trivial solution is $x_1=x_2=x_3=k=0$. You may want to add the condition that $x_1 \neq 0$ $\endgroup$ – JasonM Jun 10 '16 at 3:01
  • $\begingroup$ Also posted to (and put on hold at) MO, mathoverflow.net/questions/241800/… $\endgroup$ – Gerry Myerson Jun 10 '16 at 7:15

I assume the $p_i$ are meant to be distinct. Let $y_i$ satisfy $$-x_1p_1 \equiv y_1 \mod p_1$$ $$-x_1p_1 \equiv y_2 \mod p_2$$ $$-x_1p_1 \equiv y_3 \mod p_3 \\$$Clearly $y_1 \equiv 0 \mod p_1$

Denote by $(a^{-1})_b$ the multiplicative inverse of $a \mod b$. Then using the Chinese Remainder Theorem:

$-x_1p_1 \equiv \left[y_2p_1(p_1^{-1})_{p_2}(p_3^{-1})_{p_1p_2}\right]p_3+\left[y_3(p_1p_2)_{p_3}^{-1}\right]p_1p_2 \mod p_1p_2p_3$

Setting $k=-y_2p_1(p_1^{-1})_{p_2}(p_3^{-1})_{p_1p_2}$ and choosing any $x_2$ and $x_3$ satisfying $x_2'+x_3=y_3(p_1p_2)_{p_3}^{-1}$, where $x_2=x_2'p_1$, should solve it.

Here's some more details on how I came up with that construction. $$-x_1p_1 \equiv y_1 \mod p_1$$ $$-x_1p_1 \equiv y_2 \mod p_2$$

implies $$-x_1p_1 \equiv y_1p_2(p_2^{-1})_{p_1}+y_2p_1(p_1^{-1})_{p_2} \mod p_1p_2$$

by the Chinese Remainder Theorem. Thus, $$-x_1p_1 \equiv y_2p_1(p_1^{-1})_{p_2} \mod p_1p_2$$ $$-x_1p_1 \equiv y_3 \mod p_3 $$

so again by the Chinese Remainder Theorem,

$-x_1p_1 \equiv \left[y_2p_1(p_1^{-1})_{p_2}\right]p_3(p_3^{-1})_{p_1p_2}+\left[y_3\right](p_1p_2)(p_1p_2)_{p_3}^{-1} \mod p_1p_2p_3 \Rightarrow $

$-x_1p_1 \equiv \left[y_2p_1(p_1^{-1})_{p_2}(p_3^{-1})_{p_1p_2}\right]p_3+\left[y_3(p_1p_2)_{p_3}^{-1}\right]p_1p_2 \mod p_1p_2p_3 \Rightarrow$

$-x_1p_1 \equiv -kp_3+(x_2'+x_3)p_1p_2 \mod p_1p_2p_3 \Rightarrow$

$kp_3 \equiv x_1p_1+x_2'p_1p_2+x_3p_1p_2 \mod p_1p_2p_3 \Rightarrow$

$kp_3 \equiv x_1p_1+x_2p_2+x_3p_1p_2 \mod p_1p_2p_3$

  • $\begingroup$ Dear JasonM: I am the questioner, and I am not familiar with using the Stack Exchange. It is my pleasure to receive your detailed answer. Thanks very much! Your answer is very interesting. However, I have a little suspect about the unique of the solution. There is a limitation that $0<x_1<p_2,0\leq x_2<p_1$. It seems that you do not use this condition, or I have not fully catch up what you said? If $0<x_1<p_2,0\leq x_2<p_1$ and $x_1$ is fixed, then the solution is unique or not? $\endgroup$ – dengyuqiao Jun 10 '16 at 4:45
  • $\begingroup$ In my last section, it can be taken as $x_2' \equiv x_2\pm p_1p_3 \mod p_2$, $x_3' \equiv x_3 \pm p_3 \mod p_1p_2$, and $k' \equiv k \pm p_1p_2 \mod p_3$. That should fix your concern. $\endgroup$ – JasonM Jun 10 '16 at 4:58
  • $\begingroup$ Also, if you'd be so kind to accept my answer, it would be greatly appreciated. It's the star under the arrows near the top of my comment. $\endgroup$ – JasonM Jun 10 '16 at 5:12
  • $\begingroup$ Dear JasonM: Thanks very much again! However, if $x'_2=x_2\pm p_1p_3$ as you said, how can you guarantee that this "$x'_2$ family" have more than one $x'_2$ in the domain of [0,p_1)? e.g., let $x_2=2,p_1=5,p_3=7$ , it seems that only $x_2=2$ can be the unique solution in the domain $[0,4)$... $\endgroup$ – dengyuqiao Jun 10 '16 at 5:14
  • $\begingroup$ The only way $k' \equiv k \mod p_2$ is if $p_1p_3 \equiv 0 \mod p_2$, which since I assumed these primes are distinct, this cannot happen $\endgroup$ – JasonM Jun 10 '16 at 5:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy