Results 1 to 6 of 6

Math Help - Number of Positive Divisors

  1. #1
    Member
    Joined
    Dec 2009
    Posts
    224

    Number of Positive Divisors

    If d(n) denotes the number of divisors (+ve) of integer n. Prove that d(n) \leq 2 \sqrt{n}.

    So, we are not told if n is prime or composite, so I don't know how to approach this proble. But if we suppose the prime factorization of n is n=p_1^{\alpha_1} p_2^{\alpha_2}...p_r^{\alpha_r},

    then number of divisors of n are: d(n)=(\alpha +1)...(\alpha_r+1).

    So, how do I show that d(n)=(\alpha +1)...(\alpha_r+1) \leq 2 \sqrt{n}?

    I also know that if n is composite then the number of its divisors are less than or equal to \left\lfloor \sqrt{n} \right\rfloor (the notation means the integer part of \sqrt{n}), but I don't know if that helps at all.

    Any helps is really appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Consider the pairs \left(d, \tfrac{n}{d} \right) for the divisors d\leq \sqrt{n} and show that each divisor must appear as one -at least one- of the entries at some pair. (consider the cases \text{divisor}\leq \sqrt{n} and \text{divisor}\geq \sqrt{n} )

    Can you finish the proof?

    PS: For a composite, the number of divisors need not be less or equal to \sqrt{n} as you stated, rather the smallest divisor ( > 1) must be less or equal than \sqrt{n}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by demode View Post
    If d(n) denotes the number of divisors (+ve) of integer n. Prove that d(n) \leq 2 \sqrt{n}.

    So, we are not told if n is prime or composite, so I don't know how to approach this proble. But if we suppose the prime factorization of n is n=p_1^{\alpha_1} p_2^{\alpha_2}...p_r^{\alpha_r},

    then number of divisors of n are: d(n)=(\alpha +1)...(\alpha_r+1).

    So, how do I show that d(n)=(\alpha +1)...(\alpha_r+1) \leq 2 \sqrt{n}?

    I also know that if n is composite then the number of its divisors are less than or equal to \left\lfloor \sqrt{n} \right\rfloor (the notation means the integer part of \sqrt{n}),


    This is false: 36 has 9 positive divisors, and 9>6=\sqrt{36} . What did you really mean here?

    Tonio




    but I don't know if that helps at all.

    Any helps is really appreciated.
    .
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Dec 2009
    Posts
    224
    Quote Originally Posted by PaulRS View Post
    Consider the pairs \left(d, \tfrac{n}{d} \right) for the divisors d\leq \sqrt{n} and show that each divisor must appear as one -at least one- of the entries at some pair.
    I didn't understand this line very well. Could you please explain a bit more clearly what I need to be doing? And why are you considering the pairs (d,d/n)?

    Quote Originally Posted by Tonio
    This is false: 36 has 9 positive divisors, and . What did you really mean here?
    Oops I made a mistake, I meant that the smallest prime divisor of a composite number n is less than or equal to .
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Dec 2009
    Posts
    224
    Quote Originally Posted by PaulRS View Post
    Consider the pairs \left(d, \tfrac{n}{d} \right) for the divisors d\leq \sqrt{n} and show that each divisor must appear as one -at least one- of the entries at some pair. (consider the cases \text{divisor}\leq \sqrt{n} and \text{divisor}\geq \sqrt{n} )

    Can you finish the proof?
    Why do you consider the pairs only for divisors such that d\leq \sqrt{n}? We don't care about the size of the divisors, only the number of divisors. The question only asks for the number of divisors, that's what the notation d(n) means. Furthermore I'm not sure how to prove that at least one of the divisors must appear in those pairs...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    I meant to say that the set of positive integers dividing n can be written as: \left \{ x \in \mathbb{Z}^+ | x \text{ divides } n  \right \} = \displaystyle\bigcup_{d |n \text{ and } 1\leq d \leq \sqrt{n}  } \left \{ d, \displaystyle\frac{n}{d} \right \} (*)

    And clearly we have \displaystyle\bigcup_{d |n \text{ and } 1\leq d \leq \sqrt{n}  } \left \{ d, \displaystyle\frac{n}{d} \right \} \subseteq \bigcup_{d = 1}^{\lfloor \sqrt{n} \rfloor} \left \{ d, \displaystyle\frac{n}{d} \right \} and here the cardinal of the RHS is no more than 2\cdot \sqrt{n}

    The key to (*) is noting that:
    Any divisor which is less or equal to \sqrt{n} appears on the RHS, now suppose k were a divisor of n greater than \sqrt{n}, in this case we have that k\cdot \tfrac{n}{k} = n and so \tfrac{n}{k} is a divisor of n but \tfrac{n}{k} <\sqrt{n} thus we have the set \left \{ \frac{n}{k}, k \right \} as one of the terms of the union.
    That proves that the LHS is a subset of the RHS, but of course if d is a divisor of n, then so is n/d and so ths RHS is a subset of the LHS.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of positive divisors of n
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: August 17th 2011, 11:04 AM
  2. How many positive divisors of n^2...
    Posted in the Algebra Forum
    Replies: 3
    Last Post: December 19th 2010, 08:52 PM
  3. Running Through Positive Divisors
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: February 4th 2010, 09:28 AM
  4. Positive divisors
    Posted in the Algebra Forum
    Replies: 8
    Last Post: January 26th 2010, 05:36 AM
  5. positive integral divisors
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: September 10th 2009, 03:54 PM

Search Tags


/mathhelpforum @mathhelpforum