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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $d_{3}(n)$ denote the number of ordered 3-tuples of positive integers whose product is $n$ and $\omega(n)$ the number of distinct primes dividing $n$. How does one show that $3^{\omega(n)} \geq d_{3}(n)$ for every $n$?

share|cite|improve this question
One doesn't. If $n$ is, say, $2^{10}$, then $\omega(n)=1$, so $3^{\omega(n)}=3$, but $d_3(2^{10})$ is a lot bigger than $3$. – Gerry Myerson Nov 29 '12 at 3:19

As pointed out in the comments this is false. But, write $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$, the prime decomposition of $n$. Then define $\theta(n)=\alpha_1+\ldots+\alpha_k$. Now suppose $(a,b,c)$ is an ordered 3-tuple whose product is $n$. Clearly, $a,b,c$ can be written solely as products of powers of the primes $p_1,\ldots,p_k$. In particular, think of $n$ writen as $n=p_1\cdots p_1\cdot p_2\cdots p_2\cdots$, where each prime appears $\alpha_i$ times. To form a tuple $(a,b,c)$ we just need to ask in how many ways can we partition $\alpha_1+\alpha_2+\ldots+\alpha_n$ primes amoungst $(a,b,c)$. We can think of each prime recieving a number $1,2,3$ indicating it belongs to $a,b,c$ respectively. But this doesn't take into account the multiplicity of the primes, so we can bound this above by just selecting 1,2, or 3 for each prime, giving 3 choices for each prime for a total of $3\cdot3\cdot 3\ldots$ , $\theta(n)$ times, giving $3^{\theta(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.