Let $p$ and $q$ be any two distinct prime numbers and define the relation $aRb$ on integers $a,b$ by: $aRb$ iff $b−a$ is divisible by both $p$ and $q$. For this relation $R$:
(1) Prove that $R$ is an equivalence relation.
(2) Show that the equivalence classes of $R$ correspond to the elements of $\mathbb{Z}_{pq}$. That is: $[a]=[b]$ as equivalence classes of $R$ if and only if $[a]=[b]$ as elements of $\mathbb{Z}_{pq}$.
You may use the following lemma:
If $p$ is prime and $p∣mn$, then $p∣m$ or $p∣n$.
This question is also asked in another topic but it's still unanswered. For me, I proved the first part. But the second part I don't have any ideas. Does anyone know how to prove this? Thanks in advance!
We are trying to prove that $[a]=[b]$ if and only if $a\equiv b \; \text{(mod $pq$)}$. First assume that $[a]=[b]$. Then $a\in [b]$, so $aRb$. Therefore, $a-b$ is divisible by both $p$ and $q$. Since $p$ and $q$ are both prime, and since they are distinct, this implies that $a-b$ is divisible by $pq$ (this is a statement that you should prove as well, if you don't already know why it is true. It is important that $p$ and $q$ are both prime.) Thus $a\equiv b \; \text{(mod $pq$)}$.
For the converse, assume that $a\equiv b \; \text{(mod $pq$)}$. Then $a-b$ is divisible by $pq$. Thus, $p$ and $q$ both divide $a-b$ (this direction is a little easier to prove, and does not require both $p$ and $q$ to be prime. Still, you should make sure you are able to prove this statement by definition of what it means when one number "divides" another.) We conclude that $aRb$ and therefore $[a]=[b]$. (It is true in general that if $R$ is an equivalence relation, then $aRb$ means that $[a]=[b]$. Again, you should make sure you are able to prove this using the properties of equivalence relations and the definition of an equivalence class.)