Define a relation on $Z$ by a~b if and only if $a=b(mod2)$ and $a=b(mod5)$. Show that ~ is an equivalence relation.

Question

The if and only if is throwing me off. Would the first direction be to prove the two modular conditions hold if the relation is an equivalence relation? Furthermore, I'm having difficulty proving reflexivity, symmetry and transitivity with the modular arithmetic. Help?

Answer 1

Hint: the relation can be viewed as $a=b \pmod{10}$

In fact $a=5z + b$, $a=2y + b$ implies $5z=2y$, so $z=2w$ (i.e. $z$ is even, they're integers) and so $a=10w+b$.

Answer 2

It seems that there might be some confusion about what you're actually trying to prove; there are two parts here: The first is the definition of $\sim$, and the second is a claim about the properties of $\sim$. So by definition, we write

$$a \sim b$$

if $a \equiv b \mod 2$ and $a \equiv b \mod 5$, and we don't write $\sim$ in any other case.

Now the claim about $\sim$ is that it's an equivalence relation; there are three things to check in the definition of an equivalence relation:

• Show that $a \sim a$ by noticing that $a \equiv a \mod 2$ and $a \equiv a \mod 5$.

• Show that if $a \sim b$, then $b \sim a$; again, this is immediate from studying congruences.

• Show that if $a \sim b$, then $b \sim c$. That is, assume that $a \equiv b$ both modulo $2$ and $5$, and that $b \equiv c$ both modulo $2$ and $5$, and try concluding that $a \equiv c \mod 2$ and $a \equiv c \mod 5$.

Answer 3

What you want to show is that ~ is reflexive, symmetric and transitive.

For reflexive, this amounts to showing that for any integer x, x~x i.e. $x=x$ (mod 2) and $x=x$ (mod 5). But this is clear, since any number is congruent to itself (mod 2) and (mod 5).

Symmetric: You need to show that for any integers x and y, that if x~y then y~x. That is, if $x = y$ (mod 2) and $x=y$ (mod 5), then $y=x$ (mod 2) and $y=x$ (mod 5). You should use the definition of modular equivalence here.

Transitive: You need to show that for any integers x, y, and z, that if x~y and y~z then x~z.