Proof that a given (equivalence) relation is not a congruence

Question

Given the following relation: $$R = \{(x,y) \in \mathbb{Z} \times \mathbb{Z} \mid \exists k,l \in \mathbb{N} \backslash \{0\}: x^k = y^l\}$$ it's quite easy to prove that this relation is an equivalence relation, which isn't the problem. But how do I prove that this relation is not a congruence relation to the semigroup $(\mathbb{Z},\cdot)$?

Answer 1

First, note that we of course require $x$ and $y$ to have the same set of prime factors in order to have $R(x,y)$. That, however, isn't sufficient- we also need that $x$ and $y$ have their prime factors in the same ratio. That is, if $p_1, p_2...p_n$ are the prime factors of $x$ and $y$ (these are all of their prime factors, and each of them has multiplicity at least $1$ in both $x$ and $y$), and $m_1,m_2...m_n$ represents the multiplicities of these factors in $x$, and $w_1,w_2...w_n$ represents the multiplicities of these factors in $y$, then $(m_1,m_2...m_n) = c(w_1,w_2...w_n)$ for some nonzero $c$, i.e. they're scalar multiples of each other. In other words, one is a power of the other. (Obviously, zero relates only to itself.)

For this to be a congruence relation, you would need that if $R(x,y)$ and $R(w,z)$ for any integers $w,x,y,z$, then $R(rx,wy)$. Can you then conclude why there would be a problem? Note that $R(x,x)$ is always true.

EDIT: The necessity of both conditions should of course be proven. The second condition can also easily be shown to be sufficient.