Question

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

a.) Give two pairs which are in the relation =4 and two pairs that are not.

b.) Show the =m is an equivalence relation.

Answer 1

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}*\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
  `\\ot \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.