Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.