Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
What have you tried? This is a very straight forward verification of the definitions. – EuYu Oct 30 '12 at 0:24
up vote 2 down vote accepted

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.

share|cite|improve this answer
@Deven Ware how does the equivalence class is different? is it like a whole set that is compared or what? – Jack F Oct 30 '12 at 1:03
@DevenWare what would the equivalence class be when n=3? I am having trouble figuring this out – Jack F Oct 30 '12 at 16:29
@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) – Deven Ware Oct 30 '12 at 16:34
@DevenWare how come there is only couple? since a-b have to give 3k so there will be infinitely many solutions – Jack F Oct 30 '12 at 22:25
@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) – Deven Ware Oct 30 '12 at 22:50

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.