# How did this method get the correct answer? Product of divisors

Find the product of the divisors of $420^4$.

$420^4=2^8 \cdot 3^4 \cdot 5^4 \cdot 7^4$. I tried the following method which I soon realized was flawed: for $2^8$ there are $5^3$ possible divisors, for $2^7$ there are also $5^3$ and so on... for $3^4$ there are $9 \cdot 5^2$ possible divisors and for $3^3$ and so on and so forth.

Though I seem to be over-counting the powers loads here, e.g. I will count any one divisor maybe four times. But I still get the answer as $420^{2250}$ which is correct, how can this be?

And yes I know the formula for working out the product easily.

-
You're not even counting whole divisors. You're counting the exponent of each of the four prime divisors which occurs in the product. – Graham Kemp Jul 17 '14 at 2:31

I believe it's just a coincidence of the fact that you're computing the product of the divisors of $n^{\ell}$ for a number $n$ that has $\ell$ distinct prime factors.

Set $n=420$ and $m=420^4$. If by the statement "for $2^8$ there are $5^3$ possible divisors" you mean that there are $5^3$ possible divisors of $m$ of the form $2^8 \cdot s$ for an integer $s$, then yes, this will over-count the number of divisors $d$ of $m$ by a factor of $4$. So your count is $c = 4d$.

I suspect all you did was compute $n^{c/2}$ rather than $m^{d/2}$. But $n^{c/2} = n^{4d/2} = (n^4)^{d/2} = m^{d/2}$.

This generalizes. If $n$ has the prime factorization $n=\prod_{i=1}^{\ell} p_i^{a_i}$ then $$c:=\prod_{i=1}^{\ell} (a_i + 1) = \ell \cdot d$$ where $d$ is the number of divisors of $n$. Then of course the product of all the divisors of $n^{\ell}$ is just $n^{c/2}$.

-

What you are doing seems to be correct, although your procedure is a bit ad hoc.

Let me try to formalize your method: in general, if $x = p_1^{n_1} p_2^{n_2} ... p_k^{n_k}$ with $p_i$ distinct primes and $n_i>0$, the product of all factors will be of the form $p_1^{K_1}\dots p_n^{K_n}$ for some $K_i >0$. The crux of the matter is to determine the $K_i$'s. Note that $K_i$ will be the sum over all factors of $x$ of the exponent of $p_i$ appearing in the factor.

This is, I think, what you are getting at when you write "for $2^8$ there are $5^3$...". You're saying that factors divisible by $2^8$ will contribute $8\cdot 5^3$ to the exponent of $2$ in the product of all factors. Factors divisible by $2^7$ but not $2^8$ will contribute $7*5^3$, and so forth. Summing all these, you get $(1+2+3+4+...+8)(5^3)$ for the exponent of $2$. The way that you've enumerated things, nothing is double counted.

Returning to the general set up, factors of $x$ are precisely numbers of the form $p_1^mt$, for $t$ a factor of $p_2^{n_2}\dots p_k^{n_k}$ and $0 \leq m \leq n_1$. If we let $M$ equal the number of factors of $p_2^{n_2}\dots p_k^{n_k}$, we have that $$K_1=M(\sum_{i=1}^{n_1}i) = M\frac{n_1(n_1+1)}{2}.$$ In your case, if $p_1=2$ and $n_1=8$, you calculate that $M= 5^3$. This is correct: in general, $M$, the number of factors of $p_2^{n_2}\dots p_k^{n_k}$, is $(n_2+1)\dots (n_k+1)$. Generalizing this argument to other indices,

$$K_j = \frac{(\prod_{i=1}^k n_i+1)(n_j)}{2},$$

which is the formula that you know. So your method can actually be used to construct a (much longer) proof of the formula.

Hope this helps clarify things.

-

Call $n=420^4$, $D = \{ \mbox{divisors of }n\}$ and $d=\#D$. Then $$\left(\prod_{a \in D} a\right)^2 = \prod_{a \in D} a * \prod_{a \in D} \frac{n}{a} = n^d$$

