How to show that $(a \sim b \iff n | a−b)$ is an equivalence relation?

Question

Let $n \in \mathbb{Z}$, $n > 0$ be a fixed positive integer.

Define the relation $\sim$ on the set $\mathbb{Z}$ of integers by setting $$ \forall a, b \in\mathbb{Z}\ (a \sim b \iff n | a−b). $$ Show that $\sim$ is an equivalence relation, and determine the cardinality $\#(Z/ \sim)$ of the quotient set $Z/\sim$.

Answer 1

First, $a \sim a$ because $n|0 = a - a$, and $a \sim b \iff b \sim a$ because $n|(a-b) \iff n|(b-a)$, and finally, if $a \sim b, b \sim c$, then $n|(a-b)$, and $n|(b-c)$, then $n|(a-b)+(b-c) = a-c$, thus $a \sim c$. Thus $\sim$ is an equivalence relation on $\mathbb{Z^{+}}$. This means if $a, b\in \mathbb{Z^{+}}$, and $[a] = [b] \iff n|(a-b)$. Consider $0 \leq m \leq n - 1$ and $[m]$. Observe that the classes $[k]$'s with $k \in [0,n-1]$ are distint, and they are the only classes of the quotient set $\mathbb{Z}/\sim$. For if $[p]$ be a class in this set, then $p = qn + r$, with $0 \leq r \leq n-1$. So $n|(n-r)$, and $[p]=[r]$, so $[p]$ is one of the classes mentioned. Thus: $\mathbb{Z}/\sim = \{[0],[1],...,[n-1]\}$, and $|\mathbb{Z}/\sim| = n$

Answer 2

Since you "don't know how to start", I wrote out the first ten steps in some detail. I hope this helps. How far did you get through this list on your own, before you gave up and came here for help?

1. Read the problem. "Show that $\sim$ is an equivalence relation, and . . ."
2. Look up the definition of "equivalence relation": reflexive, symmetric, and transitive.
3. Decide that the first thing to do is prove that the relation $\sim$ is reflexive.
4. Look up the definition of "reflexive": need to show that $a\sim a$.
5. Compare with the definition of $\sim$ given in the problem: need to show that $n|a-a$.
6. Simplify: $a-a=0$, so need to show that $n|0$.
7. Look up definition of $|$: need to show that $\frac0n$ is an integer.
8. Yes, $\frac0n=0$ and $0$ is an integer.
9. Decide that the next thing to do is prove that $\sim$ is symmetric.
10. Look up the definition of symmetric: need to show that $a\sim b\implies b\sim a$.