# Thread: more gcd

1. ## more gcd

I am stuck on this one too........let m,n be integers such that gcd(m,n)=1. prove that if a equivalent to b mod m and a equivalent to b mod n, then a equivalent to b mod (mn)

thanks

2. Since $\displaystyle a \equiv b \mod m$, we have $\displaystyle m \mid (a-b)$. Similarily $\displaystyle n \mid (a-b)$. Now you probably know that if $\displaystyle s \mid u$, $\displaystyle t \mid u$ and $\displaystyle (s,t)=1$ then $\displaystyle st \mid u$. What do you conclude?

3. ## ?

Originally Posted by Bruno J.
Since $\displaystyle a \equiv b \mod m$, we have $\displaystyle m \mid (a-b)$. Similarily $\displaystyle n \mid (a-b)$. Now you probably know that if $\displaystyle s \mid u$, $\displaystyle t \mid u$ and $\displaystyle (s,t)=1$ then $\displaystyle st \mid u$. What do you conclude?
do you conclude that a is equivalent to b mod (mn)?

4. Ultimately, yes. But do you understand why?

5. Originally Posted by Bruno J.
Ultimately, yes. But do you understand why?
is it because s and t both divide u therefore mn divides a and b

6. Yes!