Sign up ×
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.

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.

share|cite|improve this question

2 Answers 2

up vote 2 down vote accepted

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.

share|cite|improve this answer
A perfect answer. Thank you. – Moderat 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.$

share|cite|improve this answer

Your Answer


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.