3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Do you know the Chinese Remainder Theorem? $\endgroup$ – Crostul Jul 12 '16 at 10:03
  • $\begingroup$ @Crostul This can only be applied if the $m_i$ are pairwise coprime. What can we do if this is not the case ? $\endgroup$ – Peter Jul 12 '16 at 10:04
  • $\begingroup$ @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. $\endgroup$ – Crostul Jul 12 '16 at 10:27
  • $\begingroup$ 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? $\endgroup$ – Ronteg Jul 12 '16 at 10:31
2
$\begingroup$

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.

$\endgroup$

Your Answer

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

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