Answer to Question #284246 in Discrete Mathematics for Prasad

Question

Prove that the relation R:{(x,y)|x-y is divisible by 3} is an Equivalence relation.(R is

defined over Z) L2 CO2 10

Answer 1

Let us prove that the relation $R=\{(x,y)|\ x-y\text{ is divisible by 3}\}\subset\Z\times\Z$ is an equivalence relation.

Since $x-x=0$ is divisible by 3 for any $x\in \Z,$ we conclude that $(x,x)\in R$ for any $x\in \Z,$ and hence the relation is reflexive.

Let $(x,y)\in R.$ Then $x-y$ is divisible by 3. It follows that $y-x=-(x-y)$ is also divisible by 3, and thus the relation $R$ is symmetric.

Let $(x,y),(y,z)\in R.$ Then $x-y$ is divisible by 3 and $y-z$ is divisible by 3. It follows that $x-z=(x-y)+(y-z)$ is also divisible by 3, and therefore $(x,z)\in R.$ We conclude that $R$ is a transitive relation.

Therefore, the relation $R=\{(x,y)|\ x-y\text{ is divisible by 3}\}\subset\Z\times\Z$ is an equivalence relation.