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.

  • $\begingroup$ 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.) $\endgroup$ – John Gowers Mar 25 '13 at 17:54
  • $\begingroup$ Maybe I'm misremembering, but I'm pretty sure that, when solutions exist, they are unique modulo $lcm(m,n)$. $\endgroup$ – Hurkyl Mar 25 '13 at 17:55
  • $\begingroup$ Is there a general strategy/process? $\endgroup$ – user2175923 Mar 25 '13 at 18:14
  • 2
    $\begingroup$ @donkey: Your final comment is also mistaken: you need $\gcd(a,b) | a-b$, rather than dividing both numbers individually. $\endgroup$ – Hurkyl Mar 25 '13 at 18:22
  • 1
    $\begingroup$ @user: $ag \equiv bg \bmod cg$ if and only if $a \equiv b \bmod c$. (assuming $g \neq 0$) $\endgroup$ – 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.

  • $\begingroup$ 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) $\endgroup$ – user2175923 Mar 25 '13 at 18:36
  • $\begingroup$ Also the notation is different from the OP $\endgroup$ – user2175923 Mar 25 '13 at 18:41
  • $\begingroup$ In my notation $d$ is $\gcd(m,n)$; and $x \mod y$ is a remainder after division of $x$ by $y$. $\endgroup$ – 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.$


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.