1
$\begingroup$

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!

2 Answers 2

5

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

  • 0
    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.2012-05-30
0

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