Solvability condition for congruences systems

Question

I know that a congruence system certainly has a solution if $gcd(m_1, m_2) = 1$ $$ \begin{cases} a_1x \equiv b_1\pmod{m_1}\\ a_2x \equiv b_2\pmod{m_2}\\ \end{cases} $$ but there are some systems that are solvable even if this condition does not apply. For example: $$ \begin{cases} 4x \equiv 7\pmod {15}\\ 8x \equiv 11\pmod{21}\\ \end{cases} $$

while in others this does not happen: \begin{cases} x \equiv 1\pmod {10}\\ x \equiv 4\pmod{15}\\ \end{cases} My question is: how do I understand when a system admits a solution?

Answer 1

You are looking at the system $$\left\{ \begin{array}{c} a_{1}x=b_{1}\text{ mod }m_{1}\\ a_{2}x=b_{2}\text{ mod }m_{2} \end{array}\right.$$

First take the simpler system $ax=b\text{ mod }m$. This has a solution for $x$ iff $\left(a,m\right)\vert b$. Try to prove this with Bezout's theorem.

In particular, the original system may lack a solution, even when $\left(m_{1},m_{2}\right)=1$: $$\left\{ \begin{array}{c} 2x=3\text{ mod }6\\ 5x=7\text{ mod }35 \end{array}\right.$$ Each equation separately has no solution.

So $\left(m_1,m_2\right)=1$ is not sufficient, and as you pointed out it isn't necessary either.

The necessary and sufficient condition is that $\left(a_1,m_1\right)\vert b_1$, $\left(a_2,m_2\right)\vert b_2$, and $\left(a_{2}m_{1},a_{1}m_{2}\right)\vert a_{1}b_{2}-a_{2}b_{1}$. Necessity isn't too hard to show. Given the condition holds, Bezout's identity gives $u,v\in \bf{Z}$ such that $ua_{2}m_{1}+va_{1}m_{2}=a_{1}b_{2}-a_{2}b_{1}$. Then the solution is $$x=\frac{b_{1}+um_{1}}{a_{1}}$$

This is a solution as $a_{2}b_{1}+ua_{2}m_{1}=a_{1}b_{2}-va_{1}m_{2}$ which is a multiple of $a_1a_2$ say $a_1a_2x$, then $$a_{1}x=b_{1}+um_{1}$$ $$a_{2}x=b_{2}-vm_{2}$$

Answer 2

Consider the system

$$ \begin{cases} a_1x \equiv b_1 \pmod{m_1} \newline a_2x \equiv b_2 \pmod{m_2} \end{cases} $$

A necessary condition for the system to have a simultaneous solution is that each equation is solvable. This happens precisely when

$$ \gcd(a_i,m_i) \mid b_i, \quad i=1,2. $$

Assuming each condition holds, reduce the system to

$$ \begin{cases} c_1x \equiv d_1 \pmod{n_1} \newline c_2x \equiv d_2 \pmod{n_2} \end{cases} $$

where $\gcd(c_i,n_i)=1$, $i=1,2$, and hence to

$$ x \equiv \begin{cases} e_1 \pmod{n_1} \newline e_2 \pmod{n_2} \end{cases} $$

Now CRT applies provided $\gcd(n_1,n_2)=1$.

If $\gcd(n_1,n_2)>1$, then consider each prime factor common to $n_1,n_2$, to get

$$ x \equiv \begin{cases} e_1 \pmod{p^{r_1}} \newline e_2 \pmod{p^{r_2}} \end{cases} $$

Without loss of generality, if $r_1 \ge r_2$, we must have $x$ congruent to both $e_1$ and $e_2$ modulo $p^{r_2}$. So, there is no solution if $e_1 \not\equiv e_2 \pmod{p^{r_2}}$, and we replace the pair of congruence by the single congruence $x \equiv e_1 \pmod{p^{r_1}}$, which now implies the other congruence.

For each common prime divisor of $n_1$ and $n_2$, we carry out this procedure, stopping if any one of these results in a pair of contradicting congruences. If all pairs of congruences yield a common congruence, we have a new system of congruences modulo distinct prime powers. We are guaranteed a solution by CRT.

To conclude, let us apply all this to the two examples listed in the question.

$\bullet$ Both $4x \equiv 7\pmod{15}$ and $8x \equiv 11\pmod{21}$ are solvable because $\gcd(4,15)=\gcd(8,21)=1$. Multiplying the first congruence by $4$ and the second by $8$ yields the system

$$ x \equiv \begin{cases} 13 \pmod{15} \newline 4 \pmod{21} \end{cases} $$

This is equivalent to the system

$$ x \equiv \begin{cases} 1 \pmod{3}, \; 3 \pmod{5} \newline 1 \pmod{3}, \; 4 \pmod{7} \end{cases} $$

or to

$$ x \equiv \begin{cases} 1 \pmod{3}, \newline 3 \pmod{5} \newline 4 \pmod{7} \end{cases} $$

The CRT ensures a (unique) solution modulo ($3 \cdot 5 \cdot 7$).

$\bullet$ The system

$$ x \equiv \begin{cases} 1 \pmod{10} \newline 4 \pmod{15} \end{cases} $$

is equivalent to the system

$$ x \equiv \begin{cases} 1 \pmod{2}, \; 1 \pmod{5} \newline 1 \pmod{3}, \; 4 \pmod{5} \end{cases} $$

This gives contradictory congruences modulo $5$, thereby yielding no solution.