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

  • 1
    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.2011-12-08
  • 3
    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.2011-12-08
  • 2
    @John.Mathew: You have stated well the argument for *not* doing an induction on $n$.2011-12-08
  • 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$.