0

Let $\sim$ and $\approx$ be relations on $\mathbb Z$ defined as follows: $$\text{For } a, b \in \mathbb Z, a\sim b\text{ if and only if } 2a+3b\equiv0\pmod5$$

$$\text{For } a, b \in \mathbb Z, a\approx b \text{ if and only if } a+3b\equiv0\pmod5$$

a) Is $\sim$ an equivalence relation on $\mathbb Z$? If not, is this relation reflexive, symmetric, or transitive?

b) Is $\approx$ an equivalence relation on $\mathbb Z$? If not, is this relation reflexive, symmetric, or transitive?

I tried to work on part a, I'm just having trouble showing if it's transitive or not. I think that it is an equivalence relation, it appears to be reflexive and symmetric.

For part b, I just don't know how you "use" the $\approx$ notation in this case, we were not taught this in class.

kimchi lover
  • 24,277
Claire
  • 167
  • $\approx$ is just the same as ~. They just wanted to use a different notation because they already used ~ in part a – Ovi Nov 15 '18 at 02:54
  • 1
    $\approx$ is just notation, it works exactly the same way notationally as $\sim$, so if you understood that you're fine. Try showing that the first condition is equivalent to $a \equiv b \bmod 5$. – Qiaochu Yuan Nov 15 '18 at 02:55
  • it's not equivalent though, is it? I found that it's equivalent to $a \equiv -4b \pmod 5$ – Claire Nov 15 '18 at 03:01
  • @Claire Good. Now $-4 \equiv 1 \pmod 5$ – Ovi Nov 15 '18 at 03:03
  • @Claire By the way, if you want the person to be notified of your comment, you have to use "@theirname" – Ovi Nov 15 '18 at 03:04
  • The second one is equivalent to $a\equiv-3b\equiv2b$, which is not reflexive, because $a\not\equiv2a$ in general. – mr_e_man Nov 15 '18 at 03:18
  • Yeah, i was able to figure that part out. It's not an equivalence relation because, for example, $(4, 4) \notin R$ because $4+12=16$ and $16 \neq 5n$ where $n \in \mathbb Z$ @mr_e_man – Claire Nov 15 '18 at 03:20

1 Answers1

1

One thing that jumps out is that we are working in $\pmod 5$, and it just happens that $2+3=5$. Let's keep that in mind for now.

To show transitivity, we assume

Assume $a$ ~ $b$ and $b$ ~ $c$. Thus we assume that

$$2a+3b \equiv 0 \pmod 5$$

and

$$2b+3c \equiv 0 \pmod 5$$

We want to be able to conclude that $2a+3c \equiv 0 \pmod 5$.

Now what is the first way that comes to mind if we want $a$ and $c$ to show up in the same congruence relation? Well to add the relations we already have. This gives

$$2a+5b + 3c \equiv 0 \pmod 5$$

But $5 \equiv 0 \pmod 5$, so $5b \cong 0 \cdot b = 0 \pmod 5$, so we have

$$2a + 3c \equiv 0 \pmod 5$$

as we wanted.

EDIT:

This is the way it works with congruence relations:

You can prove the following facts (we take them for granted with usual equality, but you have to prove them for congruence):

$(1)$ If $a \equiv b \pmod n$, and $c \equiv d \pmod n$ then $a+c \equiv b+d \pmod n$ (moral: you can add two congruences together)

$(2)$ If $a \equiv b \pmod n$, then $ac \equiv bc \pmod n$ for any integer $c$. (moral: you can multiply both sides of a congruence by something)

So now:

We can prove from the definition of congruence that $-5 \cong 0 \pmod 5$. Therefore, using $(2)$, we can say that $(-5) \cdot b \equiv 0 \cdot b \pmod 5$, so $-5b \equiv 0 \pmod 5$.

Using $(2)$, we can add the congruences $2a+5b + 3c \equiv 0 \pmod 5$ and $-5b \equiv 0 \pmod 5$ to get $2a+3c \equiv 0 \pmod 5$.

This is how it's done very formally; in practice, in any congruence relation, if you see some $a$ and you know that $a \equiv b$, then you can replace $a$ with $b$ in some or all places where $a$ occurs. That's why I said in the original that $5b \equiv 0 \pmod 5$ and we are done, since you can just replace $5b$ by $0$.

A note about $(2)$: you can always multiply both sides, but you can't always divide, or cancel out common factors. For example, $4 \cdot 3 \equiv 2 \cdot 3 \pmod 6$, but $3 \not \equiv 2 \pmod 6$. Canceling of course does work in some places, but in only works in all cases if you are modulo a prime number; then it's ok to cancel like this.

Ovi
  • 23,737