Add Me!Close Menu Navigation

That Other Little Gauss Story

Determine the product of distinct positive integer divisors of n = 420^4.

Since we’ve traditionally required prime factorization in order to count the divisors, let’s do that here as well.

    \begin{align*} 420 &= 21 \times 20 \\ &= 3 \times 7 \times 4 \times 5 \\ 420^4 &= 2^8 \times 3^4 \times 5^4 \times 7^4 \end{align*}

Your first instinct might have been to use a similar counting argument based on the exponents of the prime factors to say, for example, that any divisor d can either have 2^0, 2^1, 2^2, \cdots or, 2^8. Because the operative conjunction here is or, you might be tempted to say that the exponent on \prod_{d|420^4} d is just \sum_{i}^{3_2} i = \frac{8\times 9}{2}. However, this only gives the product of all the twos and the product of all the threes and so on. What it doesn’t include are things like 2 \times 3 \times 5.

Tempting as it is to approach this problem via some counting argument made on the exponents, it seems like it’s going to be a pain in the ass. Let’s have a go at it from a different direction.

Let’s look at some arbitrary divisor d = 2^a 3^b 5^c 7^d. By the definition of d being a divisor, it must be the case that exactly one other integer \frac{420^4}{d} is also a divisor of 420^4. In fact, the product of these two divisors will result in 420^4. Now, in the same vein of that school children story of how little gauss summed all integers less than 100 together within his head, we take the same exact reasoning in that story and apply it here.

Since 420^4 = 2^93^45^47^4, it must be the case that there are exactly 9 \times 5 \times 5 \times 5 = 1125 divisors. With the exception of 420^2, for every divisor d|420^4, another divisor \frac{420^4}{d}|420^4 also exists. Since there are \lfloor \frac{1125}{2} \rfloor = 562 such unique pairs whose product is 420^4, then their product must be (420^4)^526. However, we left out 420^2, so we need to take it into consideration.

This gives us 420^{4\times 526+2} = 420^{2250} as the product of all divisors of 420^4. \blacksquare

In fact, this can be extended by defining the function \tau(n) = \mbox{number of divisors of }n, then the product of all of the digits of n is just \prod_{d|n} d = n^\frac{\tau(n)}{2}. This can be shown using the same argument as above. \blacksquare

Posted By Lee