Equivalence Relation with dividing x and y integers
Define $x\sim y$ means 5 divides $(x - y)$ for $x$ and $y$ integers. Show that is an equivalence relation.
Equivalence relation means it satisfies reflexity, symmetry, and transitivity.
reflexive: $x\sim x$ means 5 divides $x$
symmetry: $x \sim y \rightarrow y\sim x$ means 5 divides $x - y$ and 5 divides $y - x$: $$5/(x - y) = 5/(y - x)$$ so symmetry is satisfied.
I am not sure if I am right here and I am lost on how to prove it is transitive any suggestions would be greatly appreciated
The relation $x \sim y \iff 5 | (x-y)$ is an equivalence relation since it is:
Reflexive: $x \sim x$ since $5 | (x -x)$, that is $ 5 | 0$, which is trivially true.
Symmetric: If $x \sim y$ then $(x-y) = 5m$ for some integer $m$. Then $y \sim x$ is true since $5 | (y-x)$ because $y-x = -5m$ for some integer $m$.
Transitive: If we have that $x \sim y$ and $y \sim z$ then we can write those as $x-y = 5m$ and $y-z=5n$ for integers $m$ and $n$. Then $x - 5n - z = 5m$ and hence $x-z = 5m + 5n$ so $5 | (x-z)$ and hence $x \sim z$.
Notice that you need to show each of these steps, though you simply stated them.
Reflexive: $ x\sim x \implies 5|(x -x )$. In fact, $0 = 0 \cdot 5$ then in fact $%$ divides $0$.
Symmetry: $ x \sim y \implies y \sim x$ means that if $5 | (x - y)$ then $$(x-y) = 5\cdot k \implies -(y-x) = 5 \cdot k \implies (y - x) = 5 \cdot (-k)$$
and in fact $5$ divides $(y-x)$.
- Transitivity: $x \sim y$ and $y \sim z \implies x \sim z$. In fact if $5 | (x -y)$ and $5| (y - z)$ then there exist $k, k'$ integers such that
$$(x - y) = 5 \cdot k \ \ \text{and} \ \ (y -z) = 5 \cdot k' \implies x - 5 \cdot k - z = 5 \cdot k' \implies x - z = 5\cdot (k' + k)$$
Conclusion $5 | (x - z)$.
Note that every integer $n$ can be written uniquely as $n=5k+f(n)$ where $k$ is an integer and $f(n)\in\{0,1,2,3,4\}$.
Here $f:\mathbb Z\rightarrow\{0,1,2,3,4\}$ is a well defined function and $x\sim y\iff f(x)=f(y)$.
Based on this it is easy to show that $\sim$ is an equivalence relation:
- $f(x)=f(x)$ (reflexive)
- $f(x)=f(y)\implies f(y)=f(x)$ (symmetric)
- $f(x)=f(y)\wedge f(y)=f(z)\implies f(x)=f(z)$ (transitive)