Let $a$, $b$, $m$ and $n$ be integers with $m > 0$ and $n > 0$. If $(n,m)\mid(a−b)$, then the system

$$\begin{cases} x\equiv a\pmod m \\ x\equiv b\pmod m \end{cases} $$

has a solution. Describe how to find a solution.

Can anyone explain how to solve this for me? I have been looking at it, but I do not know where to begin or what to look for when solving it.

  • $\begingroup$ Welcome to Math.SE! Please consider using Mathjax for mathematics :) $\endgroup$ – Shaun Nov 17 '13 at 18:49
  • $\begingroup$ What is Mathjax? $\endgroup$ – user109496 Nov 17 '13 at 18:50
  • $\begingroup$ Do you know the Chinese Remainder Theorem? $\endgroup$ – Calvin Lin Nov 17 '13 at 18:51
  • $\begingroup$ I have touched base on it, I wouldn't say that I fully grasp it though. $\endgroup$ – user109496 Nov 17 '13 at 18:53
  • $\begingroup$ Is the question how to prove that it has a solution? $\endgroup$ – Michael Hardy Nov 17 '13 at 18:59

The solutions of $x\equiv a\pmod n$ are $x=a+kn$ for any $k\in\Bbb Z$. Similarly, that of $x\equiv b\pmod m$ are $x=b+lm$ with $l\in\Bbb Z$.

By Bezout's identity, we have $u_0,v_0\in\Bbb Z$ such that $(n,m)=u_0n+v_0m$. By the hipothesis, this implies that $$b-a=un+vm$$ for $u=\frac{b-a}{(n,m)}\cdot u_0,\ v=\frac{b-a}{(n,m)}\cdot v_0$. But then consider $$x:=a+un=b-vm\,.$$


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.