# Help with intro to number theory question

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.

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