4
$\begingroup$

How can I show this is an equivalence relation:

$$ n \operatorname{R} m \Longleftrightarrow n^2 - m^2 \textrm{ is divisible by } 5 $$

I know equivalence relations are symmetric, reflexive and transitive. I'm just not sure how to use this knowledge to prove it.

$\endgroup$
  • $\begingroup$ What does nRm means? $\endgroup$ – moray95 May 30 '13 at 18:55
  • $\begingroup$ It's common shorthand notation for $(n,m)\in R$ $\endgroup$ – Zen May 30 '13 at 18:56
5
$\begingroup$

We need to show that for all integers $x, y, z$, the relation $$R = \{(m, n): m^2 - n^2 \;\;\text{is divisible by 5}\}$$ is reflexive, symmetric, and transitive.

We will use the notation $\;5 \mid m^2 - n^2$ to denote "$m^2 - n^2$ is divisible by $5$."

Let $x, y, z \in\mathbb{Z}$

Reflexive:
We need to show that for any $x \in \mathbb Z$, $x\,R\, x$. Now $x^2-x^2=0$. Since $0$ is divisible by every integer, it is also divisible by 5, so the relation is reflexive.

Symmetric
We need to show that for any $x, y \in \mathbb Z$, if $x\,R\,y$ then $y\,R\,x$. So, suppose $x\,R\,y$. This would mean that $\,5 \mid x^2 - y^2$. Then $\,5 \mid -(x^2-y^2)=y^2-x^2$. So $\,5\mid y^2 - x^2\,$, hence $y\,R\,x$ and the relation $R$ is therefore symmetric.

Transitive
We need to show that if $x\,R\,y\,$ and $\,y\,R\,z\,$, then $x\,R\,z.\,$ So: suppose $x\,R\,y$ and $y\,R\,z$. It follows that $\,5\mid (x^2 - y^2)$ and $\,5\mid y^2 - z^2$. But then $$5 \mid \left[(x^2 - y^2) + (y^2 - z^2)\right] = x^2 - y^2 + y^2 - z^2 = x^2 - z^2.$$ So $5 \mid x^2 - z^2$, which means $x\,R\,y$, and the relation is therefore transitive.

Since our choice of $x, y, z \in \mathbb Z$ was arbitrary, it holds that $R$ is an equivalence relation on the set of integers, since it is reflexive, symmetric, and transitive.

$\endgroup$
  • $\begingroup$ how did this not get any upvotes - not true now! :-) $\endgroup$ – Amzoti May 31 '13 at 0:42
2
$\begingroup$

Recall that the binary relation $ \operatorname{R} $ on $\mathbb{N}^2$ is an equivalence relation iff it is symmetric, reflexive and transitive.

Fix any $n,m\in\mathbb{N}$.

Reflexive ($n \operatorname{R} n$): $n^2-n^2=0$ and $5|0$

Symmetric (if $n \operatorname{R} m$ then $m \operatorname{R} n$): if $5|n^2-m^2=0$ then $5|-(n^2-m^2)=m^2-n^2$

Transitive (if $(n \operatorname{R} m)$ and $(m \operatorname{R} \ell)$ then $n \operatorname{R} \ell$): if $5|n^2-m^2=0$ and $5|m^2-\ell^2=0$ then $5|(n^2-m^2+m^2-\ell^2)=n^2-\ell^2$

$\endgroup$
0
$\begingroup$

I assume your relation is over the set of integers.

Consider arbitrary elements $x, y, z$ in $\mathbb{Z}$. Show that all three equivalence relation properties hold for any such elements.

You could also argue that R is equivalent to (no pun) say $n^2 \equiv m^2 \mod 5$ and since modular congruence is known to be an equivalence relation, R is an equivalence relation.

$\endgroup$
0
$\begingroup$

Given that $xRy$ holds precisely when $x^2-y^2$ is divisible by 5 is exactly the same as saying that $x^2-y^2$ is a multiple of 5; ie $xRy \,\equiv\, (\exists a \in \mathbb{Z} :: x^2-y^2 = 5a)$.

As user Zen said, you could observe the connection between $R$ and mod-equivalence; however, the purpose of the problem may be familiarity with proving/seeing equivalence relations.

As far as I know, transitivity is usually the trickiest to prove and as such I shall try of be of use there. We must show: $xRy, yRz \implies xRz$.

${\bf Proof \; Of \; Transitivity::}$ If $xRy$ and $yRz$, then there are integers $a,b$ with $x^2-y^2=5a$ and $y^2-z^2=5b$. Then we have $(x^2-y^2)+(y^2-z^2)=5a+5b$, that is we have $x^2-z^2=5(a+b)$. Thus we have found an integer $c := a+b$ with $x^2-z^2=5c$ but this means $xRz$ ---as desired.

$\langle\langle$ Notice that the above proof made no use of any properties of the number 5. A nifty exercise would be to show the relation $x \ R_k \ y \;:\equiv\; (\exists a \in \mathbb{Z} :: x^2-y^2 = ka)$ is an equivalence relation, for any given $k \in \mathbb{Z}$.

Challenge: We abstracted away from the number 5, can we abstract away from the operation of subtraction? What about squaring and the multiplication?$\rangle\rangle$

Best regards,

Moses

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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