# Solutions to system of congruences?

Say you have the following:

$x \equiv a \pmod c$ and $x \equiv b \pmod d$, where $a$ and $b$ are known integers, and $c$ and $d$ are known positive integers.

The following claim is made regarding the above:

"When $c$ and $d$ are coprime, any two solutions for $x$ differ by $k(cd)$, where $k$ is some integer."

How does one go about proving this sort of claim? I'd imagine that you can show that any two solutions are congruent $\pmod {cd}$, but I'm not sure how to prove that.

-
If $x$ and $y$ are two different solutions, look at $x-y$. This must be divisible by both $c, d$. Now if they are relatively prime, then... – Macavity Mar 15 '13 at 5:41
With very little more (if you wish), that could be a rather nice answer, @Macavity – DonAntonio Mar 15 '13 at 6:31
OK - will do that in detail. – Macavity Mar 15 '13 at 7:26

Let $x_1, x_2$ be two different solutions which satisfy the congruences. Then we have: $$x_1 - x_2 \equiv a - a \equiv 0 \mod c$$ $$x_1 - x_2 \equiv b - b \equiv 0 \mod d$$
So $c, d$ both divide $x_1 - x_2$. Thus $x_1 - x_2 = mc = nd$ for some integers $m, n$.
But this means $c$ divides $nd$, and as $c$ is relatively prime to $d$, all prime factors of $c$ must divide $n$. So $c$ divides $n$ and we have $n = kc$ for some integer $k$. Substituting back for $nd = kcd$, we also then have $x_1 - x_2 = k(cd)$ as you wanted.