1. ## Multiplicative Arithmetic Functions

Prove that $\displaystyle \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).

2. Originally Posted by kyldn6
Prove that $\displaystyle \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 $\displaystyle n =\prod\limits_{i=1}^np_i^{a_i}$ be the prime decomposition of n, with $\displaystyle 0<a_i\in \mathbb{N}$. We'll need the following easy lemma:

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

Now,by induction on n = the number of distinct prime divisors of n: if $\displaystyle n=p^a$ , then $\displaystyle \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 $\displaystyle n =\prod\limits_{i=1}^np_i^{a_i}$ and define
$\displaystyle m =\prod\limits_{i=1}^{n-1}p_i^{a_i}$ , then:

$\displaystyle \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 $\displaystyle p_n^k$ appears

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

$\displaystyle \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 $\displaystyle d(m)(a_n+1)=d(n)$. Q.E.D.

Tonio

3. 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.