A slight modification in Chinese Remainder Theorem

44 Views Asked by At

Suppose $m_1, m_2, m_3,\ldots, m_k > 1$ and not necessarily pairwise relatively prime. Also $a_1, a_2,\ldots, a_k\in\Bbb Z$. What can we say about the solutions of the following congruence equations:

$\begin{align*} x&=a_1\mod m_1\\ x&=a_2\mod m_2\\ &\phantom{1}\vdots\\ x&=a_k\mod m_k \end{align*}$

1

There are 1 best solutions below

0
On

What is known is that there exists solutions if and only if $$\forall\,1\le i,j\le k,\qquad a_i\equiv a_j\mod\gcd(m_i,m_j).$$ When these conditions are satisfied, the solution is unique $\bmod\operatorname{lcm}(m_1,m_2,\dots,m_k)$