Question

We define the relation =m (read "equal mod m") on Z x Z to be the set: {(p,q): m|(p-q)}. Please show work.

Answer 1

Step-by-step explanation:

a) Give two pairs which are in the relation $\equiv \mod 4$ and two pairs that are not.

As stated before, a pair $(x,y)\in \mathbb{Z}\times\mathbb{Z}$ is equal mod m (written $x\equiv y\mod m$) if $m\mid (x-y)$. Then:

• x=0 and y=4 is an example of a pair $\equiv \mod 4$
• x=0 and y=1 is an example of a pair $\not \equiv \mod 4$

b) Show the $\equiv \mod m$ is an equivalence relation.

An equivalence relation is a binary relation that is reflexive, symmetric and  transitive.

By definition $\equiv \mod m$ is a binary relation. Observe that:

1. Reflexive. We know that, for every m, $m\mid 0$. Then, by definition, $x\equiv x \mod m$.
2. Symmetry. It is clear that, given x,y and m such that $m\mid (x-y)$, then $m\mid (y-x)$. Therefore $x\equiv y \mod m \iff y\equiv x \mod m$
3. Transitivity. Let x,y,z and m such that $x\equiv y \mod m$ and $y\equiv z \mod m$. Then, $m\mid (y-x)$ and $m\mid (z-y)$. Therefore:

$m\mid [(y-x)+(z-y)] \implies m\mid (z-x) \implies x\equiv z \mod m$.

In conclusion, $\equiv \mod m$ defines an equivalence relation.