Define a equivalence relation For any (x,y)∈N...

Question

For any $(x,y)∈ \Bbb N$ , x ~ y is an equivalence relation if and only if $xy$ is a perfect square. 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∈\Bbb N$,$ x*x= {x^2}$ is by definition a perfect square and for any $x,y∈\Bbb N,xy=yx$ . But for transitivity and finding the equivalence classes I have hit a road block. My professor mentioned that prime factorization can be used but I just aren't seeing it.

Answer 1

Let $x=p_1^{r_1}\cdots p_n^{r_n}$ and $y=p_1^{s_1}\cdots p_n^{s_n}$, with all $r_k$ and $s_k$ nonnegative.

If $xy$ is a perfect square, then $2|r_k+s_k$ for each $k$. In other words, $r_k\equiv s_k\pmod 2$. Can you get it from here?

For the equivalence classes, lets start with the equivalence of $1$. Since, $1y=y$, we have $1\sim y\iff y$ is a perfect square. Let's let $[n]$ be the equivalence class of $n$. Then $[1]=\{n^2:n\in\Bbb N\}$.

Now, lets find $[p]$ where $[p]$. If $py$ is a perfect square, then $y=p^rq_1^{r_1}\cdots q_n^{r_n}$ where each $q_k$ is prime, $r$ is odd and $r_k$ is even for each $k$.

Next do this for pairs of primes, and then triples of primes. You should get the idea of how to identify the equivalence classes.

Answer 2

Prime factorization does help. First I would like to mention that $x\in\mathbb{N}$ is a perfect square iff each of his prime factors has an even power. If $x=p_1^{2s_1}p_2^{2s_2}p_3^{2s_3}$ then $x=(p_1^{s_1}p_2^{s_2}p_3^{s_3})^2$. Suppose x ~ y and y ~ z. Lets look at their prime factorization. $x=p_1^{r_1}p_2^{r_2}...p_n^{r_n}$ $y=p_1^{k_1}p_2^{k_2}...p_n^{k_n}$ $z=p_1^{t_1}p_2^{t_2}...p_n^{t_n}$. Let us argue that $\forall i \space r_i\equiv_2k_i\equiv_2t_i$. Assume to get contradiction $r_j\not\equiv_2k_j$ thus w.l.o.g $r_j \equiv_2 0$ and $k_j \equiv_2 1$. Now $xy=p_1^{r_1 + k_1}p_2^{r_2 + k_2}...p_n^{r_n + k_n}$ but $r_j + k_j \equiv_2 1$ which means $xy$ is not a perfect square. The same holds for $k_i\equiv_2t_i$ and from the transitivity of $\equiv_2$ we get $r_i\equiv_2t_i$ which implies $r_i + t_i \equiv_2 0$ which implies all $xz$ prime factors powers are even which makes it a perfect square. Equivalence classes are given by the powersof each prime mod 2 i.e. for each prime $p$ we can write $x=p^{s_x}x'$ and $y=p^{s_y}y'$ so x ~ y iff $s_x\equiv_2 s_y$ for all primes $p$.