$ \tau(a)$-function for the number of divisors

154 Views Asked by At

Given a number $a$ with prime decomposition $p_1^{x_1}p_2^{x_2}\cdots p_m^{x_m}$ (with $x_i \in \Bbb N$ and $p_i \neq p_j$ if $i \neq j$).

How can you proof that the number of divisors of $a$ is $ \tau(a) = (x_1 + 1)(x_2+1)\cdots (x_m + 1)$?

You know that each factor $p_m^{x_m}$ has $x_m+1$ divisors: $1, p, p^2, ...p^{x_m+1}$

1

There are 1 best solutions below

0
On BEST ANSWER

We are counting the divisors of $$p_1^{x_1}p_2^{x_2}\cdots p_m^{x_m}$$

Note that in order to find a divisor you pick a prime factor and a power for that prime factor.

For each prime factor $p_i$ we have $1+x_i$ choices where the $1$ is for the case that you do not pick that particular prime number.

Thus the total number of choices are $ \tau(a) = (x_1 + 1)(x_2+1)\cdots (x_m + 1)$