Product of Divisors of some $n$ proof

Question

The function $d(n)$ gives the number of positive divisors of $n$, including n itself. So for example, $d(25) = 3$, because $25$ has three divisors: $1$, $5$, and $25$.

So how do I prove that the product of all of the positive divisors of $n$ (including $n$ itself) is $n^{\frac{d(n)}{2}}$.

For example, the divisors of $12$ are $1$, $2$, $3$, $4$, $6$, and $12$. $d(12)$ is $6$, and $1 · 2 · 3 · 4 · 6 · 12 = 1728 = 12^3 = 12^{\frac{6}{2}} = 12^{\frac{d(n)}{2}}$

Answer 1

You want to show that $\prod_{d\mid n}d^2=n^{d(n)}$. Note that $$\prod_{d\mid n}d^2=\prod_{d\mid n}d\frac{n}d=\prod_{d\mid n}n=n^{d(n)}$$

Answer 2

The solution by Pedro Tamaroff is far more compact, and better. We will give the same proof in a more long-winded way.

First we mention a fact about the private lives of the divisors of $n$. It is easy to see that $d$ is a divisor of $n$ if and only if $\frac{n}{d}$ is a divisor of $n$. It turns out that $d$ and $\frac{n}{d}$ are a couple, or to put it in the language of today, they are partners. In your example, $1$ and $12$ are partners, as are $2$ and $6$, as are $3$ and $4$. Note that the product of any $2$ partnered numbers is $n$.

Then if $n$ is not a perfect square, the divisors of $n$ are divided into couples. If $n$ is a perfect square, then $\frac{n}{\sqrt{n}}=\sqrt{n}$, so in that case all the divisors of $n$ are coupled except for $\sqrt{n}$.

Let us look first at the case $n$ not a perfect square. Then there are $\frac{d(n)}{2}$ couples. The product of the elements in any couple is $n$, so the product of all the divisors of $n$ is $n^{d(n)/2}$.

Now suppose that $n$ is a perfect square. Then there are $\frac{d(n)-1}{2}$ couples plus a solitary individual $n^{1/2}$.

The product of the elements in any couple is $n$, so the product of all the coupled elements is $n^{(d(n)-1)/2}$. Multiply by $n^{1/2}$. We get $n^{d(n)/2}$.

Answer 3

I was playing with the Dirichlet convolution that results from the zeta function and its derivative multiplied together and found this roundabout proof, I ended up here because I was just wanting to confirm that it was correct but found that no one offered this solution so here I am giving it.

$$\sum_{d|n} \log d = \log \left( \prod_{d|n} d \right)$$

However we can rewrite that sum the other way as,

$$\sum_{d|n} \log (n/d) = \sum_{d|n} \log n - \sum_{d|n} \log d$$

Like the snake biting its own tail for using integration by parts to integrate $e^x \sin x$ we can add that sum itself to the left hand side and divide by 2 to get

$$\sum_{d|n} \log d = \frac{\tau(n)}{2} \log n$$

Since this is equal, to the original sum, equating them gives the result

$$n^{\tau(n)/2} = \prod_{d|n}d$$

Answer 4

I know this is an old question, but I recently came across to this problem and after solving it on my own, I decided to make a research for it and found this entry.

The above-mentioned solutions are really great. But for those who need less abstract solutions, I will just post my approach to this question step by step.

1) Let's call our subject, the natural number, n and call the product of its divisors, m. It is pretty easy to see that n and m are made of exactly the same prime numbers, meaning that if you prime-factorize both of them, you will see the same prime numbers (SPOILER: however their powers will be different most of the times).

2) If you can figure out the power of each prime number in the prime factorization of m, you can figure out m. (Pretty easy, right? [see Unique Factorization Theorem for the sake of math]). So let's try to figure out the powers of prime factors of m.

3) Remember, m is the product of divisors of n. So, for every prime number p, that is a prime-factor (in other words, a divisor) of n, consider all the divisors of n that are divisible by p. (It may be hard to consider them for now). Now, think on this following statement for some time and try to convince yourself for it: The set of divisors of n that are divisible by p is the same set with the set of divisors of n, that are NOT divisible by, multiplied by all the powers of p that divide n. (I know it's mouthful).

4) In case the last statement is hard to swallow do the following. Draw a Venn diagram of the set of all divisors of n. (I suggest a rectangle). Let's say, the power of p is k in the prime-factorization of n. Divide the Venn diagram into k+1 subsets that have the equal size on your diagram. The top subset is the set of divisors that are not divisible by p. The second subset is the set of divisors that are divisible by p but not p^2. The third subset includes divisors that are divisible by p^2 but not p^3. ...and all the way to the last subset whose elements are divisors of n that are divisible by p^k. Let's call these subsets A0, A1, A2,... Ak from the begining to the end.

