2
$\begingroup$

For $m,n$ in $N$ define $m$ equivalent $n$ if $m^2-n^2$ is multiple of $3$ a) show that this is an equivalence relation b) list elements in equivalence class [0] c) list elements in equivalence class [1] d)do you think there are any more equivalence classes?

for part a i proved that its true by showing through matrix that its symmetric,reflexive and transitive. my problem is that i don't really understand how to find equivalence class, can someone explain how to do it and show on part b or c, rest ill do myself once i get how to do it.

$\endgroup$
  • $\begingroup$ Well, what does it mean for an integer $n$ to be equivalent to $0$? $\endgroup$ – fkraiem Mar 9 '14 at 21:50
  • $\begingroup$ so for above problem for elements in class[0], i need to find elements m,n for which when (m^2)-(n^2) mod 3=0? $\endgroup$ – user2977404 Mar 9 '14 at 22:04
  • $\begingroup$ No. $m$ is equivalent to $n$ if and only if $m^2-n^2$ is a multiple of $3$, or equivalently if and only if $m^2-n^2 \mod 3 = 0$. Now, what does it mean for $n$ to be equivalent to $0$? $\endgroup$ – fkraiem Mar 9 '14 at 22:11
  • $\begingroup$ means n and 0 belong to the same equivalence class $\endgroup$ – user2977404 Mar 9 '14 at 22:55
2
$\begingroup$

There are exactly two equivalence classes:

a. The set of integers divisible by 3, and

b. The set of integers non-divisible by 3.

Clearly, if $3\mid m$ and $3\mid n$, then $3\mid m^2$ and $3\mid n^2$, and hence $3\mid m^2-n^2$.

If $3\not\mid m$ and $3\not\mid n$, then $m^2$ and $n^2$ leave remainder 1, when divided by 3, and hence $3\mid m^2-n^2$.

$\endgroup$
1
$\begingroup$

The equivalence class $[0]$ is the set of all elements related to $0$. We have $m \in \mathbb{N}$ is related to $0$ $\iff m^2 - 0 = m^2$ is a multiple of $3$. Since $3$ is prime, $m \sim 0 \iff m$ is a multiple of $3$. Hence, $[0] = \{3k : k \in \mathbb{N} \}$.

Similarly, $m \sim 1 \iff m^2 - 1 = (m + 1)(m-1)$ is a multiple of $3$, in which case $m \equiv 1, 2 \bmod 3$. So $[1] = \mathbb{N} \setminus 3\mathbb{N}$.

Every positive integer is congruent to $0, 1$, or $2$ modulo $3$, so there are no more equivalence classes.

$\endgroup$

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.