# Prove a property of divisor function

Let $n$ be a positive natural number whose prime factorization is $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$, where $p_i$ are natural distinct prime numbers, and $a_i$ are positive natural numbers.

Using induction to show that the number of divisors of $n$ is $$(a_1+1)(a_2+1)\cdots(a_k+1)$$

Hint: Instead of inducting on $n$ consider inducting on $k$.

• but how can we induce on $k$ since if $n$ is a prime, $n+1$ could be a composite number which certainly changes a lot in its prime factorization. Dec 8 '11 at 3:52
• Check that if $n = p_1^{a_1}$ it has $a_1 +1$ factors. Make the suitable assumption for $n = p_1^{a_1} ...p_{k-1}^{k-1}$ and show what you have to. Dec 8 '11 at 3:55
• @John.Mathew: You have stated well the argument for not doing an induction on $n$. Dec 8 '11 at 3:58
• Generally speaking, regular induction is not very good for dealing with "divisor" questions directly, because it is very hard to relate the divisors of $n$ to the divisors of $n+1$. One can use so-called "strong induction", however: assume the result holds for all integers strictly less than $n$, and prove that it holds for $n$. Dec 8 '11 at 3:58

Hint $\# 2$: tards answer might be a simpler way to go, but here is an alternative route:

Let $d(n)$ denote the number of divisors of the integer $n$. Show that $$\gcd(m,n) = 1 \quad \implies \quad d(mn) = d(m)d(n).$$ Such functions are called multiplicative functions. Then just show that $$d(p^{\alpha}) = \alpha+1.$$

One observation to help help prove that $d(mn) = d(m) d(n)$, whenever $\gcd(m,n) =1$:

If $a \mid mn$ and $\gcd(a,m) = 1$, then it must be that $a \mid n$.