# Verifying prime factorization equivalence class

I define a relation on $\Bbb N$ as follows:

$x \sim y \Longleftrightarrow \ \exists \ j,k \in \Bbb Z$ s.t. $x \mid y^j \ \wedge \ y \mid x^k$

I have shown that $\sim$ is an equivalence relation by proving symmetry, reflexivity, and transitivity, so now I am trying to determine the equivalence classes $[1], [2], [9], [10], [20]$

My Work

\begin{align*} \left[1\right] &= \{1\}\\ \left[2\right] &= \{2^n \mid n \in \Bbb N\} \\ \left[9\right] &= \{3^n \mid n \in \Bbb N\} \\ \left[10\right]&= \{2^n\cdot 5^m \mid n,m \in \Bbb N\} \\ \left[20\right]&= \left[10\right] \end{align*}

In general, $$\left[x\right] = \{p_1^{n_1}\cdots p_m^{n_m} \mid n_i \in \Bbb N \ \forall i \}$$ where $p_1 \cdots p_m$ is the prime factorization of $x$, which each prime raised to the first power, which is why $[10] = [20]$.

My Question

Is this a valid way to answer this question? This is just what makes sense to me, but I'm not sure if more explicit reasoning is needed.

-

You should state explicitly and prove the following general lemma. Your post shows that you are perfectly aware of it.

Lemma: Let $p_1,p_2,\dots, p_k$ be distinct primes, and let $m=p_1p_2\cdots p_k$. Let $n$ be a positive integer. Then $[n]=[m]$ iff there exist positive integers $a_1,a_2,\dots,a_k$ such that $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$.

After that, all of the specific cases are immediate consequences of the lemma.

-
A perfect answer. Thank you. –  Mike Sep 7 '12 at 16:21

Hint $\,$ Assume $\rm\,x\sim y.\,$ Prime $\rm\, p\:|\:x\:|\:y^n\:\Rightarrow\:p\:|\:y.\:$ By symmetry $\rm\:p\:|\:y\:\Rightarrow\:p\:|\:x,\:$ so $\rm\:p\:|\:x\!\iff\!p\:|\:y.\:$ Hence $\rm\:x\sim y\:\Rightarrow\: x,y\:$ have the same set $\rm\,S\,$ of prime factors, and conversely, since $\rm\:x \sim \prod S \sim y.$

Remark $\$ The product of the prime divisors of an integer $\rm\,n\,$ is called the radical of $\rm\,n.\,$ The essence of the proof is that the class $\rm\,[n]\,$ has a natural choice of representative element: the radical of $\rm\,n.$

-