Mod m

[Trumbone]

For the problem if a = b(mod m) and a = b(mod n), prove a = b(mod mn), I know that m and n are relatively prime. So the greatest common divisor of m and n is 1, but I am not sure if this can help me solve hte problem. Any advice?

 

[daon]

a=b(mod m)
a=b(mod n)

so m|(a-b) and n|(a-b)

since m,n are coprime, mn|(a-b).

this is kind of "obvious" because they share no common prime factors. so if mr=ns, m=s and n=r. if you need to prove this, you may use the fundamental theorem of arithmetic or can try writing it as a linear combination: mp+nq=1.