1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hint: Use the Chinese remainder theorem to split $12$ first, then join them back afterwards. $\endgroup$ – Arthur Nov 6 '16 at 15:52
  • $\begingroup$ 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$. $\endgroup$ – model_checker Nov 6 '16 at 16:05
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – model_checker Nov 6 '16 at 16:09
  • $\begingroup$ @Shrey Aryan Yes, you are correct. See my edited answer. $\endgroup$ – Robert Z Nov 6 '16 at 16:17
3
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.