Let $n_1$, $n_2$,...$n_k \in N^{+}$ and $c_1,c_2,..c_k \in Z$. Then the system of linear congurences $x\equiv c_i\pmod {n_i}$ for $i=1,2,..k$ has a solution if and only if $\gcd(n_i,n_j)\mid c_i-c_j$.

Suppose it has a solution $y$. Then $y\equiv c_i\pmod {n_i}$ and $y\equiv c_j\pmod {n_j}$. Hence $y=c_i+n_i k_i$. From the second equation we get $c_i+n_ik_i=c_j+n_jk_j$, where $k_i$ and $k_j$ are integers. Then $c_i-c_j=n_jk_j-n_ik_i$. If $d=\gcd(n_i,n_j)$, then $d$ divides the rhs and hence $d$ divides $c_i-c_j$.

Now suppose the $\gcd(n_i,n_j)=d_i$ divides $c_i-c_j$, then $c_i-c_j=d_ie_i$ for some $e_i$ in $Z$. Someway I have to construct a solution which I am uanble to do.

Thanks for the help!!


You have shown that the divisibility condition is necessary. We show it is sufficient, by sketching a proof that if the divisibility condition is satisfied, then there is a solution.

In principle, it is by induction on $k$. We replace the first two $C_1$ and $C_2$ by an equivalent congruence $D_1'$. Then we replace $D_1'$ and $C_3$ by an equivalent congruence $D_2'$. And so on. The only place where we need to actually work is in going from two congruences to one.

So consider the two congruences $x\equiv a\pmod{m}$ and$x\equiv b\pmod{n}$, where $m$ and $n$ are not necessarily relatively prime. We show that if $\gcd(m,n)$ divides $b-a$, then the system has a solution.

Since the $\gcd(m,n)$ divides $b-a$, there exist integers $u$ and $v$ such that $mu+nv=b-a$. Let $c=a+mu$. Then it is clear that $c\equiv a\pmod{m}$. But $c=a+mu=a+(b-a)-nv=b-nv$, so $c\equiv b\pmod{n}$.

So we have shown that the system has a solution $c$. For the induction step, we need a little more, we need to characterize all solutions. Let $\text{lcm}(m,n)=w$. The solution $c$ we have produced is trivially a solution of $x\equiv c\pmod{w}$. We show that any solution $x$ of the system is congruent to $c$ modulo $w$.

Since $c\equiv a\pmod{m}$ and $c\equiv b\pmod{n}$, $x$ is a solution of the system if and only if $x\equiv c\pmod{m}$ and $x\equiv c\pmod{n}$. This is the case if and only if $m$ and $n$ both divide $x-c$. And that is the case if and only if $w$ divides $x-c$.

So we have replaced the two congruences $x\equiv a\pmod{m}$ and $x\equiv b\pmod{n}$ by the equivalent congruence $x\equiv c\pmod{w}$.

  • 1
    $\begingroup$ I think you also have to argue that the condition $\gcd(n_i,n_j)\mid c_i-c_j$ is preserved after replacing the two congruences by one, but that should follow from $\text{lcm}(\gcd(a,m),\gcd(a,n))=\gcd(a,\text{lcm}(m,n))$ for $a,m,n\in\mathbb Z$. $\endgroup$ Sep 5 '14 at 8:37
  • $\begingroup$ Yes, I left out that detail from the description of the induction argument. An alternate way is to separate, not unite. Break up the individual congruences as congruences modulo prime powers. Now go through the highest powers of any prime $p$ that occur in the moduli. The divisibility condition forces consistency, and now we can use ordinary CRT. This is algebraically more natural, since it is more closely tied to direct product decomposition. $\endgroup$ Sep 5 '14 at 8:51

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.