Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Question 1: Let $x,y \in S$ such that $x\sim y$ if $x^2 =y^2\pmod6 $. Show that $\sim$ is an equivalence relation.

This is what I tried:
Reflexive: $x^2\pmod6 = x^2$ implying $x\sim x$
Symmetry: suppose $x\sim y$, then $x^2 =y^2\pmod6$
Operating by inverse of $x^2$ both sides we have $e=(x^2)^{-1} y^2\pmod6$
Then I have $y^2=x^2\pmod6$, hence $y\sim x$
I would like to get some corrections up to here because am not sure with this

Question 2. Find the orbits of the given permutation: $$v:\mathbb{Z}\to\mathbb{Z}\quad\text{ defined by }\quad v(n)=n+3$$

Here is my solution which I would also want somebody to correct me!
Let the relation $\sim$ be defined on $\mathbb{Z}$ by $a\sim b$ if $b=a+3$
I consider that the orbits of $v$ are the classes of $\mathbb{Z}$ with respect to $\sim$ given by $\{b\mid b=a+3\}$. Thus I get only three orbits which are $\{1,4,7,10,…,3n-2\mid n\in \mathbb{Z}\}$, $\{2,5,8,…,3n-1\mid n\in \mathbb{Z}\}$, and $\{3,6,9,…,3n \mid n\in \mathbb{Z}\}$.

share|cite|improve this question
What is $S$? Does x2 mean $x^2$? – lhf Dec 17 '11 at 16:36
Please ask separate questions. – lhf Dec 17 '11 at 16:36
And please try to use latex! – sxd Dec 17 '11 at 16:37
Despite the fact that you correctly write $n \in \mathbb{Z}$, your explanation makes it sound as if the only numbers you are considering are the positive integers. – André Nicolas Dec 17 '11 at 17:06
up vote 2 down vote accepted

Your argument for symmetry of the first relation is flawed, because you do not know that there is such a thing as the inverse of $x$ modulo $6$ (for example, what if $x^2 \equiv 0 \pmod{6}$? ) But you don't have to: if $x^2\equiv y^2\pmod{6}$, then $6|x^2-y^2$, hence $6|y^2-x^2$, so $y^2\equiv x^2\pmod{6}$.

And you are still missing transitivity: if $x^2\equiv y^2\pmod{6}$ and $y^2\equiv z^2\pmod{6}$, why must $x^2\equiv z^2\pmod{6}$? (Hint. Just use the definitions).

share|cite|improve this answer
;thanks sir, do yo mean a divides b by b|a instead of b/a? – neema Dec 17 '11 at 21:08
what about question 2, am i correct? – neema Dec 17 '11 at 21:13
"$a|b$" means "$a$ divides $b$" means "there exists an integer $k$ such that $ak=b$". This is different from $b/a$ which denotes the rational (possibly integer) number you get by actually dividing $b$ by $a$. $a|b$ is a relation between $a$ and $b$; $b/a$ is a number resulting from performing an operation on $a$ and $b$. – Arturo Magidin Dec 18 '11 at 0:16
Question 2 is badly written, because the sets you describe look as if they were finite and start at the least positive integers. It is also false to claim that $\sim$ as you define it is an equivalence relation: it's not reflexive, it's not symmetric, and it's not transitive. So while it is true that there are three orbits, your argument is very confused. – Arturo Magidin Dec 18 '11 at 0:18
:okay..i want to know more, is it possible for the permutation of a given set to have orbits, given that the relation involving a and b is not an equivalent relation? – neema Dec 18 '11 at 14:18

HINT $\ $ Show more generally that if $\rm\ f\::\:S\to T\:$ and $\rm\:\: \equiv\:\: $ is an equivalence relation on $\rm\:T,\:$ then $\rm\ \{\: (x,y)\ :\ f(x)\:\:\equiv\:\: f(y)\:\}\ $ is an equivalence relation on $\rm\:S\:.\:$ This is called the (equivalence) kernel of $\rm\:f\:,\:$ if we view the codomain as the quotient set $\rm\ T/\equiv\:,\: $ which above is $\rm\ \mathbb Z/6\:,\:$ with $\rm\ f(x) = x^2\:.$

See also the more general notions of difference kernels and equalizers, and see this prior question where the fiber viewpoint is mentioned.

share|cite|improve this answer

Hint for #1. Any relation defined via equality of the values of a function is an equivalence relation. More precisely:

If $f:X\to Y$ and $\sim$ is defined on $X$ by $x\sim y$ iff $f(x)= f(y)$, then $\sim$ is an equivalence relation.

Conversely, every equivalence relation arises in this way.

share|cite|improve this answer
Note that to apply this directly requires viewing $\:\mathbb Z/6\:$ as a quotient set, because it uses an equality $\rm\:f(x) = f(y)\:$ vs. a congruence $\rm\:f(x)\equiv f(y)\:.\:$ But even if the OP has not yet learned about quotient sets, they may still comprehend this viewpoint by using congruence instead of equality - see my answer. – Bill Dubuque Dec 17 '11 at 18:51
@Bill, yes, nicely put, thanks. – lhf Dec 17 '11 at 19:28

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.