Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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


share|improve this question

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
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. –  geraldgreen Dec 8 '11 at 3:52
2  
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. –  tards Dec 8 '11 at 3:55
1  
@John.Mathew: You have stated well the argument for not doing an induction on $n$. –  André Nicolas Dec 8 '11 at 3:58
3  
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$. –  Arturo Magidin 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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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