Results 1 to 3 of 3

Math Help - Multiplicative Arithmetic Functions

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    12

    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).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    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\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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    Posts
    12
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Arithmetic functions
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 22nd 2010, 02:29 PM
  2. [SOLVED] Squarefree and Multiplicative Functions
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: December 13th 2008, 08:31 PM
  3. Arithmetic Functions
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 4th 2008, 01:53 PM
  4. Arithmetic Functions.
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 5th 2008, 02:50 PM
  5. Number Theory - Multiplicative Functions
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: August 9th 2007, 09:09 AM

Search Tags


/mathhelpforum @mathhelpforum