# Multiplication Rule, Proof by Induction, Divisors of (prime # to some power)*(prime # to some power)

Let $p_1, p_2, p_3, \cdots, p_m$ be distinct prime numbers and let $a_1, a_2, a_3, \cdots, a_m$ be positive integers. If $N = p_1^{a_1}\cdot p_2^{a_2}\cdot p_3^{a_3}\cdot\cdots\cdot p_m^{a_m}$, how many divisors does $N$ have? To prove a formula for this, you should use the multiplication rule and an induction proof.

So I found that for some prime number $p$ to some power $a$, there are $a + 1$ divisors. Example: $3^3 = 27$, divisors = $1, 3, 9, 27$, i.e., it has four divisors $(3 + 1)$.

For the inductive step, I have "assume $p_1^{a_1}\cdot p_2^{a_2}$ has $(a_1 + 1)\cdot(a_2 + 1)$ divisors. How should I include "a prime number to some power has that power $+ 1$ divisors"? Feeling stuck atm.

Wow. Not sure induction is necessary.

I'd say as $n= p_1^{a_1}p_2^{a_2}....p_m^{a_m}$ has only $p_1, ... p_m$ as prime factors all factors must be of the form $p_1^{k_1}.... p_m^{k_m}$ (where $k_i$ can be $0$) and that as $a_i$ is the highest power that of $p_i$ that can divide $n$ then each $k_i$ can be as little as $0$ and as high as $a_i$. There are $a_i+1$ options and so it is basic combinatorics that there are $(a_1 + 1).... (a_m+1)$ such factors.

That ought to be a good proof.

But if you want to (or are asked to do it) by induction:

Base case: The factors of $p^a$ are $1, p, p^2.... p^a$ and there are $a+1$ such factors.

Pf: $p$ is prime is indivisible so the only prime factors of $p^a$ is $p$ is every factor is a power of $p$. For any $k > a$, $p^k\not \mid p^a$ and for every $0\le k \le a$ then $p^k*p^{a-k} = p^a$ so all $p^k$ are factors and there are $a+1$ of them.

Inductive case: If $N= p_1^{a_1}.... p_m^{a_m}$ has $(a_1 + 1)....(a_m+1)$ factors and for $M=p_{m+1}^{a_{m+1}}$ has $a_{m+1}+1$ factors (as per base case), than $P=NM =p_1^{a_1}.... p_m^{a_m}p_{m+1}^{a_{m+1}}$ will have $(a_1 + 1)....(a_m+1)(a_{m+1}+1)$ factors.

Pf: $N$ and $M$ are relatively prime. Let $f$ be a factor of $NM$. Let $d=\gcd(N,f)$ and $c=\gcd(M,f)$. As $N$ and $M$ are relatively prime $f = dc$. So the only factors of $NM$ will be of the form $dc$ where $d|N$ and $c|M$ and every number of that form will be a factor.

As there are $(a_1 + 1)....(a_m+1)$ such $d$ and $a_{m+1} + 1$ such c. There are $(a_1 + 1)....(a_m+1)(a_{m+1}+1)$ such $cd$.

Prove a lemma that if $(m,n)=1$ then the number of divisors of $mn$ is the product of the number of divisors of $m$ and the number of divisors of $n$.

• Because not having any prime factors in common (e.g., gcd is 1) (a) is what you need for your case and (b) makes the maths work. If they are not relatively prime...say 6 and 10, you can see this doesn't work: 6 has 4 factors, and 10 has 4 factors, but 60 has only 12 factors, not 16. – C Monsour Apr 28 '18 at 4:57