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