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

• Aug 25th 2010, 11:20 AM
Boysilver
Prove d(n) =< d(2^n - 1)
Let $\displaystyle d(n)$ denote the divisor function; that is, $\displaystyle d(n)$ is the number of natural numbers dividing $\displaystyle n$. Prove $\displaystyle 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 $\displaystyle d({p_1}^{e_1}\ldots{p_r}^{e_r}) = (e_1+1)\ldots(e_r+1)$ where $\displaystyle n={p_1}^{e_1}\ldots{p_r}^{e_r}$ is the prime factorisation of $\displaystyle n$, but I can't get anything to work. Thanks!
• Aug 25th 2010, 11:40 AM
Opalg
Quote:

Originally Posted by Boysilver
Let $\displaystyle d(n)$ denote the divisor function; that is, $\displaystyle d(n)$ is the number of natural numbers dividing $\displaystyle n$. Prove $\displaystyle 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 $\displaystyle d({p_1}^{e_1}\ldots{p_r}^{e_r}) = (e_1+1)\ldots(e_r+1)$ where $\displaystyle n={p_1}^{e_1}\ldots{p_r}^{e_r}$ is the prime factorisation of $\displaystyle n$, but I can't get anything to work. Thanks!

Hint: If m divides n then $\displaystyle 2^m-1$ divides $\displaystyle 2^n-1$.