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.

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|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
add comment

1 Answer

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|improve this answer
add comment

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.