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