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

Define the relation $\sim$ on $\mathbb{Z}$ by $a \sim b$ if and only if $5a \equiv 2b \pmod{3}$.

Prove that $\sim$ is an equivalence relation on $\mathbb{Z}$. Identify the distinct equivalence classes on $\mathbb{Z}/\sim$.

How can I prove something like this? Do I need to prove something for reflexiveness, symmetry, and transitivity?


share|cite|improve this question
I'm not sure I understand you correctly, but if i do the answer is yes. Proving that ~ is reflexive, symmetric and transitive is exactly how you should prove this. – WWright Oct 28 '10 at 3:05
Show that $a\sim b$ iff $a\equiv b\pmod 3$. – Mariano Suárez-Alvarez Oct 28 '10 at 3:05
So to prove, say reflexiveness, would I choose a number "a" in Z and prove that "b" could be equal to "a"? – Bradley Barrows Oct 28 '10 at 3:14
reflexive means $a\sim a$ so you need to show that $5a \equiv 2a \pmod{3}$ – WWright Oct 28 '10 at 3:20
@Bradly: have you read Arturo's answer? – Mariano Suárez-Alvarez Oct 28 '10 at 3:20
up vote 6 down vote accepted

Yes, you need to "prove something".

To show that $\sim$ is an equivalence relation, you need to prove that it is reflexive, symmetric, and transitive. That is, you need to prove that:

  1. For every $a\in\mathbb{Z}$, $a\sim a$ is true. Since "$x\sim y$" means "$5x\equiv 2y\pmod{3}$", then that means that you need to prove that for every $a\in\mathbb{Z}$, $5a\equiv 2a\pmod{3}$ is true.
  2. For every $a,b\in\mathbb{Z}$, if $a\sim b$ is true, then $b\sim a$ is true. If you are unsure what this means, then "unpack" the meaning of "$a\sim b$" and of "$b\sim a$" the way I did above.
  3. For every $a,b,c\in\mathbb{Z}$, if $a\sim b$ and $b\sim c$ are both true, then $a\sim c$ is true.

That will prove that $\sim$ is an equivalence relation.

Then you need to think about the equivalence classes. That is, given $a\in\mathbb{Z}$, what is $[a]=\{b\in\mathbb{Z}\mid a\sim b\}$, the set of all integers that are related to $a$? The different sets you get this way are the equivalence classes of $\mathbb{Z}/\sim$.

share|cite|improve this answer

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.