Now consider A0. If you multiply the elements of A0 with p, you get the A1. If you multiply the elements of A0 with p^2, you get A2. Now recall the last final statement in the bullet 3); you will understand the statement now. This means all these subsets have equal number of elements.

5) Back to the topic, consider all the divisors of n that are divisible by p. This set is the same with the union of A1, A2, ..., Ak (since only A0 is 'p-free'). The power of p in the prime-factorization of m, can be figured out by the power of p in the prime factorization of the number that is equal to the product of the elements in the sets A1, A2, ..., Ak. (We excluded A0, because it will not bring any p factor). Remember that, A1=p * A0 A2=p^2 * A0 ... Ak = p^k * A0

So, "'the number' that is equal to the product of the elements in the sets A1, A2, ..., Ak" is the same with the product of elements in the sets p * A0, p^2 * A0, ..., p^k * A0. (Multiplying a number with a set is a bad notation, but I hope it makes sense).

6) Denote the number of elements in A0 (in other words, the number of p-free divisors of n) by c. The power of p in the prime factorization of 'that number' will be 1*c + 2*c + ... + k*c, because A1 brings 1 p factor for each of c elements, A2 brings 2 p factors for each of c elements, ... until all the way down to Ak that brings k p factors for each c elements. (Recall that each subset has equal number of elements and A0 has c elements, so each one of them has c elements). Consider: 1*c + 2*c + ... + kc = [k(k+1)/2]*c

7) (Almost over). This was for a prime factor p of n that has the power k and A0 had c elements. If you consider all the prime factors of n, you will have different p, k, c values and different A0, A1,..., Ak sets. Let's say, n = p1^k1 * p2^k2 * ... * pt^kt. (the numbers at the right side are indices. Please someone fix my post). (There are t number of unique prime factors of n).

The final equation of 6) tells us that

m = p1^[(k1*(k1+1)/2)*c1] * p2^[(k2*(k2+1)/2)*c2] * ... * pt^[(kt*(kt+1)/2)*ct]

Also notice that

c1 = (k2+1)(k3+1)(k4+1)...*(kt+1)

c2 = (k1+1)(k3+1)(k4+1)...*(kt+1)

c3 = (k1+1)(k2+1)(k4+1)...(kt+1) ... ct = (k1+1)(k2+1)(k4+1)...(k(t-1)+1)

because i.e c1 is the number of divisors that are not divisible by p1, which is the number of divisors of n/(a1^k1) which is the same number of n divided by the biggest power of a1 that divides n, so you only consider the rest of the powers k2, k3, ... and add 1 to each of them and then multiply to find out the total number of divisors of n/(a1^k1). (like we were taught in the elementary school).

And let's denote (k1+1)(k2+1)(k3+1)(k4+1)...(kt+1) as C which is the total number of divisors of n.

So, m becomes:

m = p1^[(k1/2)*C] * p2^[(k2/2)*C] * ... * pt^[(k2/2)*C]

m = (p1^k1)^(C/2) * (p2^k2)^(C/2) * ... * (pt^kt)^(C/2)

m = [(p1^k1)(p2^k2)...*(pt^kt)]^(C/2)

m = n^(C/2)

This is the end since C was the total number of divisors as you expected.

I know this proof was a pain in the ass to follow and was too long, but since there were a lot of calculations and analysis, I believe it should be more convincing than one-line solutions especially if you struggle with thinking in a abstract way or if you just didn't put your full trust into math yet that you need to see some calculations and diagrams to believe it :D.

Answer 5

Let the set of divisors of $n$ be $s(n)=\{x_1,...,x_{d(n)}\}.$ Then $$s(n)=\{n/x_1,...,n/x_{d(n)}\}.$$ $$\text {Therefore}\quad \prod_{x\in s(n)}x=\prod_{x\in s(n)}n/x=n^{d(n)}/\prod_{x\in s(n)}x.$$

Answer 6

I had a different approach, albeit less elegant than the ones above. I'll outline it for anyone that wants a more brute force approach.

