Showing that $x \equiv a \pmod m$ and $x \equiv b \pmod n$ ha s unique solution mod $mn/(m,n)$

Question

I have the following system of congruences

$$\begin{align} x &= a \pmod m \\ x &= b \pmod n. \end{align}$$

I need to prove that this system has unique solution mod $mn/d$ where $d = \gcd(m,n)$ provided that

$$d \mid (b - a).$$

From the first system I have x - a = mq for $q$ $\in Z$ Hence we get $x = mq + a$ . Now put that into the second system and we will get $mq + a = b\pmod n$. $mq = b - a \pmod n$, so this turns into a linear congruence and one can easily prove that solution exist iff $(m,n) | (b - a)$.

Now to get the solution for $q$ we can easily use linear diophantine result for 2 variables so call $q = x$. This mean that the solution is given by x = $x_0$ + n/(m,n)*k for k $\in Z$ So we get x = $x_0$ (mod $n/(m,n)$). I don't get mod $mn/d$.

I know how to proof the rest I just need this little part of someone could clarify that would be great.

Answer 1

I think your renaming $q$ to $x$ is the source of the confusion. You're right that you get a unique solution for $q$ modulo $n/(m,n)$. But $x=mq+a$, and so $x$ is determined uniquely modulo $m\cdot n/(m,n)$—exactly as you want.

Answer 2

You have $mq+a \equiv b\pmod{n} \cdots \color{red}{q} = q_0 + \frac{n}{(m,n)}k$

Next plugin $\color{red}{q}$ into $$\begin{align}x&=m\color{red}{q}+a\\ x&=m\left(q_0 + \frac{n}{(m,n)}k\right)+a\\x&=mq_0 + \frac{mn}{(m,n)}k+a\\x&\equiv mq_0 +a\pmod{\frac{mn}{(m,n)}}\end{align}$$