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

  • 1
    $\begingroup$ 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. $\endgroup$ Dec 8 '11 at 3:52
  • 3
    $\begingroup$ 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. $\endgroup$
    – tards
    Dec 8 '11 at 3:55
  • 2
    $\begingroup$ @John.Mathew: You have stated well the argument for not doing an induction on $n$. $\endgroup$ Dec 8 '11 at 3:58
  • 5
    $\begingroup$ 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$. $\endgroup$ 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.