Proving $a=b \bmod 19$ is an equivalence relation

Question

My question is:

$a \equiv b \bmod {19} \iff aRb$ (prove that $R$ is an equivalence relation)

Before that, I already know that equivalence relation is when $R$ is reflexive, symmetric and transitive but just don't know how to prove it. I've searched for similar questions before asking but did not really get it because of all the symbols and stuff and I am new to discrete maths.

Thanks in advance!

Answer 1

HINT:

write $a=19k+r, b=19q+z, c=19t+s$.

Does $a\equiv a$ mod$(19)$?

If $a\equiv b$ mod$(19)$, does $b\equiv a$ mod$(19)$?

If $a\equiv b$ mod$(19)$ and $b\equiv c$ mod$(19)$, does $a\equiv c$ mod$(19)$?

Answer 2

To check these, remember that $$a\equiv b \pmod{19} \iff 19 |(a-b)\iff a-b=19k \text{ for some }k\in \Bbb Z$$

• Reflexive: $a\overset{?}{\equiv} a \pmod{19}$
• Symmetric: Suppose $a\equiv b \pmod{19}$. Does this imply that $b \equiv a \pmod{19}$?
• Transitive: Suppose $a \equiv b \pmod{19}$ and $b \equiv c \pmod{19}$. Do these imply that $a \equiv c \pmod{19}$?

Answer 3

Yes, you need to prove that the relation is reflexive, symmetric and transitive.

Reflexivity: clearly aRa, since $19$ divides $0=a-a$.

Symmetry: Suppose aRb. Then $a= b\;\text{mod} 19$ which means 19 divides $a-b$. But then it also divides $-(a-b)=b-a$ and hence $b=a\;\text{mod} 19$. So bRa.

Finally,

Transitivity: Suppose aRb and bRc. Then $a-b=19k$, for some integer $k$ and also $c-b=19m$ for some integer $m$. But then, subtraction of the two equalities gives $a-c=19k-19m=19(k-m)$ and therefore $a-c$ is a multiple of $19$, implying $aRc$ as required.