4
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.$$

$\endgroup$
  • 1
    $\begingroup$ COuld you exaplin this part ? $ \quad 5x+3y \equiv 0 \pmod 4 \quad \Longleftrightarrow \quad x \equiv y \pmod 4.$ $\endgroup$ – SMath Sep 17 '14 at 6:47
  • 4
    $\begingroup$ 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$. $\endgroup$ – E W H Lee Sep 17 '14 at 6:51
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Josh Keneda Sep 17 '14 at 8:24
  • $\begingroup$ Sorry, I'm new to this ... $\endgroup$ – Flavius Suciu Sep 17 '14 at 10:53
  • $\begingroup$ Oh don't apologize! I just saw that this was your first post and thought the dollar sign thing might come in handy. $\endgroup$ – Josh Keneda Sep 17 '14 at 11:44
1
$\begingroup$

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)}$.

$\endgroup$
1
$\begingroup$

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.

This might seem pedantic, but absolute unambiguous clarity is everything to a mathematician.

$\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.