# equivalence classes

• Dec 11th 2008, 06:37 AM
NidhiS
equivalence classes
Let D be the relation on Z defined as follows:

for all m,n in Z m D n <==> 3|(m^2 - n^2)

1.prove that D is an equivalence relation and
2.describe the distinct equivalence classes of D.

I don't know how to go abt it(Worried)
• Dec 11th 2008, 07:51 AM
TheEmptySet
To be an equivelence relation it must be

Reflexive $\displaystyle a \mathcal{R} a$

Symmetric $\displaystyle a \mathcal{R} b \implies b \mathcal{R} a$
and
Transative if $\displaystyle a \mathcal{R} b \mbox{ and } b \mathcal{R}c \implies a \mathcal{R}c$

Reflexive $\displaystyle n \mathcal{R} n$ yes becuause

$\displaystyle 3|(n^2-n^2) \implies 3|0$

symmetric yes because if $\displaystyle m \mathcal{R} n$

$\displaystyle 3|(m^2-n^2) \implies 3q=(m^2-n^2)$ for some integer q, factoring we get

$\displaystyle 3q=-1(n^2-m^2) \implies 3(-q)=n^2-m^2 \implies 3|(n^2-m^2)$
so $\displaystyle n \mathcal{R}m$

Transative

$\displaystyle a \mathcal{R} b \mbox{ and } b \mathcal{R}c$

$\displaystyle 3q_1=(a^2-b^2),q_1 \in \mathbb{Z}$ and

$\displaystyle 3q_2=(b^2-c^2),q_2 \in \mathbb{Z}$

solving the 2nd for $\displaystyle b^2$ we get

$\displaystyle b^2=3q_2+c^2$ sub this into the first one to get

$\displaystyle 3q_1=[a^2-(3q_2+c^2)] \iff 3q_1=a^2-3q_2-c^2 \iff 3(q_1+q_2)=a^2-c^2$

This tells us that $\displaystyle 3|(a^2-c^2) \implies a\mathcal{R}c$

for part two think graphically. Good luck.
• Dec 11th 2008, 09:57 AM
Soroban
Hello, NidhiS!

I'll do part 1 . . .

Quote:

Let $\displaystyle \mathbb{D}$ be the relation on $\displaystyle Z$ defined as follows:

. . for all $\displaystyle m,n \in Z\!:\;\; m\,\mathbb{D}\,n\;\Longleftrightarrow\;3|(m^2 - n^2)$

1. Prove that $\displaystyle \mathbb{D}$ is an equivalence relation.

Definition: .$\displaystyle m \,\mathbb{D}\,n\:\text{ if and only if }\: m^2-n^2 \:=\:3k\:\text{ for some integer }k.$
. . . . . . . .
(The difference of their squares is a multiple of 3.)

Reflexive: .Is $\displaystyle a\,\mathbb{D}\,a$ ?

. . $\displaystyle a\,\mathbb{D}\,a \;=\;a^2-a^2 \;=\;0 \;=\;3(0)$ . . . Yes!

Symmetric: .$\displaystyle \text{If }a\,\mathbb{D}\,b,\:\text{ does }\:b\,\mathbb{D}\,a$ ?

. . We have: .$\displaystyle a\,\mathbb{D}\,b \quad\Longrightarrow\quad a^2-b^2 \:=\:3k$

. . Then: .$\displaystyle b^2-a^2 \:=\:3(\text{-}k) \quad\Longrightarrow\quad b\,\mathbb{D}\,a$ . . . Yes!

Transitive: .$\displaystyle \text{If }\,a\,\mathbb{D}\,b\,\text{ and }\,b\,\mathbb{D}\,c,\:\text{ does }a\,\mathbb{D}\,c$ ?

. . $\displaystyle \text{We have: }\:\begin{array}{ccc}a^2-b^2 &=&3h \\ b^2-c^2 &=& 3k \end{array}$

. . Add: .$\displaystyle a^2-c^2 \:=\:3(h+k) \quad\Longrightarrow\quad a\,\mathbb{D}\,c$ . . . Yes!

$\displaystyle \mathbb{D}$ is reflexive, symmetric and transitive.

Therefore, $\displaystyle \mathbb{D}$ is an equivalence relation.