In his book ``Topics in number theory, Volumes I and II''. William J. Leveque proved the following theorem(see page 34)

Theorem A necessary and sufficient condition that the system of congruences $x\equiv a_i\bmod m_i$ $(i=1,2,\dots,n)$ be solvable is that for every pair of indices $i,j$ between $1$ and $n$ inclusive, $$\gcd(m_i,m_j)\mid (a_i-a_j).$$ The solution, if it exists, is unique modulo the least common divisor $[m_1,m_2,\dots,m_n]$.

Then he uses this theorem to deduce the Chinese Remainder Theorem.

The following is the proof:

Proof The condition is necessary is obvious. To prove the sufficiency we first consider the homogeneous congruences. The solution of the homogeneous congruent equations $x\equiv 0\bmod m_i$ $(i=1,2,\dots,n)$ is $x\equiv0\bmod[m_1,m_2,\dots,m_n]$. Hence we should find a solution $\delta$ of the original congruences. Then all the integers satisfy the system are given by $\delta+[m_1,m_2,\dots,m_n]\operatorname{Z}$. Consider the case $x\equiv a\bmod m$ and $x\equiv b\bmod n$ with $[m,n]\mid (a-b)$. We show that $$a+[m,n]\operatorname{Z}\cap b+[m,n]\operatorname{Z}=a+m\frac{b-a}{(m,n)}\left(\frac{m}{(m,n)}\right)^{-1}+[m,n]\operatorname{Z}.$$ In fact, assume that $x=a+my\in b+n\operatorname{Z}$, then $my\in b-a+n\operatorname{Z}$ or $my\equiv b-a\bmod n$. Thus $$\frac{m}{(m,n)}y\equiv\frac{b-a}{(m,n)}\bmod\frac{n}{(m,n)}.$$ Hence $$y\equiv\frac{b-a}{(m,n)}\left(\frac{m}{(m,n)}\right)^{-1}\bmod\frac{n}{(m,n)}$$ and $$my\equiv m\frac{b-a}{(m,n)}\left(\frac{m}{(m,n)}\right)^{-1}\bmod\frac{mn}{(m,n)}=[m,n].$$ Thus $$x\equiv a+m\frac{b-a}{(m,n)}\left(\frac{m}{(m,n)}\right)^{-1}\bmod[m,n].$$ Now we prove the theorem. Let $x\equiv\delta\bmod[m,n]$. We show that for $3\leq i\leq n$, $$(m_i,[m_1,m_2])\mid(c_i-\delta).$$ This can easily be seen by considering the exponent $\alpha$ of any prime $p$ which occurs in the prime-power factorization of $(m_i,[m_1,m_2])$. Let the exponent of $p$ in the factorization of $m_j$ be $\beta_j$, for $j=1,2,\dots,i$. Then $p$ occurs in $[m_1,m_2]$ with exponent $\max(\beta_1,\beta_2)$, so that $$\alpha=\min(\beta_i,\max(\beta_1,\beta_2))=\max(\min(\beta_1,\beta_i),\min(\beta_2,\beta_i)).$$ Remember that $c_i-\delta=c_i-c_1+c_1-\delta=c_i-c_2+c_2-\delta$, thus $p^\alpha\mid c_i-\delta$ and the sufficiency of the condition is proved.

Finally, solving the first two congruences simultaneously, we get a solution which is unique $\bmod[m_1,m_2]$; solving this with the third, we get a solution unique $\bmod[m_3,[m_1,m_2]]$, that is, unique $\bmod[m_1,m_2,m_3]$, etc. $\blacksquare$

My Question We know that the Chinese remainder theorem is nothing but $$\operatorname{Z}/m_1\cdots m_n\operatorname{Z}\simeq \operatorname{Z}/m_1\times\cdots\operatorname{Z}/m_n\ \text{if}\ (m_i,m_j)=1\ \text{for all $i\neq j$}$$

Is there a similar theorem when $(m_i,m_j)\neq1$? Or is there an exact sequence such that we can read the theorem from that exact sequence?

We know that William J. Leveque's theorem is equivalent to say that $$\bigcap_{i=1}^na_i+m_i\operatorname{Z}\neq\emptyset$$ if and only if $$(m_i,m_j)\mid(a_i-a_j)$$ for all pairs $1\leq i\neq j\leq n$.

  • $\begingroup$ In general such a homomorphism is surjective $\text{iff}$ the coprimality holds, so you can try stating the theorem in these terms but it won't be useful for solving problems without surjectivity. Additionally I think the most general statement is in terms of arbitrary commutative rings, changing coprime numbers for coprime ideals. $\endgroup$ – GPerez Dec 13 '14 at 12:44
  • $\begingroup$ Is there an exact sequence, maybe has the form $$0\rightarrow A\rightarrow B\rightarrow^{\phi} C$$ and $\phi(b)=0$ in $C$ if and only if $(m_i,m_j)\mid (a_i-a_j)$ $\endgroup$ – HGF Dec 13 '14 at 12:51
  • $\begingroup$ I've not seen a statement like that myself, but maybe one can be devised. I suggest reading this. $\endgroup$ – GPerez Dec 13 '14 at 13:26
  • $\begingroup$ Thank you very much for your help. $\endgroup$ – HGF Dec 13 '14 at 13:59

Your Answer

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

Browse other questions tagged or ask your own question.