So the answer is $n^{d/2}$.

Finally, computing $d=9*5*5*5 = 1125$, you get that the product of the divisors of $n$ is $420^{2250}$.

-
Sorry but did you read my post? I know the formula, I was just wondering why an apparently flawed method gave the correct answer as it seems to me that it should have given a completely wrong answer. – user121591 Jul 16 '14 at 22:40

$420^4 =2^8 \cdot 3^4 \cdot 5^4 \cdot 7^4$. I tried the following method which I soon realized was flawed: for $2^8$ there are $5^3$ possible divisors, for $2^7$ there are also $5^3$ and so on... for $3^4$ there are $9⋅5^2$ possible divisors and for $3^3$ and so on and so forth.

Though I seem to be over-counting the powers loads here, e.g. I will count any one divisor maybe four times. But I still get the answer as $420^{2250}$ which is correct, how can this be?

Why do you think this method is flawed? You want to count the product of all the divisors of the number, so of course you're counting the same prime divisors multiple times.

Let's simplify the example. Find the product of the divisors of $18$.

The divisors of $18$ are: $\{1, 2, 3, 6, 9, 18\}$ which is: $\{2^0 3^0, 2^1 3^0, 2^0 3^1, 2^1 3^1, 2^0 3^2, 2^1 3^2\}$

Clearly each power of $2$ occurs thrice, and each power of $3$ occurs twice.

So the product is: \begin{align} & \quad (2^0 \times 2^1)^3 \times (3^0 \times 3^1 \times 3^2)^2\\ & = 2^{(0+1)\times 3}\cdot 3^{(0+1+2)\times 2} \\ & = 2^3 3^6 \\ & = 18^3\end{align}

Thus by this method, the product of the divisors of $420^4$ is: \large \begin{align} & \quad\quad 2^{\frac{8\times 9}2\times 5^3}3^{\frac{4\times 5}2\times 9\times 5^2}5^{\frac{4\times 5}2\times 9\times 5^2}7^{\frac{4\times 5}2\times 9\times 5^2} \\ & = (2^2\times 3\times 5\times 7)^{2\times 9\times 5^3} \\ & = 420^{2250}\end{align}

In general, take any cardinal $n$, such that $n= \prod_{i=1}^r p_i^{a_i}$ where $\{p_1, \ldots p_r\}$ are the prime divisors of $n$, and $\{a_1, \ldots, a_r\}$ are their exponents.

Let $\pi(n)$ be the product of the divisors of $n$. The number of times a prime divisor ($p_i$) appears in $\pi(n)$ will be $\frac {a_i} 2 \sum_{j=1}^r (a_j+1)$. (As shown above.) So thus:

\begin{align}\pi(\prod_{i=1}^r p_i) & = \prod_{i=1}^r p_i^{\frac {a_i} 2 \sum_{j=1}^r (a_j+1)} \\ & = \left(\prod_{i=1}^r p_i^{a_i}\right)^{\frac 12 \prod_{j=1}^r (a_j+1)} \\ \therefore \pi(n) & = n ^{\frac 12 \prod_{j=1}^r (a_j+1)} \end{align}

Now we know that $\sigma_0(n) = \sum_{j=1}^r (a_j+1)$ is the count of whole divisors of $n$. So we have: $$\pi(n) = n^{\sigma_0(n)/2}$$

\boxed{\begin{align}\because \sigma_0(2^8 3^4 5^4 7^4) & =(8+1)(4+1)^3 \\ & = 1125 \\ \therefore \pi(420^4) &= (420^4)^{1125/2} \\ & = 420^{2250}\end{align}}

-
If I understood things correctly, the poster wasn't concerned about over-counting prime divisors but rather the divisors themselves. – Shawn O'Hare Jul 17 '14 at 0:23
You're correct Shawn – user121591 Jul 17 '14 at 15:40