Prove $a R b$ iff $a \equiv b \pmod 2$ and $a \equiv b \pmod 3$ is an equivalence relation

Question

In the set $\mathbb{Z}$ we describe the relation:

$a\mathrel{R}b \Leftrightarrow a\equiv b\pmod2 \text{ and } a\equiv b\pmod3$

Prove that $R$ is an equivalence relation. Describe $\overline{0}$ and how many different classes of equivalence relations exist?

I know that to prove that R is an equivalence relation we need to show that R has Reflexivity, symmetry and transitivity, but we have not done any examples in class and I am not very aware of how to prove it .

Just guidelines to help me understand are enough, no full solutions plese!

My solution on symmetry, tell me if it's correct:

$a\equiv bmodn$ : $\exists n \epsilon \mathbb{Z} : n \mid (a-b)$

$a\mathrel{R}b$ : $a\equiv bmod2$ and $a\equiv bmod3$

$b\mathrel{R}a$ : $b\equiv amod2$ and $b\equiv amod3$

$\exists 3 \epsilon Z : 3 \mid (a-b)$

$\exists 2 \epsilon Z : 2 \mid (a-b)$

$\exists 3 \epsilon Z : 3 \mid (b-a)$

$\exists 2 \epsilon Z : 2 \mid (b-a)$

let $a-b = k$

$b-a = -k$

$\exists (-1) (-1)(a-b) = (b-a)$

Answer 1

Hint:

To prove that ${\bf R}$ is an equivalence relation, you must prove:

• Reflexivity: for all $a$, we have $a{\bf R}a$
• Symmetry: if $a{\bf R}b$, then $b{\bf R}a$
• Transitivity: if $a{\bf R}b$ and $b{\bf R}c$, then $a{\bf R}c$

---

Work:

Given that you have not had any examples in class, I will do the case for reflexivity and leave you the others as exercise. Note that we will need a definition of the modulo operation: we write that $a \equiv b$ (mod n) iff $\exists n \in \mathbb{Z}$ s.t. $n|(a-b)$: $a$ is equivalent to $b$ mod $n$ if and only if $n$ divides their difference.

Reflexivity:
Take any $a \in \mathbb{Z}$. Then $a \equiv a$ (mod 2) and $a \equiv a$ (mod 3), because $(a-a)=0$ and $2|0$ and $3|0$. To prove that two and three both divide zero, we note that there exists $0$, an integer such that $n \cdot 0 = 0$.

Answer 2

The equivalence relation is the intersection of the equivalence relations $a\tilde{}b$ iff $a\equiv b \mod 2$ and $a\tilde{} b$ iff $a\equiv b \mod 3$. The intersection of two equivalence relations is again an equivalence relation. See this question