Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
What have you tried? –  lhf May 30 '12 at 11:26
add comment

2 Answers

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|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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.