Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
    
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

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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