# Multiplicative Arithmetic Functions

• November 2nd 2009, 07:07 PM
kyldn6
Multiplicative Arithmetic Functions
Prove that $\begin{array}{cc}\prod\\d|n\end{array}d = n^{\frac{d(n)}{2}}$

d(n) are the positive factors of n. Ex: d(12) = 6 (the factors are 1, 2, 3, 4, 6, 12).
• November 3rd 2009, 04:10 PM
tonio
Quote:

Originally Posted by kyldn6
Prove that $\begin{array}{cc}\prod\\d|n\end{array}d = n^{\frac{d(n)}{2}}$

d(n) are the positive factors of n. Ex: d(12) = 6 (the factors are 1, 2, 3, 4, 6, 12).

Well, it took a while but I think I got it. Of course, using Dirichlet's product I suppose it could be way faster, but I'm assuming you haven't yet covered that, so let's try it the long way

Let $n =\prod\limits_{i=1}^np_i^{a_i}$ be the prime decomposition of n, with $0. We'll need the following easy lemma:

Lemma: The number of positive divisors of n is $d(n)=\prod\limits_{i=1}^n(a_i+1)$

Now,by induction on n = the number of distinct prime divisors of n: if $n=p^a$ , then $\prod\limits_{d\mid n}d=1\cdot p\cdot p^2\cdot ...\cdot p^a=p^{1+2+...+a}=p^{a\frac{a+1}{2}}=\left(p^a\rig ht)^{\frac{a+1}{2}}=n^{\frac{d(n)}{2}}$ , and we're cool.

Assume now the claim's true for all natural numbers divisible by up to n-1 different primes, and let $n =\prod\limits_{i=1}^np_i^{a_i}$ and define
$m =\prod\limits_{i=1}^{n-1}p_i^{a_i}$ , then:

$\prod\limits_{d\mid n}d=\prod\limits_{d\mid m}d\,\prod_{\substack{d\mid n\\p_n\mid d}}d=m^{\frac{d(m)}{2}}m^{a_n\frac{d(m)}{2}}\cdot p_n^{d(m)}\cdot p_n^{2d(m)}\cdot...\cdot p_n^{a_nd(m)}$ , the 2nd equality being due to the inductive hypothesis and the fact that the factor $p_n^k$ appears

multiplying each and every one of the divisors of m , $1\leq k\leq a_n$ . Thus:

$\prod\limits_{d\mid n}d=m^{\frac{d(m)(a_n+1)}{2}}p^{a_n\frac{d(m)(a_n+ 1}{2}}=\left(mp_n^{a_n}\right)^{\frac{d(n)}{2}}=n^ {\frac{d(n)}{2}}$ , since $d(m)(a_n+1)=d(n)$. Q.E.D.

Tonio
• November 3rd 2009, 06:47 PM
kyldn6
Thanks Tonio, I managed to work this one out and came up with the same proof you presented in the first half of you post. Thanks for verifying it.