Multiplicative Arithmetic Functions

kyldn6 · #1 $Old$ November 2nd, 2009, 09:07 PM

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

tonio · #2 $Old$ November 3rd, 2009, 06:10 PM

Quote:

Originally Posted by kyldn6 $View Post$

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<a_i\in \mathbb{N}$ . 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\right)^{\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

kyldn6 · #3 $Old$ November 3rd, 2009, 08:47 PM

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.