Determining the transversal for an equivalance relation

338 Views Asked by At

If you have an equivalence relation $c$ on $\Bbb{Z}$ defined by $$\{x,y\in\Bbb{Z}:p\in\Bbb{Z},x=5p+y\}$$ How would you proceed to determine if the following subset of $\Bbb{Z}$ $$\{-8,1,10,13,19\}$$ is a traversal of $\Bbb{Z}$ on $c$ or not?

Could you please give me a hint? The way of doing this is clearly not just brute forcing, since quotient set $\Bbb{Z}/c$ has an infinite number of elements. So how would you proceed?

1

There are 1 best solutions below

2
On BEST ANSWER

The quotient set has only $5$ elements.

Divide an integer $x$ by $5$. The remainder will say you in which class is $x$. If the number is negative and you find the division somewhat confusing (just like myself do), just add a big enough multiple of $5$ to it:

$-8+10=2$, so $-8$ is in the same class as $2$.

$1$ is in the same class as... well, as $1$.

$10$ is in the same class as $0$ because $10/5$ gives $0$ as remainder.

$13$ is in the class of $3$ because $13/5$ gives $3$ as remainder.

Etc.