# Proof of congruency

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}$.

Thanks!

-

$$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'.$$

-
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.$

-