2
$\begingroup$

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


2 Answers 2

4

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

  • 4
    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$.2011-12-08
1

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