0
$\begingroup$

How can i find necessary and sufficient condition for this system to have a solution:

$x \equiv u_1(mod \ m_1)$

$...$

$x \equiv u_n(mod \ m_n)$

| cite | improve this question | | | | |
$\endgroup$
  • 2
    $\begingroup$ if the $m_n$ are coprime there is a solution, that is the CRT. If there are some common factors, one needs some consistency conditions. One I did yesterday that needed, and had, some consistency: math.stackexchange.com/questions/2272440/… $\endgroup$ – Will Jagy May 9 '17 at 17:16
  • 1
    $\begingroup$ Try $n=2$ first. $\endgroup$ – lhf May 9 '17 at 17:43
  • $\begingroup$ It's sufficient but not nesc that the m_i be coprime (then you have the CRT). If m_i and m_j are not coprime then it is nesc that u_i - u_j = 0 mod gcd(m_i,m_j) $\endgroup$ – fleablood May 9 '17 at 17:44
1
$\begingroup$

The Chinese remainder theorem states that if the $m_i$ are co-prime a solution will exist.

So it is sufficient that the $m_i$ be co-prime.

If $x \equiv u_i \mod m_i$ and $x \equiv u_j \mod m_j$ and $\gcd(m_i, m_j) = d \ne 1$ then $x = k_im_i + u_i = k_jm_j + u_j$ so $u_i - u_m = d(k_im_i/d - k_jm_i/d)$ so $u_i \equiv u_j \mod d; x \equiv u_i \mod \frac {m_i}d; x\equiv u_j \mod \frac {m_j}d$ which will have a solutions as $\frac {m_i}d$ and $\frac {m_j}d$ are coprime.

So it is necessary and sufficient that if any $m_i, m_j$ are not coprime that $u_j\equiv u_i \mod \gcd(m_i, m_j)$.

| cite | improve this answer | | | | |
$\endgroup$
0
$\begingroup$

Try looking at the proof of the Chinese Remainder Theorem to see how the case when the $m_n$'s are coprime is dealt with and try to make a generalization.

| cite | improve this answer | | | | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.