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
    @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