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.

Can we generate divisors($n^2$) in case that we already have divisors(n) ? or at least can we predict how many integers are in divisors($n^2$) ?
while divisors(n) is the list of integers (not necessarily primes) which divide n.

share|improve this question
    
Look at the table here and compare numbers that relate to your question. What do you notice? Is it 'always' possible?en.wikipedia.org/wiki/Table_of_divisors –  Amzoti Nov 23 '12 at 21:39
    
It seems to me that you mean the phrase "divisors(n)" as the result of a computer command in some language similar to Mathematica, which will happily produce an ordered list of divisors, once it succeeds in factoring the number. You really should give some examples to clarify this. I give an answer based on this reading of your question. –  Will Jagy Nov 23 '12 at 22:42

7 Answers 7

We cannot predict the number of divisors of $n^2$, given the number of divisors of $n$. For note for example that $6$ and $8$ each have $4$ positive divisors. But $6^2$ has $9$, while $8^2$ has $7$.

Remark: One can generate infinitely many examples by using the fact that if the prime power factorization of $n$ is $p_1^{a_1}\cdots p_k^{a_k}$, then $n$ has $(a_1+1)\cdots (a_k+1)$ divisors.

For any composite $d$, we can find integers $x$ and $y$ such that $x$ and $y$ have the same number $d$ of divisors, but $x^2$ and $y^2$ do not.

Indeed, for any $k$, we can find numbers $x_1,x_2,\dots, x_k$ such that the $x_i$ all have the same number of divisors, but the $x_i^2$ all have distinct numbers of divisors.

share|improve this answer

If $\{r_1,r_2,\ldots,r_k\}$ are the divisors of $n$ then $\{r_i\cdot r_j:1\leq i\leq j\leq k\}$ are the divisors of $n^2$.

share|improve this answer

Let $n = \prod_p p^{\nu_p(n)}$ the prime decomposition of $n$, then $n^2 = \prod_p p^{2\nu_p(n)}$. An integer $d = \prod_p p^{\nu_p(d)}$ is hence a divisor of $n^2$, if it fulfills $\nu_p(d) \le 2\nu_p(n)$ for each $p$. Given $d$, define $$ d_1 = \prod_p p^{\lfloor\nu_p(d)/2\rfloor}, \qquad d_2 = \prod_p p^{\lceil \nu_p(d)/2\rceil} $$ Then $d = d_1d_2$ and $d_1 \mid n$, $d_2 \mid n$ (note that if $\nu_p(d)$ is odd, we have $\nu_p(d) < 2\nu_p(n)$ and hence $\lceil \nu_p(d)\rceil \le \nu_p(n)$. So every divisor of $n^2$ is a product of divisors of $n$ and therefore $$ \mathrm{divisors}(n^2) = \{a \cdot b \mid a,b \in \mathrm{divisors}(n)\}. $$

share|improve this answer

The number of divisors of $n=\prod p_i^{e_i}$ is known to be $\tau(n)=\prod(e_i+1)$, thus it is not completely possible to predict $\tau(n^2)$ given only $\tau(n)$. For example $6=2\cdot 3$ and $8=2^3$ both have $(1+1)(1+1)=3+1=4$ divisors, while their squares have $(2+1)(2+1)=9$ and $6+1=7$ divisors.

share|improve this answer
    
For what it may be worth, it appears to me that the OP is referring to "divisors(n)" as a computer command giving the list of all divisors of $n.$ If so, the prime factorization of $n$ is visible and everything else follows. We are mostly assuming he means the count of divisors because this is a mathematics website. But he is a Mechatronics Engineering Student. –  Will Jagy Nov 23 '12 at 22:48
    
@WillJagy Will, the OP's second question is "or at least can we predict how many integers are in divisors($n^2$) ?" so he is clearly interested in the count of divisors, at least secondarily. Cheers! –  Matthew Conroy Nov 23 '12 at 23:21
    
@MatthewConroy, yes, that seems right. If he ever again looks at this site he will get correct answers to several related questions. –  Will Jagy Nov 23 '12 at 23:27

If you already have all the $k$ divisors of $n$ say $$D_n = \{1=d_0, d_1,d_2,\ldots,d_k = n\}$$ then all the divisors of $n^2$ are (there will be some repetitions) $$D_{n^2} = \{d_{\ell_1}\cdot d_{\ell_2}: 1\leq \ell_1, \ell_2 \leq k\}$$ In general, if $n = p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_m^{\alpha_m}$, then the number of divisors is given by $\displaystyle \prod_{j=1}^m(1+\alpha_j) = \vert D_n \vert$. The number of divisors of $n^2$ is $\displaystyle \prod_{j=1}^m(1+2\alpha_j) = \vert D_{n^2} \vert$. Note that clearly $\vert D_{n^2} \vert \leq \vert D_n \vert^2$. If we have all $\alpha_j \geq 1$, then note that $(1+2 \alpha_j) \leq \dfrac34 (1+\alpha_j)^2$. Hence, we get that $$\vert D_{n^2} \vert \leq \dfrac34 \vert D_n \vert^2$$

However any divisor of $n^2$ will be of the form $p_1^{\beta_1}p_2^{\beta_2} \cdots p_m^{\beta_m}$, where $0 \leq \beta_j \leq 2 \alpha_j$.

Since $0 \leq \beta_j \leq 2 \alpha_j$, any $\beta_j$ can be written as $\alpha_j^{(1)} + \alpha_j^{(2)}$, where $0 \leq \alpha_j^{(1)},\alpha_j^{(2)} \leq \alpha_j$. Hence, any divisor of $n^2$ can be written as $$\underbrace{\left( p_1^{\alpha_1^{(1)}}p_2^{\alpha_2^{(1)}} \cdots p_m^{\alpha_m^{(1)}}\right)}_{d_1} \cdot \underbrace{\left(p_1^{\alpha_1^{(2)}}p_2^{\alpha_2^{(2)}} \cdots p_m^{\alpha_m^{(2)}} \right)}_{d_2}$$ where $d_1, d_2 \in D_{n}$.

share|improve this answer

Let $\tau(n)$ be the number of divisors of $n$.

Then, for a prime power, $p^{\alpha}$, we have $$ \frac{\tau(p^{2\alpha})}{\tau(p^{\alpha})} = \frac{2\alpha+1}{\alpha+1} $$ It is easy to see, then that, $$ \frac{3}{2} \le \frac{\tau(p^{2\alpha})}{\tau(p^{\alpha})} < 2$$ and we can approach the right side arbitrarily closely with larger and larger $\alpha$. Hence $$ \left(\frac{3}{2}\right)^{\omega(n)} \le \frac{\tau(n^2)}{\tau(n)} < 2^{\omega(n)}$$ where $\omega(n)$ is the number of prime divisors of $n$.

Also, since $$ \frac{2\alpha+1}{2 \alpha+2} \le \frac{3}{4}$$ for $\alpha \ge 1$, we have $$ \tau(n^2) \le \frac{3}{4} (\tau(n))^2 $$ for $n>1$, with equality if and only if $n$ is prime.

share|improve this answer

There is an ambiguity in your question. If you actually have the complete and correct list of divisors of a natural number, you can readily determine which divisors are prime powers by comparing divisors with each other. As a result, you can reconstruct the explicit prime factorization of the number. Therefore you have the prime factorization of $n^2,$ simply by doubling each exponent. Finally, there is the simple formula for calculating the number of divisors, see COUNTING DIVISORS FROM FACTORIZATION. Furthermore, you can easily produce the complete list of divisors of $n^2$ without repetition, again using the prime factorization of $n^2.$

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.