# Solve the system of linear congruence.

Problem: Solve $$x\equiv8\pmod {12}$$ $$x\equiv6\pmod {9}$$ Now I have read about the Chinese Remainder Theorem, which is particularily helpful in solving systems of linear congruence, but in this notice that the moduli are not relatively prime (pairwise). So, I cannot apply the theorem. In fact this leads me to a general question: If we are given as system: $$a_1x\equiv b_1\pmod {n_1}$$ $$a_2x\equiv b_2\pmod {n_2}$$ $$a_3x\equiv b_3\pmod {n_3}$$ $$a_4x\equiv b_4\pmod {n_4}$$ $$...$$ $$a_rx\equiv b_r\pmod {n_r}$$ where the moduli are not pairwise relatively prime. How do we go about solving this system and what are the conditions that determine the solvability of the system.

• Hint: Use the Chinese remainder theorem to split $12$ first, then join them back afterwards. – Arthur Nov 6 '16 at 15:52
• Thank you for your reply. I tried splitting $12$ but could not get factors which make all the moduli relatively prime. We could have $4$ and $3$, but then $3$ and $9$ are not relatively prime. Should I solve the system with $4$ and $3$ moduli and then consider another system which includes this solution and the one with modlus $9$. – model_checker Nov 6 '16 at 16:05

Hint. Note that $$x\equiv8\pmod {12}\Rightarrow x=12k+8=4(3k+2) \mbox{ with k\in \mathbb{Z}}\Rightarrow \mbox{x is divisible by 4}$$ In a similar way $$x\equiv 6\pmod {9}\Rightarrow x=9j+6=3(2+3j) \mbox{ with j\in \mathbb{Z}}\Rightarrow \mbox{x is divisible by 3}$$

What may we conclude?

More generally the linear system $$x\equiv a\pmod {m}$$ $$x\equiv b\pmod {n}$$ has a solution iff $\gcd(m,n)$ divides $(a-b)$.

• Ohhh....We may conclude that $x$ is divisble by $12$ since $4$ and $3$ are relatively prime. But $x$ leaves a remainder of $8$ when divided by $12$ and thus we obtain a contradiction. Brilliant! Could you please tell me the necessary and sufficient conditions that determine the solvability of this system. – model_checker Nov 6 '16 at 16:09
• @Shrey Aryan Yes, you are correct. See my edited answer. – Robert Z Nov 6 '16 at 16:17

Hint $\ {\rm mod}\ 3=\gcd(9,12)\$ we have $\,x\equiv 8\equiv 2\,$ by the first, contra $\,x\equiv 6\equiv 0\,$ by the second.

Similarly if $\, x\equiv a\pmod m,\ x\equiv b\pmod n\,$ then $\, a\equiv x\equiv b\pmod d\,$ for $\,d =\gcd(m,n),\$ hence $\,d\mid a-b\,$ is a necessary condition for the existence of a solution.

This compatibility condition is also a sufficient condition for the existence of solution, and it extends pairwise to any number of congruences - see this answer for a constructive proof (which depends on the key fact that gcd distributes over lcm).

This has no solution. From the first it is obvious the $4|x$, from the second however we have $3|x$ , from which we can conclude that $12|x$, but this contradicts the first.