Calculating $\tau(n)$, the number of positive divisors of $n \in \mathbb N$

Question

So I have these parts to this problem:

If $n \in \mathbb N$, then let $\tau(n)$ be the number of positive divisors of $n$. For example, $\tau(6) = 4$.

(a) If $n= p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}$ where $p_i$ are distinct primes and $a_i\in \mathbb N$, then prove that the number of positive divisors of $\tau(n)=(a_1+1)(a_2+1)\ldots(a_k+1)$.

(b) Find the number of positive divisors of $1,\!633,\!500$.

(c) Prove or disprove that $\tau(nm) = \tau(n)\tau(m)$ for all $m$, $n\in \mathbb N$.

I'm not sure how to prove part a. For part b, I know I can just do a series of divisions to find that answer, so I got $2^2\times 5^3\times 3^3\times11^2$ for the divisors, so I think $\tau(1,\!633,\!500)$ would be 4 in this case. For part c, I think I can do a counterexample of 4 and 6, where $\tau(4)=3$, and $\tau(6)=4$, but $\tau(24)$ is not equal to 12, which is $\tau(4)\tau(6)$, if I did my math right.

So, can anyone help me on part a and tell me if I am doing b and c wrong?

Answer 1

In (a) you can write each positive divisor uniquely in the form

$$p_1^{\ell_1}p_2^{\ell_2}\ldots p_k^{\ell_k}\;,$$

where $\ell_i\in\{0,1,\ldots,a_i\}$ for $i=1,\ldots,k$. Choosing a positive divisor amounts to choosing the exponents $\ell_1,\ldots,\ell_k$; in how many ways can that be done?

Your answer to (b) is way off, partly because you did not in fact apply the formula, and partly because you didn’t finish decomposing $1,633,500$ as a product of powers of distinct primes.

Your answer to (c) is fine.

Answer 2

Hint: try to prove that $\tau$ is multiplicative, that is if $m,n$ are relatively prime positive integers, then $\tau(mn)=\tau(m)\tau(n)$. This reduces to calculating $\tau$ for prime powers, $\tau(p^k)=k+1$, where $p$ is prime.

Answer 3

A few hints (for a more number theoretic approach):

1. $\tau(n) = \displaystyle\sum_{d \mid n}1$
2. If $a, b$ are coprime, then $$\begin{align}\tau(ab) &= \sum_{d\mid ab}1\\&=\sum_{d\mid a , \ d' \mid b}1\quad\text{since $a, b$ are coprime}\\&=\sum_{d\mid a}1\sum_{d'\mid b}1 = \tau(a)\tau(b)\end{align}$$Hence, it is sufficient only to calculate $\tau$ for prime powers. (Does this hold if $a,b$ are not coprime?)
3. If $p$ is prime and $k \in \mathbb N$, then the divisors of $p^k$ are exactly the powers of $p$ less than $p^k$. How many of these are there?

Answer 4

Look at our number $n=p_1^{a_1}\cdots p_k^{a_k}$. For the sake of concreteness, let $n=3^4\cdot 7^2 \cdot 13^1\cdot 19^2$.

The positive divisors of $n$ are the numbers $3^a\cdot 7^b\cdot 13^c\cdot 19^d$, where $0\le a\le 4$, $0\le b\le 2$, $0\le c\le 1$, and $0\le d\le 2$.

We are making a positive divisor $m$ of $n$. How many $3$'s will $m$ have? That is, what are the possibilities for $a$? It could be $0$ ($m$ is not divisible by $3$), or $1$, or $2$, or $3$, or $4$, altogether $5$ choices, which it is convenient to call $4+1$.

For every decision about how many $3$'s $m$ will have, there are $2+1$ choices as to how many $7$'s $m$ will have. And for every decision about the $7$'s, there are $1+1$ possible decisions about the $13$'s, and $2+1$ decisions about the $19$'s, for a total of $(4+1)(2+1)(1+1)(2+1)$.

The general argument is the same.