# Describing A Congruence Class

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?

-
Given an element in $Z$, its equivalence class is the set of all elements in $Z$ that are related to that particular element. So pick an integer. Can you describe all the integers that are related to that integer? –  Braindead Nov 10 '12 at 22:45
@EMACK: Have the varied answers helped to clarify why there are exactly six equivalence classes? –  amWhy Nov 11 '12 at 17:46
@amWhy Yes, most certainly. Thank you for asking. –  Mack Nov 11 '12 at 17:48

$$[n]_6=\{x\in\Bbb Z:x\equiv n\!\!\!\pmod 6\}=\{x\in\Bbb Z:6\mid x-n\}$$

and actually calculate $[n]_6$ for some values of $n$.

• $[0]_6=\{x\in\Bbb Z:6\mid x-0\}=\{x\in\Bbb Z:6\mid x\}=\{x\in\Bbb Z:x=6k\text{ for some }k\in\Bbb Z\}$; this is just the set of all multiples of $6$, so $[0]_6=\{\dots,-12,-6,0,6,12,\dots\}$.

• $[1]_6=\{x\in\Bbb Z:6\mid x-1\}=\{x\in\Bbb Z:x-1=6k\text{ for some }k\in\Bbb Z\}$; this isn’t quite so nice, but we can rewrite it as $\{x\in\Bbb Z:x=6k+1\text{ for some }k\in\Bbb Z\}$, the set of integers that are one more than a multiple of $6$; these can be described as the integers that leave a remainder of $1$ when divided by $6$, and $[1]_6=\{\dots,-11,-5,1,7,13,\dots\}$.

More generally, if $x$ is any integer, we can write it as $x=6k+r$ for integers $k$ and $r$ such that $0\le r<6$: $r$ is the remainder when $x$ is divided by $6$. Then

\begin{align*} [r]_6&=\{x\in\Bbb Z:6\mid x-r\}\\ &=\{x\in\Bbb Z:x-r=6k\text{ for some }k\in\Bbb Z\}\\ &=\{x\in\Bbb Z:x=6k+r\text{ for some }k\in\Bbb Z\}\\ &=\{6k+r:k\in\Bbb Z\}\; \end{align*}

the set of all integers leaving a remainder of $r$ when divided by $6$. You know that the only possible remainders are $0,1,2,3,4,5$, so you know that this relation splits $\Bbb Z$ into exactly six equivalence classes, $[0]_6,[1]_6,[2]_6,[3]_6,[4]_6$, and $[5]_6$.

-

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

-
Anothe long Tale is here + –  Babak S. Aug 9 '13 at 7:55

You're right, it does not describe all the congruence classes -- due to an error. Namely, notice $\rm\:6\mid x\!-\!n\:$ means $\rm\:6\color{#C00}k = x\!-\!n,\:$ not $\rm\:6 = \color{#C00}k(x\!-\!n).\:$ Recall $\rm\:a\mid b \!\iff\! a\color{#C00}k = b\:$ for some $\rm\:\color{#C00}k\in\Bbb Z.$ Thus $\rm\:x\in [n]_6$ $\!\iff\!$ $\rm\exists k\in \Bbb Z\!:\ x = n + 6k$ $\!\iff\!$ $\rm x\in n + 6\,\Bbb Z = \{\ldots n\!-\!12,\ n\!-\!6,\ n,\ n\!+\!6,\ n\!+\!12,\ldots\}.$

-
And would this describe all of the congruence classes? –  Mack Nov 11 '12 at 17:35
@EMACK Yes, since above $\rm\:n\:$ denotes an arbitrary integer. –  Bill Dubuque Nov 11 '12 at 17:40
Very nice--it's quite succinct. –  Mack Nov 11 '12 at 17:45