[Math] Describing A Congruence Class

discrete mathematicsequivalence-relationsrelations

The question is, "Give a description of each of the congruence classes modulo 6."

Well, I began saying that we have a relation, $R$, on the set $Z$, or, $R \subset Z \times Z$, where $x,y \in Z$. The relation would then be $R=\{(x,y)|x \equiv y~(mod~6)\}$

Then, $[n]_6 =\{x \in Z|~x \equiv n~(mod~6)\}$

$[n]_6=\{x \in Z|~6|(x-n)\}$

$[n]_6=\{x \in Z|~k(x-n)=6\}$, where $n \in Z$

As I looked over what I did, I started think that this would not describe all of the congruence classes on modulo 6. Also, what would I say k is? After despairing, I looked at the answer key, and they talked about there only being 6 equivalence classes. Why are there only six of them? It also says that you can describe equivalence classes as one set, how would I do that?

Best Answer

Take any $n \in \mathbb{Z}.$

Then for each such $n$ there is an integer $k$ such that one of the following equations are satisfied. $$n=6k + 0$$ $$n=6k+1$$ $$n=6k+2$$ $$n=6k+3$$ $$n=6k+4$$

$$n=6k+5$$

Can any integer satisfy more than one of the above equalities?

Can any integer NOT satisfy any of of the above equalities?

Then we can describe the equivalence classes of the equivalence relation $\equiv_{6}$ (congruence, mod $6$) as they relate to the division algorithm:

Given any $d \in \mathbb{Z}, d>0$, we know that $\forall n \in \mathbb{Z}$, there exist unique integers $q, r$ such that $n = dq + r$ where $0\leq r< d$.

In this problem, we have the divisor $d = 6$ of a given $n$:

  • $k = q\in \mathbb{Z}$ is the unique corresponding quotient which results when dividing $n$ by $d = 6$, and
  • $r$ is the unique corresponding remainder, $0\le r < d = 6$, left after dividing that $n$ by $6$.

Then the corresponding equivalence classes can be defined in terms of the the remainder $r$:
$$[r]_6 \in \{[0]_6,[1]_6, [2]_6, [3]_6, [4]_6, [5]_6\} \;\text{ where}$$

$$ [0]_6 = \{...,-12,-6,0,6,12,...\}$$ $$[1]_6 = \{...-11,-5,1,7,13,...\}$$ $$[2]_6 = \{...-10,-4,2, 8, 14...\}$$ $$ \vdots$$ $$[5]_6 = \{...-7,-1,5, 11, 17,...\}$$

Related Question