Let $n$ be a positive integer. Show that $\tau (2^n − 1) \ge \tau (n)$, where $\tau (n)$ is the number of divisors of $n$ including $n$ itself and $1$. I just can not seem to figure this one out any help would be appreciated.
Showing that $\tau(2^n − 1) \ge \tau (n)$
1
$\begingroup$
elementary-number-theory
-
0@Victor: The question wasn't about $\tau$ being a multiplicative function. You just can't tag it with some property of $\tau$ like that. By the same logic, one can tag it as unbounded-function. Also, tags are supposed to be at the right level of specificity. Being too specific or too broad is not recommended. – 2012-03-02
1 Answers
4
For all positive integers $k$ and $\ell$, $2^{k\ell}-1=(2^k-1)(2^{k(\ell-1)}+2^{k(\ell-2)}+\cdots+2^k+1).$ So, if $k$ divides $n$, $2^k-1$ divides $2^n-1$. Therefore, $2^n-1$ must have at least as many divisors as $n$.
-
0Thanks a lot David that was really helpful. I knew that use of the geometric progression was important in figuring this out, but just could not see this simple result. – 2012-03-02