# When a congruence system can be solved?

How to prove that a congruence system with $n$ equations can be solved if and only if all the equations can be solved two by two?

\begin{cases} x \equiv a_1 \phantom ((mod\phantom mm_1) \\ x \equiv a_2 \phantom ((mod\phantom mm_2) \\ ... \\ x \equiv a_n \phantom ((mod\phantom mm_n) \end{cases}

I know that if $n=2$, the system can be solved if and only if $\gcd(m_1,m_2)\mid a_1-a_2$.

The thesis is: the system is solvable $\Longleftrightarrow$ $\gcd(m_i,m_j)|\mid a_i-a_j$ for all $i\neq j$.

• Do you know the Chinese Remainder Theorem? – Crostul Jul 12 '16 at 10:03
• @Crostul This can only be applied if the $m_i$ are pairwise coprime. What can we do if this is not the case ? – Peter Jul 12 '16 at 10:04
• @Ronteg Assuming you know CRT, you can write every $m_i$ as a product of prime powers. Hence, you can add the hypothesis that all the $m_i$ are actually prime powers. Now, consider those having the largest exponent, and you are done. – Crostul Jul 12 '16 at 10:27
• So I use CRT and I get an equivalent system where I have more equations with $(mod \phantom n{s_{ij}}^{a_{ij}})$ where $s_{ij}$ is a prime factor of $m_i$. And then? – Ronteg Jul 12 '16 at 10:31

Hint $\$ Suppose for induction there is a solution $\,x = a\,$ to the first $\,n\!-\!1\,$ congruences, i.e.

$$a\equiv a_i\!\!\pmod{m_i},\,\ i=1,\ldots n-1\tag{#}$$

Combining the solution with the final congruence we obtain the system

\begin{align} &x \equiv a\! \pmod m,\ \ m = {\rm lcm}(m_1,\ldots m_{n-1})\\ &x\equiv a_n\!\!\!\! \pmod{m_n}\end{align}

You know this is solvable iff $\,(m_n,m)\mid a-a_n.\$ Since gcd distributes over lcm we have

$$(m_n,m) = (m_n,{\rm lcm}(m_1,\ldots m_{n-1}) = {\rm lcm}((m_n,m_1),\ldots,(m_n,m_{n-1})) =: \ell$$

Hence $\ (m_n,m)\mid a-a_n \iff \ell\mid a-a_n\iff (m_n,m_i)\mid a-a_n,\$ for all $\,i \le n-1$

$\ \ (m_n,m_i)\mid m_i\mid a-a_i\,$ since $\,a\,$ is a solution of the first $\,n-1\,$ congruences $\,({\#})$

$\qquad\ \ (m_n,m_i)\mid a_n\!-\!a_i\,$ by hypothesis. Therefore it divides their difference, i.e.

$\qquad\ \ (m_n,m_i)\mid a-a_n = a-a_i -(a_n - a_i).\$ Therefore a solution exists.

Remark $\$ Domains satsifying CRT = Chinese Remainder Theorem are known as Prüfer domains. They are non-Noetherian generalizations of Dedekind domains. Their ubiquity stems from a remarkable confluence of interesting characterizations. See this answer for a couple dozen characterizatons.