1
$\begingroup$

prove that if $n>0$ is a positive integer then relation $\equiv_n$ on integers defined by $a\equiv_n b$ if $n\mid (a − b)$ is an equivalence relation. what if $n=2$?

so i know we have to proof reflexivity, symmetry and transitivity.

$\tag 1 a\sim a ?$ $\tag 2 a\sim b \text{ then } b\sim a$ $\tag 3 a\sim b, b\sim c \text{ then } a=c$

but im kind of confused of how to prove it

  • 0
    What have you tried? This is a very straight forward verification of the definitions.2012-10-30

1 Answers 1

2

You are correct that we need to check 1) reflexivity, 2) symmetry, and 3) transitivity. (except note your transitivity should have a (~) not $=$ in the last part)

So lets check these:

1) Fix any $a$. Then $(a - a) = 0$, so $n \mid (a - a)$ and hence $ a \equiv_n a$.

2) Suppose $a \equiv_n b$. Then $n \mid (a-b)$. So we have some $k$ so that $nk = (a-b)$, but then $n(-k) = (b-a)$ and hence $n \mid (b-a)$ so we have $b \equiv_n a$.

3) Suppose $a \equiv_n b$ and $b \equiv_n c$. Then $n \mid (a-b)$ and $n\mid (b-c)$ so we have some $k$ so that $nk = (a-b)$ and $j$ so that $nj = (b-c)$ Then $n(j + k) = nk + nj = (a-b) + (b-c) = a - c$. So $n \mid (a-c)$ and $a \equiv_n c$.

So $\equiv_n$ is an equivalence relation.

  • 0
    @Deven Ware how does the equivalence class is different? is it like a whole set that is compared or what?2012-10-30
  • 0
    @DevenWare what would the equivalence class be when n=3? I am having trouble figuring this out2012-10-30
  • 0
    @JackF Think about when two numbers are equivalent to each other. For $n=3$ this means that $(a-b) = 3k$, or put another way $a = b + 3k$, so $[a] = \{x : x = a + 3k \text{ for some k}\}$, using this you can figure out all the equivalence classes for $n = 3$ (hint: there aren't very many)2012-10-30
  • 0
    @DevenWare how come there is only couple? since a-b have to give 3k so there will be infinitely many solutions2012-10-30
  • 0
    @JackF every number is equivalent to its remainder when divided by $3$, so they're can't be very many equivalence classes! (Since there aren't very many remainders)2012-10-30