Results 1 to 2 of 2

Math Help - Prove d(n) =< d(2^n - 1)

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    38

    Prove d(n) =< d(2^n - 1)

    Let d(n) denote the divisor function; that is, d(n) is the number of natural numbers dividing n. Prove d(n) \leq d(2^n - 1).

    I think there must be a trick that I'm missing. I've tried an inductive argument without success and know that d({p_1}^{e_1}\ldots{p_r}^{e_r}) = (e_1+1)\ldots(e_r+1) where n={p_1}^{e_1}\ldots{p_r}^{e_r} is the prime factorisation of n, but I can't get anything to work. Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Boysilver View Post
    Let d(n) denote the divisor function; that is, d(n) is the number of natural numbers dividing n. Prove d(n) \leq d(2^n - 1).

    I think there must be a trick that I'm missing. I've tried an inductive argument without success and know that d({p_1}^{e_1}\ldots{p_r}^{e_r}) = (e_1+1)\ldots(e_r+1) where n={p_1}^{e_1}\ldots{p_r}^{e_r} is the prime factorisation of n, but I can't get anything to work. Thanks!
    Hint: If m divides n then 2^m-1 divides 2^n-1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove a(AB)=(aA)B=A(aB) ..
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 29th 2010, 04:14 AM
  2. Prove: f is one-to-one iff f is onto
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: June 25th 2010, 10:02 AM
  3. Replies: 2
    Last Post: August 28th 2009, 02:59 AM
  4. Please prove
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: April 7th 2009, 01:58 PM
  5. Prove this .
    Posted in the Math Topics Forum
    Replies: 5
    Last Post: February 18th 2009, 04:09 AM

Search Tags


/mathhelpforum @mathhelpforum