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?

  • $\begingroup$ 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$. $\endgroup$
    – almagest
    May 11 '16 at 18:09
  • 1
    $\begingroup$ 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}$. $\endgroup$ May 11 '16 at 18:09
  • 1
    $\begingroup$ 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. $\endgroup$
    – drhab
    May 11 '16 at 18:27
  • $\begingroup$ 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)$. $\endgroup$
    – DylanSp
    May 11 '16 at 18:29

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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.