# Using Chinese Remainder Theorem for two equations with non-coprime moduli

I have

\begin{align} x & \equiv a\mod m \\ x & \equiv b \mod n \end{align}

Normally I would solve for $x$ by doing $(an\cdot \operatorname{inverse}(n,m) + bm\cdot \operatorname{inverse}(m,n)) \bmod mn$ but I am not sure how to modify this for when $m$ and $n$ are not coprime. Assume a solution exists.

• If $m,n$ are not coprime and a solution exists, then the solution is not unique. But you can always reduce to a problem when $m,n$ are coprime by dividing everything through by the HCF of $m,n$. ($m$ and $n$ are divisible by the HCF by definition. If $a$ and $b$ are not divisible by the HCF then there are no solutions.) – John Gowers Mar 25 '13 at 17:54
• Maybe I'm misremembering, but I'm pretty sure that, when solutions exist, they are unique modulo $lcm(m,n)$. – Hurkyl Mar 25 '13 at 17:55
• Is there a general strategy/process? – user2175923 Mar 25 '13 at 18:14
• @donkey: Your final comment is also mistaken: you need $\gcd(a,b) | a-b$, rather than dividing both numbers individually. – Hurkyl Mar 25 '13 at 18:22
• @user: $ag \equiv bg \bmod cg$ if and only if $a \equiv b \bmod c$. (assuming $g \neq 0$) – Hurkyl Mar 25 '13 at 18:22

Assume $m = m_1 d$, $n = n_1 d$ where $m_1$ and $n_1$ are coprime. And $d < min(m,n)$.

$x \equiv a~(\mod m_1 d) \Rightarrow x \equiv a\mod d~(\mod m_1) \qquad\mbox{and}\qquad x\equiv a\mod m_1~(\mod~d)$

Similary, $x \equiv a\mod~d~(\mod{n_1}) ~\mbox{and}~x\equiv a\mod~{n_1}~(\mod d)$. So, we have additional condition of solution existance: $a\mod{m_1} \equiv a\mod{n_1}~(\mod d)$.

Now we compute $x_{n_1, m_1}$ for $n_1$ and $m_1$. Then we have new system:

$x \equiv x_{n_1,m_1}~(\mod n_1m_1)$

$x \equiv a ~(\mod d)$

Notice, $\min(d, n_1m_1) < \min(m,n)$, it is a semi-invariant. So we can solve it recursively.

• Can you provide an example? I am having trouble following all this notation. I'm just after a simple explanation here for what to do (e.g. divide this by gcd of this, solve this, etc) – user2175923 Mar 25 '13 at 18:36
• Also the notation is different from the OP – user2175923 Mar 25 '13 at 18:41
• In my notation $d$ is $\gcd(m,n)$; and $x \mod y$ is a remainder after division of $x$ by $y$. – urandon Mar 25 '13 at 19:19

Hint $\$ A solution exists $\rm\!\iff\! \exists\, j,k\in\Bbb Z\!:\ a+jm = x = b+kn\!\iff\! kn-jm = a\!-\!b.\:$ If so $\rm\:(n,m)\mid a\!-\!b.\:$ Conversely, if $\rm\:(n,m)\mid a\!-\!b\:$ then the Bezout identity $\rm\:xn - ym = (n,m)\:$ scales to a solution $\rm\: kn-jm = a\!-\!b\:$ by multiplying the Bezout identity by $\rm\:(a\!-\!b)/(n,m).$

A solution is unique $\rm\:mod\,\ lcm(m,n),\$ since if $\rm\:x,x'$ are solutions then $$\rm \begin{eqnarray}x'\equiv x\ \ (mod\ m)\\ \rm x'\equiv x\ \ (mod\ n)\ \end{eqnarray}\!\!\iff\! m,n\mid x'\!-\!x\!\iff\! lcm(m,n)\mid x'\!-\!x\!\iff\! x'\!\equiv x\ \ (mod\ lcm(m,n))$$

So we reduce to solving $\rm\ xn - ym = (n,m) =: d,\:$ or $\ \rm x\, \hat n - y\, \hat m\, = 1,\$ for $\rm\ \hat n = n/d,\,\ \hat m = m/d.\$ This is equivalent to $\rm\ mod\ \hat m:\ x\,\hat n\equiv 1,\$ so $\rm\ x\equiv 1/{\hat n},\:$ which exists since $\rm\:(\hat n,\hat m) = 1.$