Proving the relation $xy=m^2$ is an equivalence relation

Question

The question states that $R$ is a relation on $\mathbb{N}$ (excluding $0$) if and only if $xy = m^2$ with $m \in \mathbb{N}$. It asks to prove that it is an equivalence relation.

I showed that it is reflexive as $xx=x^2$ and we know that $x \in \mathbb{N}$.

I showed symmetry by using the fact that multiplication is commutative so $xy=yx$ thus if $xy$ is in the relation so is $yx$.

I'm having some trouble with showing that it is transitive. I know that to show if a relation is transitive then $(x,y) \in R \land(y,z) \in R \implies (x,z) \in R$.

How do i show this for this example?

Answer 1

If $x\sim y$ then $xy = n^2$ for some natural $n$; we also have $y \sim z \implies yz = m^2$. Putting this together gives

$$xz = \frac{(xy)(yz)}{y^2} = \frac{n^2m^2}{y^2} = \left(\frac{nm}{y}\right)^2$$

You just need to show that $\frac{nm}{y}$ is a natural number. Can you do that?

Answer 2

Since $(x,y)\in R$ we have $xy =a^2$ for some integer $a$ and since $(y,z)\in R$ we have $yz = b^2$ for some integer $b$. So we have $$xy^2z = a^2b^2 = (ab)^2$$ and thus $xz$ must be also square of some integer number, so $(x,z)\in R$.

Answer 3

Assume we have $(x,y) \in R \land(y,z) \in R$. Then $xy = m^2$ and $yz = n^2$ for $m,n \in \mathbb{N}$. Multiplying these equations, we get $$xy^2z = m^2n^2 \implies xz = \frac{m^2n^2}{y^2}$$ so what we need to prove is whether $\frac{m^2n^2}{y^2} \in \mathbb{N}$ or not. But this is easy since we already know $y|m^2$ and $y|n^2$ by our first assumption so we can conclude that $y^2|m^2n^2$. Therefore transitivity holds.

Answer 4

Here is another take.

Note that $xRy$ iff $v_p(x) \equiv v_p(y) \bmod 2$ for all primes $p$, because $xy=m^2$ implies $v_p(x)+v_p(y)=2v_p(m)$. (Here, $v_p(x)$ is the exponent of $p$ in the factorization of $x$.)

Let $v: \mathbb N^* \to \prod_p \mathbb \{0,1\}$ defined by $v(x)(p)=v_p(x) \bmod 2$. That is, $$v(x)=(v_2(x) \bmod 2, v_3(x) \bmod 2, v_5(x) \bmod 2, \ldots)$$

Then $xRy$ iff $v(x)=v(y)$ and so $R$ is an equivalence relation because equality is an equivalence relation.