# How to show that this relation is transitive

Fix $m\in\mathbf{Z}$ and consider for $x,y\in\mathbf{Z}$ the relation $\sim$, where $x\sim y$ whenever there is a $z\in\mathbf{Z}$ such that $z^2=(x\cdot y)^m$.

Consider for a fixed $n\in\mathbf{N}$ the relation $\Delta$ on $\mathbf{N}$ where $x\Delta y$ whenever there is a $z\in\mathbf{N}$ such that $z^2=(x\cdot y)^n$. I use the convention $0\notin \mathbf{N}$.

How can I show that $\sim$ is not transitive and $\Delta$ is? And how can I determine the cardinality of the equivalence classes under $\Delta$?

-
If m<0 only +1 and -1 are related with itself and there are not any more relation. If m=0 there are relation between all integers. In both case the relation is transitive, isn't it? – H. Kabayakawa Jun 2 '12 at 16:03

As was pointed out in the comments, the first part of the problem, dealing with $\sim$, is misstated. If $m<0$, $x\sim y$ if and only if $x=y=1$ or $x=y=-1$, and the relation is transitive. If $m=0$, $x\sim y$ for all $x,y\in\Bbb Z$ if, as is usual, you take $0^0=1$, and $x\sim y$ if and only if $x\ne 0\ne y$ if you take $0^0$ to be undefined; in either case $\sim$ is transitive. Presumably the intent was to have $m\in\Bbb Z^+$. In that case $x\sim 0$ for every $x\in\Bbb Z$, so to show that $\sim$ is not transitive, you need only find $x,y\in\Bbb Z$ such that $x\not\sim y$, for then you’ll have $x\sim 0$, $0\sim y$, and $x\not\sim y$. This is easy to do.

It’s best to split $\Delta$ into two cases. If $n$ is even, you should have no trouble showing that $x\Delta y$ for all $x,y\in\Bbb Z^+$ and hence that $\Delta$ is transitive. When $n$ is odd, the relation $\Delta$ isn’t nearly so trivial, and some work is required. Let’s look first at the case $n=1$: $x\Delta y$ if and only if $xy$ is a perfect square. Look at the prime factorizations of $x$ and $y$: $x=p_1^{a_1}p_2^{a_2}\dots p_m^{a_m}$, say, and $y=q_1^{b_1}q_2^{b_2}\dots q_n^{b_n}$. Now $x$ and $y$ may share some prime factors, so let’s assume that we’ve arranged them so that $p_1=q_1$, $p_2=q_2$, and so on through $p_k=q_k$, but the primes $p_{k+1},\dots,p_m,q_{k+1},\dots,q_n$ are all distinct. (If $x$ and $y$ have no common prime factors, $k=0$.) Then

\begin{align*} xy&=\left(p_1^{a_1}p_2^{a_2}\dots p_m^{a_m}\right)\left(q_1^{b_1}q_2^{b_2}\dots q_n^{b_n}\right)\\ &=p_1^{a_1+b_1}p_2^{a_2+b_2}\dots p_k^{a_k+b_k}p_{k+1}^{a_{k+1}}\dots p_m^{a_m}q_{k+1}^{b_{k+1}}\dots q_n^{b_n}\tag{1} \end{align*}

is a perfect square if and only if all of the exponents in $(1)$ are even. This happens precisely when all three of the following conditions are met:

1. If a prime $p$ is a factor of both $x$ and $y$ and appears with exponent $a$ in the prime factorization of $x$ and with exponent $b$ in the prime factorization of $y$, then $a+b$ is even.
2. If a prime $p$ is a factor of $x$ but not of $y$, it appears to an even power in the prime factorization of $x$.
3. If a prime $p$ is a factor of $y$ but not of $x$, it appears to an even power in the prime factorization of $y$.

Of course (2) and (3) are just special cases of (1) if we allow a prime to appear $0$ times in the prime factorization of a number.

In other words, $x\Delta y$ if and only if every prime number appears altogether an even number of times in the prime factorizations of $x$ and $y$ combined. Thus, to check transitivity of $\Delta$ you want to ask:

If the prime $p$ occurs altogether an even number of times in the prime factorizations of $x$ and $y$ combined, and also in the prime factorizations of $y$ and $z$ combined, must it occur altogether an even number of times in the prime factorizations of $x$ and $z$ combined?

You even know that the answer is supposed to be yes; you just have to figure out why. (HINT: When is the sum of two integers odd? When is it even?)

Once you’ve seen clearly what’s going on in the case $n=1$, the other cases when $n$ is odd should cause no trouble.

-

For any $\,k\in\mathbb{Z}\,,\,k\sim 0\,$, so $\,1\sim 0\,\,and\,\,0\sim 4\,$ , but $\,1 \rlap{/}{\sim} 4\,$ . Now play with this idea to show $\,\Delta\,$ is transitive.

-