1

Define the following $R$ on the set of integers $\Bbb{Z}$

$(a,b) \in R$ if and only if $3a + 5b$ is divisible by $8$

Prove that $R$ is an equivalence relation.

Attempt:

Reflexive:

a~a if and only if $3a+5a$ is divisible by 8

Since $3a+5a = 8a$ is divisible by 8, the relationship is reflexive.

Symmetry:

Let $a,b,k \in \Bbb{Z} $

$aRb$ = $ 3a+5b = 8k$

$bRa$ = $ 5b + 3a = 8k$

Therefore, it's symmetric

Transitivity:

Let $a,b,c, i, k \in \Bbb{Z} $

$aRb$ = $ 3a+5b = 8i$

$bRc$ = $ 5b + 3c = 8k$

Now what?

drhab
  • 151,093
John
  • 99
  • 1
  • 6
  • 2
    Symmetry isn't proved. $a\mathrel{R}b$ means $8 \mid 3a+5b$ (as you said), but $b\mathrel{R}a$ means $8 \mid 3b + 5a$. – Pece Dec 07 '13 at 07:20

4 Answers4

3

The proof of symmetry is not correct. You are given that $3a+5b$ is a multiple of $8$. You need to show that $3b+5a$ is a multiple of $8$.

Note that $(3a+5b)+(3b+5a)=8(a+b)$. So if $3a+5b=8k$, then $3b+5a=8(a+b)-8k$. The right side is clearly divisible by $8$.

For transitivity, it's your turn. You need to show that if $3a+5b$ is divisible by $8$, and $3b+5c$ is divisible by $8$, then $3a+5c$ is divisible by $8$. Hint: add.

Another way: The following is a slightly more conceptual way of looking at things. Note that $3a+5b=3a-3b+8b$. So $3a+5b$ is divisible by $8$ if and only if $3a-3b$ is divisible by $8$. Now verifying we have an equivalence relation is much easier. For example, for symmetry, it is clear that if $3a-3b$ is divisible by $8$, then $3b-3a$ is divisible by $8$.

André Nicolas
  • 507,029
1

If $f:X\rightarrow Y$ is a function then the relation $\sim$ defined by $a\sim b\iff f\left(a\right)=f\left(b\right)$ is automatically an equivalence relation on $X$. This is easy to verify.

In your case we have:

$aRb\iff8\mid3a+5b\iff8\mid3a-3b\iff8\mid3\left(a-b\right)\iff8\mid a-b\iff\nu\left(a\right)=\nu\left(b\right)$

where $\nu$ is the (natural) function $\nu:\mathbb{Z}\rightarrow\mathbb{Z}/8\mathbb{Z}$ defined by $a\mapsto a+8\mathbb{Z}$.

Proved is now that $R$ is an equivalence relation.

drhab
  • 151,093
0

Now, well, you want to show transitivity. Your beginning is not correct, So suppose $aRb$ and $bRC$. We want to show $aRc$. We have

$ 3a + 5b = 8i $ and $3b + 5c= 8j$. Notice $ 3b = 8j - 5c = 8i - 3a - 2b $

$$\therefore 3a - 5c = 8i - 8j - 2b \implies 3a + 5c = 8i - 8j -2b + 10c$$

$$ \implies 3a + 5c = 8i - 8j -2b + (8j - 6b) =8i - 8b = 8(i - b)$$

Hence, $aRc$

ILoveMath
  • 10,694
  • I'm sorry, but I can't see why 8j−5c=8i−3a−2b. – Edward.Lin Jun 08 '21 at 17:19
  • Better do it like this $3a+5c=(8i-5b)+(8j-3b)=8i+8j-(5+3)b=8(i+j-b)$ your result is erroneous, but the conclusion stands. – zwim Jun 08 '21 at 18:56
  • $3b + 5c = 8j$ so $3b = 8j - 5c$. And $3a+5b = 8i$ so $3b = 8i -3a-2b$. So $8j-5c=8i-3a-2b$. But there is a typo further that no-one caught for 8 years. $10c = 16j -6b$ and not $8j -6b$. ... However $(3a+5b) + (3b + 5c) = 8i + 8j \implies 3a +8b + 5c = 8i+8j \implies 3a + 5c = 8i +8j -8b$ is clearly much easier, isn't it. – fleablood Jun 08 '21 at 19:18
0

This problem is easier if you note:

$$aRb \equiv 3a + 5b = 0 \equiv 3a = -5b \equiv 3a = 3b \equiv a = b \pmod 8$$

Transitive: $$ aRa $$ $$ a = a \pmod 8 $$

Reflexive $$ aRb \equiv bRa$$ $$ a = b \equiv b = a \pmod 8$$

Transitive $$ \left( aRb \land bRc \right) \equiv aRc $$ $$ \left( a = b \land b = c \right) \equiv a = c \pmod 8 $$

DanielV
  • 23,556