# For $\ a, b \in \mathbb Z, a\approx b\ \Leftrightarrow \ 2a+3b\equiv0\pmod5$ Is $\sim$ an equivalence relation on $\mathbb Z$?

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.

• $\approx$ is just the same as ~. They just wanted to use a different notation because they already used ~ in part a
– Ovi
Commented Nov 15, 2018 at 2:54
• $\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$. Commented Nov 15, 2018 at 2:55
• it's not equivalent though, is it? I found that it's equivalent to $a \equiv -4b \pmod 5$ Commented Nov 15, 2018 at 3:01
• @Claire Good. Now $-4 \equiv 1 \pmod 5$
– Ovi
Commented Nov 15, 2018 at 3:03
• @Claire By the way, if you want the person to be notified of your comment, you have to use "@theirname"
– Ovi
Commented Nov 15, 2018 at 3:04

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.

• can you just explain the last part of this a bit more, the part that starts with "but" Commented Nov 15, 2018 at 3:09
• @Claire Sure, editing now
– Ovi
Commented Nov 15, 2018 at 3:11
• okay thank you! @ovi Commented Nov 15, 2018 at 3:21
• @Claire Just finished the edit
– Ovi
Commented Nov 15, 2018 at 3:41
• okay this makes sense, thank you so much for taking the time to help me! @Ovi Commented Nov 15, 2018 at 3:46