1
$\begingroup$

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.

  • 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 1

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

  • 0
    Thanks 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