0
$\begingroup$

For any $(x,y) \in \mathbb{N}$, $xRy $ iff $xy$ is a perfect square. Show that $R$ is an equivalence relation and what are the equivalence classes? Here is my progress so far.

By the rules of multiplication we know that it is already symmetric and reflexive because for any $x \in \mathbb{N}, x^2$ is by definition a perfect square and for any $x,y \in \mathbb{N}, xy = yx$. But for transitivity would I use the fundamental theorem of arithmetic and use the fact that all the exponents over the primes in a perfect square have to be even? Also for the equivalence classes do I do a similar thing and use the prime factorization?

$\endgroup$
2
$\begingroup$

You just need to prove that $x R y$ if and only if $S(x)=S(y)$, where $S(x)$ is the set of prime numbers with odd exponents in the prime factorization of $x$. All the rest follows from that.

$\endgroup$
2
  • $\begingroup$ To prove two sets are the same you have to prove that they are subsets of each other right? The equivalence classes would follow from that fact? I am guessing there isn't a nice closed form expression for the equivalence class then. $\endgroup$ – ultrainstinct Nov 2 '15 at 14:30
  • 1
    $\begingroup$ @Panphobia How about $[x]=\{y\mid S(y)=S(x)\}$ then? Closed form for equivalence class. Not nice enough? You could also define equivalence classes on base of finite sets of primes. If $P$ is such a set and $m$ the product of its elements then $[m]=\{mn^2\mid n\in\mathbb N\}$. Be aware that $P$ is allowed to be empty. In that case $m=1$. $\endgroup$ – drhab Nov 2 '15 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.