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

I practice with some easy tasks and I can't solve one of them. I know that:

$$ a\equiv b \pmod n\\ a\equiv b \pmod{n^\prime}\\ \gcd(n, n^\prime)=1 $$

I need to show that $a\equiv b \pmod{nn^\prime}$.


share|cite|improve this question
up vote 5 down vote accepted

$$a\equiv b \mod n \implies a-b=k_1 n$$

$$a\equiv b \mod n' \implies a-b=k_2 n'$$

for some integers $k_1$,$k_2$. If $k_1 n = a-b =k_2 n'$ and $gcd(n, n')=1$ then $k_1$ is a multiple of $n'$ and $k_2$ is a multiple of $n$, so $a-b = k_3 nn'$ for some integer $k_3=k_1/n'=k_2/n$. And

$$a-b=k_3 nn' \implies a\equiv b \mod nn'. $$

share|cite|improve this answer
How did you deduce that, by Euclid's lemma, unique factorization, properties of gcds or lcms? It is essential to say what properties you use in order to judge if the proof is correct. – Bill Dubuque May 30 '12 at 13:05

Hint $\rm\ \ \ gcd(n',n)=1,\ \ n'\:|\:n\,(a\!-\!b)/n\:\Rightarrow\:n'\:|\:(a\!-\!b)/n\:\Rightarrow\: nn'\:|\:a\!-\!b\ \ $ by Euclid's Lemma.

Alternatively $\rm\:\ n,n'\:|\:a\!-\!b\:\Rightarrow\:lcm(n,n')\:|\:a\!-\!b,\ $ but $\rm\:lcm(n,n')=nn'\ $ if $\rm\ gcd(n,n') = 1.$

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.