$5 \mid n^2 - m^2$ is an equivalence relation

Question

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.

Answer 1

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$

Answer 2

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.

Answer 3

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.

Answer 4

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