# Show that $R = \{ (x,y) \in \mathbb{Z} \times \mathbb{Z} : 4 \mid(5x+3y)\}$ is an equivalence relation.

Let $R$ be a relation on $\mathbb{Z}$ defined by $$R = \{ (x,y) \in \mathbb{Z} \times \mathbb{Z} : 4 \mid (5x+3y)\}.$$ Show that $R$ is an equivalence relation.

I'm having a bit of trouble with this exercise in my book and I am trying to study. Can anyone give guidance for this? I know we have to show reflexivity, symmetry, and transitivity, but I don't think what I have on my paper is completely right. I would appreciate other people's opinions on what the solution should be.

This should be easily verified if we realize that $$4|(5x+3y) \quad \Longleftrightarrow \quad 5x+3y \equiv 0 \pmod 4 \quad \Longleftrightarrow \quad x \equiv y \pmod 4.$$
• COuld you exaplin this part ? $\quad 5x+3y \equiv 0 \pmod 4 \quad \Longleftrightarrow \quad x \equiv y \pmod 4.$ – SMath Sep 17 '14 at 6:47
• This is true because $5 \equiv 1 \pmod 4$ and $3 \equiv -1 \pmod 4$. Hence $5x+3y \equiv 0 \pmod 4$ implies that $x - y \equiv 0 \pmod 4$. – E W H Lee Sep 17 '14 at 6:51
Reflexive: $xRx = 5x + 3x = 8x$ which is clearly divisible by $4$ if $x\in\mathbb Z.$
Symmetry: Assume $xRy$, that implies that $5x + 3y$ is divisible by $4$. Then $yRx = 5y + 3x = (9y - 4y) + (15x - 12x) = 9y + 15x - 4y - 12x $$= (3y + 5x)- 4(y + 3x). Since 3y + 5x is divisible by 4 and 4(y + 3x) is divisible by 4, their difference is divisible by 4 too, when x and y are integers. Transitivity: Assume xRy = 5x + 3y and yRz = 5y + 3z. Sum them together and you get the 5x + 8y + 3z, which is divisible by 4 (since you added two terms divisible by 4), so 5x + 8y + 3z - 8y must also be divisible by 4 (because you subtracted a number divisible by 4 from an expression divisible by 4) and there you get the xRz. • You might already know this, but if you write your math between single dollar signs, it comes out a bit better. E.g. \5x+3x=8x\ looks like 5x+3x=8x. – Josh Keneda Sep 17 '14 at 8:24 • Sorry, I'm new to this ... – Flavius Suciu Sep 17 '14 at 10:53 • Oh don't apologize! I just saw that this was your first post and thought the dollar sign thing might come in handy. – Josh Keneda Sep 17 '14 at 11:44 In general, let a and b be integers and m a positive integer. Then,$$R:=\big\{(x,y)\in\mathbb{Z}\times\mathbb{Z}\,|\,ax+by\text{ is divisible by }m\big\}$$is an equivalence relation on$\mathbb{Z}$if and only if$m$divides$a+b$. Furthermore, if$m$divides$a+b$, then the set of equivalence classes of$\mathbb{Z}$under$R$is precisely$\mathbb{Z}/R = \mathbb{Z}/d\mathbb{Z}$(i.e.,$R$is exactly congruence modulo$d$), where$d:=\frac{m}{\gcd(m,a)}=\frac{m}{\gcd(m,b)}$. Though the other answers give a good impression of why$x\sim y\iff 4|(5x+3y)$defines an equivalence relation, it needs to be said that this is not exactly what is asked in the OP. The OP literally asks: Show that$R = \{ (x,y) \in \mathbb{Z} \times \mathbb{Z} : 4 | (5x+3y)\}$is an equivalence relation. Then one should say:$R$is not an equivalence relation.$R$is a set. More precisely,$R$is a subset of the set$\mathbb Z\times \mathbb Z\$. Its definition relies heavily on the equivalence relation mentioned in the first line of this answer, but it is not itself an (equivalence) relation.