-1

I think I know hwo to prove reflexive, symmetric, and transitive properties but please show me how to do equivalence classes or describe them.

Let n ∈ N. Define relation Rn on Z by (x, y) ∈ Rn if and only if $x^2 − y^2$ is divisible by n. Prove that Rn is an equivalence relation. (a) Let n = 4. How many equivalence classes are there? Describe the equivalence classes in the simplest possible way. (b) Let n = 5. How many equivalence classes are there? Describe the equivalence classes in the simplest possible way.

P Vanchinathan
  • 19,504
james black
  • 1,893

2 Answers2

0

Hint:

These relations say $x$ and $y$ are equivalent if and only if $x^2\equiv y^2\mod n$. Hence the equivalence classes corresp.ond to the congruence classes of the squares modulo $n$.

For instance, modulo $4$ the squares are congruent either to $0$ or to $1$. So there are two equivalence classes: even numbers have squares congruent to $0\bmod 4$ and odd numbers, squares congruent to $1 \bmod 4$.

Bernard
  • 175,478
  • The question is about behaviour modulo 5, Is it easy to describe from mod 4 behaviour? – P Vanchinathan Nov 25 '17 at 00:59
  • @PVanchinathan: The question seemed to be about both mod $4$ and mod $5$. I purposely showed only the method for $4$. It is similar for mod $5$: compute the squares mod $5$ and try to find a simple description as simple as possible for numbers having the same square mod $5$. – Bernard Nov 25 '17 at 10:22
  • two equivalence as in even numbers and odd numbers? because X, Y should be divided into two classes here, not their squares? thanks – james black Nov 25 '17 at 10:53
  • I don't understand your objection. In the case of mod $4$ the classes are indeed even and odd numbers. The case of mod $5$ is of course different: there are $3$ classes, since there are three squares mod $5$: $0, 1$ and $-1$. – Bernard Nov 25 '17 at 11:19
0

Note that the number $n=5$ is a prime number. We want $x^2-y^2$ to be a multiple of $5$ which means $5$ should divide the product of the two numbers $x-y$ and $x+y$.

This boils down to one of them being a multiple of $5$, Choose any $x$. Then choose every possible $y$ such that $x-y$ or $x+y$ should be amultiple of $5$, By looking at the last digit of $x$, you can figure out how to list all such $y$'d for a given $x$.

P Vanchinathan
  • 19,504