0
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .