# proof of a property of modular arithmetic

I have been stuck in a problem related to modular arithmetic. I have tried it using the generalized Euler's formula for $\gcd(a,b)=as+bt$, but have not reached the proof so far.

The question is:

Let $a, b, n, n'$ all belong to integers($\mathbb Z$) with $n > 0 > , n' > 0$ and $\gcd(n, n') = 1$. Show that if $a \equiv b \mod n$ and $a \equiv b \mod {n'}$ then $a \equiv b \mod {nn'}$.

If $a \equiv b \mod n$ and $a \equiv b \mod n^\prime$, then there are integers $k$ and $k^\prime$ such that $kn = a - b = k^\prime n^\prime$. If $kn = k^\prime n^\prime$ and $(n,n^\prime) = 1$, then what is $(n,k^\prime)$?
• They aren't necessarily equal, but $n^\prime | k$ and $n | k^\prime$. So $a - b = mnn^\prime$, so what is $a - b \mod nn^\prime$? – Michael Biro Nov 24 '14 at 1:39