contestada


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.

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

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

Respuesta :

josebarradas1607

Step-by-step explanation:

a) Give two pairs which are in the relation [tex]\equiv \mod 4[/tex] and two pairs that are not.

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

  • x=0 and y=4 is an example of a pair [tex]\equiv \mod 4[/tex]
  • x=0 and y=1 is an example of a pair [tex]\not \equiv \mod 4[/tex]

b) Show the [tex]\equiv \mod m[/tex] is an equivalence relation.

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

By definition [tex]\equiv \mod m[/tex] is a binary relation. Observe that:

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

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

In conclusion, [tex]\equiv \mod m[/tex] defines an equivalence relation.