Number Theory: $a ≡ b$ (mod $p$) and $a ≡ b$ (mod $q$). Show that $a ≡ b$ (mod $pq$). Question says $p$ and $q$ are distinct primes,  $a$ and $b$ integers. What I don't quite grasp (it would be nice if someone could provide a proof) is that why since lcm($p$, $q$) = $pq$ it always follows that $a ≡ b$ (mod $pq$). I mean it makes sense, but I just want a proof.
 A: $a \equiv b \mod p$ means that the difference $a-b$ is divisible by $p$. Similarly, $a \equiv b \mod q$ means that the difference $a-b$ is divisible by $q$. Since $a-b$ is divisible by both $p$ and $q$, it must also be divisible by the least common multiple $lcm(p,q)$ of $p$ and $q$.
A: Well, $ a \equiv b \pmod{p}$ means that $p \mid (a-b)$ or $(a-b)=pk$ for some integer $k$.  Next $ a\equiv b \pmod{q}$ means that $q\mid (a-b) = pk$.  Since $q$ is prime, if it divides a product, it must divide one of the factors.  Since $p$ and $q$ are distinct primes, $q$ doesn't divide $p$, so it must divide $k$, say $k=qm$ for some integer $m$.  Then $a-b = pk = p(qm) = (pq)m$, so $pq\mid (a-b)$ and so $a\equiv b \pmod{pq}$.
A: $a\equiv b\pmod{p}$ means that $a$ is a number of the form $b+kp$ for some integer $k$.
$a\equiv b\pmod{q}$ means that $a$ is a number of the form $b+jq$, too.
Since $\gcd(p,q)=1$, the only integers that are at the same time multiples of $p$ and multiples of $q$ are the multiples of $pq$. So the two previous contraints tell us that $a$ is a number of the form $b+hpq$, that is the same as writing $a\equiv b\pmod{pq}$.
A: The residue classes of $a$ and $b$ in the modulo $p$ ring look like
$$\{\dots,a-p,a,a+p,a+2p,\dots\}$$
$$\{\dots,b-p,b,b+p,b+2p,\dots\}$$
And likewise for $q$. 
So $a \equiv_p b$ iff the difference between $a$ and $b$ is a multiple of $p$. (Because that makes these two sets identical)
Now the residue classes in $pq$ are
$$\{\dots,a-pq,a, a+pq, a+2pq\}$$
$$\{\dots,b-pq,b, b+pq, b+2pq\}$$
And so $a \equiv_{pq} b$ iff the difference between $a$ and $b$ is a multiple of $pq$.
We have that $a \equiv_p b$ and $a \equiv_q b$ which means that the difference between $a$ and between $b$ is a multiple of both $p$ and $q$. This means that it's a multiple of $pq$. Why?
Let the difference $|a-b| = d$. The Fundamental Theorem of Arithmetic says that $d$ has a unique prime factorisation. We know that $p$ and $q$ both divide it, which means that $d = p \cdot q \cdot r$ where $r$ is product of the remaining terms in the factorisation. So whatever the difference $d$ is, it is divisible by $pq$ because $d/(pq) = r$.
