Proving equivalence classes for a equivalence relation

Question

I am having a bit of trouble trouble understanding how to start problems such as this one. I feel like I am given information that I understand separately but I can't seem to figure out how to they relate.

Let n ∈ Z (integers) be positive. Show that the equivalence relation

n|(a − b)

has equivalence classes

[r] = {kn + r|k ∈ Z}, and 0 ≤ r ≤ n − 1

I know that if let's say n=3 that the classes would be [0]= {3k}, [1]={3k+1}, etc. the variable n is what throws me off. I appreciate any sort of starting points that would help me understand more. I assume I have to show that the class is symmetric, reflexive, and transitive, but how could I show that?

Answer 1

The following statements are equivalent:

• $s\in\left[r\right]$
• $n\mid s-r$
• $\exists k\in\mathbb{Z}\left[s-r=kn\right]$
• $\exists k\in\mathbb{Z}\left[s=kn+r\right]$
• $s\in\left\{ kn+r\mid k\in\mathbb{Z}\right\}$

Check that from top to bottom. Looking at top and bottom we conclude that: $$\left[r\right]=\left\{ kn+r\mid k\in\mathbb{Z}\right\}$$

Answer 2

Let $\equiv$ denote the equivalence relation. By definition, the equivalence class containing $r$ is the set $$\{a \in \Bbb Z \ | \ a \equiv r\}.$$ Now, $a \equiv r$ if and only if $n|(a-r)$, i.e., there exists $k \in \Bbb Z$ such that $kn=a-r$, or in other words $a=kn+r$. This proves that $$\{a \in \Bbb Z \ | \ a \equiv r\}=\{kn + r|k \in \Bbb Z\}.$$