# Necessary and sufficient condition for $x \equiv u_1(mod \ m_1)$, $…$, $x \equiv u_n(mod \ m_n)$ to have a solution [duplicate]

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

• 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/… – Will Jagy May 9 '17 at 17:16
• Try $n=2$ first. – lhf May 9 '17 at 17:43
• 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) – fleablood May 9 '17 at 17:44

## 2 Answers

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

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.