# Proving equivalence classes for a equivalence relation

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?

• We usually write $a=b\bmod n$. You have to show (1) $a=a\bmod n$, (2) if $a=b\mod n$ then $b=a\bmod n$ and (3) if $a=b\bmod n$ and $b=c\bmod n$, then $a=c\bmod n$. May 11 '16 at 18:09
• Can you relate what you know about the case $n=3$ to the concepts "symmetric", "reflexive" and "transitive"? One possible source of your confusion: it's not the classes that enjoy those properties, it's the relation. The classes have other properties: they are disjoint and fill up all of $\mathbb{Z}$. May 11 '16 at 18:09
• If you are asked to prove this equality then it is preassumed allready that the relation $a\sim b$ prescribed by $n|a-b$ is an equivalence relation. In line of the comment of @EthanBolker: no checking of the $3$ mentioned properties (concerning the relation, not the class) is needed then. May 11 '16 at 18:27
• Different values of the variable $n$ give different cases of the relation; the equivalence relation is defined as saying a pair $(a, b)$ is related iff $n \mid (a - b)$. May 11 '16 at 18:29

• $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\}$$
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\}.$$