Let $$n=\prod_{i=1}^{k} p_i^{e_i}$$ where the $p_i$'s are the $k$ distinct prime divisors of $n$ and are in some fixed order (as $i$ increases). Define $n_l$ as $\prod_{i=1}^{l}p_i^{e_i}$ and $P_l$ as the product of all positive divisors of $n_l$. Note that each of the divisors will be of the form $$\prod_{\substack{i\in S \\ S\subseteq \{1,\ldots, l\}}} p_i^{m_i}$$ where for each $p_i$ you pick an $m_i$ satisfying $1\leqslant m_i \leqslant e_i$. Obviously we wish to find $P_k$.

Consider $P_{k-1}$, which will have all such divisors consisting of all primes except the last one, $p_k$. To obtain the divisors which have $p_k$ in their factorisation, we can just take every possible positive divisor obtainable from the first $k-1$ primes, and multiply each one by $p_k^{m_k}$, making $m_k$ range from $0\leqslant m_k \leqslant e_k$. Observe that $\tau(n_l)=\prod_{i=1}^{l}(e_i+1)$, as for each prime $p_i$ we can pick an exponent from $e_i+1$ available choices ($0,1,\ldots,e_i$).

So to demonstrate we can take $P_{k-1}$ and multiply each of the $\tau(n_{k-1})$ divisors by $p_k^0=1$, giving just $P_{k-1}$, and then $p_k^1$, giving $P_{k-1}(p_k^{1})^{\tau{(n_{k-1})}}=P_{k-1}p_k^{1\times \tau{(n_{k-1})}}$, and then $p_k^2$, giving $P_{k-1}(p_k^{2})^{\tau{(n_{k-1})}}=P_{k-1}p_k^{2\times \tau{(n_{k-1})}}$, and then $\ldots$, and then $p_k^{e_k}$, giving $P_{k-1}(p_k^{e_k})^{\tau{(n_{k-1})}}=P_{k-1}p_k^{e_k\tau{(n_{k-1})}}$. We just want to take the product over all these for the product of all positive divisors of $n$, $P_k$. This gives a recurrence relation, in $P_k$, as the exact same argument applies for any index $l$ and $P_l$. $$ \begin{align} P_k &=\prod_{i=0}^{e_k}P_{k-1}p_k^{i\tau{(n_{k-1})}} \\&=P_{k-1}^{e_k+1}\left(\prod_{i=0}^{e_k}p_k^{i}\right)^{\tau{(n_{k-1})}} \\&=P_{k-1}^{e_k+1}p_k^{{\tau{(n_{k-1})}}\sum_{i=0}^{e_k}{i}} \\&=P_{k-1}^{e_k+1}p_k^{\frac 1 2 {\tau{(n_{k-1})}}e_k(e_k+1)} \\&=P_{k-1}^{e_k+1}p_k^{\frac 1 2 e_k(e_k+1)\prod_{i=1}^{k-1}(e_i+1)} \\&=P_{k-1}^{e_k+1}p_k^{\frac 1 2 e_k\prod_{i=1}^{k}(e_i+1)} \\&=P_{k-1}^{e_k+1}p_k^{\frac 1 2 {\tau{(n_{k})}}e_k} \tag{*} \end{align} $$

Now we can just keep applying the recurrence, as follows.

$$ \begin{align} P_k &= \left(P_{k-2}^{e_{k-1}+1}p_{k-1}^{\frac 1 2 {\tau{(n_{k-1})}}e_{k-1}}\right)^{e_k+1}p_k^{\frac 1 2 {\tau{(n_{k})}}e_k} \\&= P_{k-2}^{(e_{k-1}+1)(e_k+1)}p_{k-1}^{\frac 1 2 {\tau{(n_{k-1})}}e_{k-1}(e_k+1)}p_k^{\frac 1 2 {\tau{(n_{k})}}e_k} \\&= P_{k-2}^{(e_{k-1}+1)(e_k+1)}p_{k-1}^{\frac 1 2 {\tau{(n_{k})}}e_{k-1}}p_k^{\frac 1 2 {\tau{(n_{k})}}e_k} \\&= \ldots \\&=P_{j}^{\prod_{i=j+1}^{k}(e_i+1)}\prod_{i=j+1}^{k}p_i^{\frac 1 2 {\tau{(n_{k})}}e_i} \\&= \ldots \\&= \prod_{i=1}^{k}p_i^{\frac 1 2 {\tau{(n_{k})}}e_i} \\&= \left(\prod_{i=1}^{k}p_i^{e_i}\right)^{\frac 1 2 {\tau{(n_{k})}}} \\&= n^{\frac{\tau{(n)}}{2}} \end{align} $$

giving the result. For rigour you can prove (*) by induction downwards on $k$.