1
$\begingroup$

I need to prove the following by induction:

Let $p_{1}$, $p_{2}$, $p_{3}$, $...$, $p_{m}$ be distinct primes.

Let $a_{1}$, $a_{2}$, $a_{3}$, $...$, $a_{m}$ be positive integers.

Suppose the following...

\begin{equation} N = (p_{1})^{a_{1}} * (p_{2})^{a_{2}} * (p_{3})^{a_{3}} * ... * (p_{m})^{a_{m}} \end{equation}

How many divisors does $N$ have?


I thought about it, and concluded that given that we're working with distinct primes, the following is true:

\begin{equation} \# \hspace{.2cm}of\hspace{.2cm} Divisors\hspace{.2cm} of\hspace{.2cm} N = (a_{1} + 1) + (a_{2} + 1) + (a_{3} + 1) + ... + (a_{m} + 1) \end{equation}

The problem is that I haven't done a proof by induction in a long time, and I think that I remember how to do it once I have the closed form, but I'm not sure how to turn the above equation into a closed form solution.

I vaguely remember using summation notation to get closed form solutions, so I attempted to turn this into a summation as well (which I may have done incorrectly):

\begin{equation} \# \hspace{.2cm}of\hspace{.2cm} Divisors\hspace{.2cm} of\hspace{.2cm} N = (\sum_{i = 1}^{m} a_{i}) + m \end{equation}

I also know that the closed form of $(\sum_{i = 1}^{n} i)$ is ${[n(n+1)]}\div{2}$, but I'm not sure if the index numbers $1 - n$ have to be consecutive in order for that to work, and they aren't necessarily consecutive in this particular case.

Any help would be hugely appreciated.

$\endgroup$
2
$\begingroup$

Pretty sure the answer is actually:

$\Pi_{i=1}^{m} (a_m + 1)$

i.e., product instead of sum.

For example, if m=2 and the p values are 2 and 3 and the a values are 2 and 2, you get N=36, which has 9 divisors (3 times 3), not 6 divisors (3 plus 3).

These divisors are: 1, 2, 4, 3, 6, 12, 9, 18, 36

$\endgroup$
  • $\begingroup$ You're right, my mistake. Thank you! How do you find the closed form for product notation..? $\endgroup$ – BabaSvoloch Apr 27 '17 at 21:04
  • $\begingroup$ This is already in closed form... I'll let you work out the proof... wouldn't want to have all the fun. $\endgroup$ – Jed Apr 27 '17 at 21:25

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.