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.
is there a relation between divisors(n) and divisors($n^2$)?
-
0It 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. – 2012-11-23
7 Answers
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.
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)\}. $
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.
-
0@MatthewConroy, yes, that seems right. If he ever again looks at this site he will get correct answers to several related questions. – 2012-11-23
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}$.
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$.
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.
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.$