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

Printable View

August 25th 2010, 11:20 AM
Boysilver

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!
August 25th 2010, 11:40 AM
Opalg

Quote:

Originally Posted by Boysilver

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

All times are GMT -8. The time now is 04:27 PM.

Copyright © 2005-2014 Math Help Forum. All rights reserved.

Copyright © 2005-2014 Math Help Forum. All rights reserved.