Take the 2-minute tour ×

Am taking a intro discrete math course..it covers some number theory content Euclidean algorithm,modular arithmetic, Euler's phi function, that's all

How can I solve a question like this: If $p$ and $q$ are distinct primes, find the number of distinct divisors of $p^mq^n$.

what I did is plugin some prime number and observed that the number of divisor is $(m+1)(n+1）$

Is there a formal way to solve this based on the contents I mentioned?

Thanks for help!

share|improve this question
Hint: How must a divisor of $p^m q^n$ look like? How many choices does this leave you? –  Fredrik Meyer Dec 19 '11 at 21:01
add comment

3 Answers

up vote 2 down vote accepted

You want to produce a (positive) divisor of $p^mq^n$. By the Unique Factorization Theorem, aka the Fundamental Theorem of Arithmetic, this will be a number $d$ of the shape $p^aq^b$, where $0 \le a\le m$ and $0 \le b \le n$.

Imagine that we have a box that contains $m$ $p$'s, and next to it a box that contains $n$ $q$'s.

First we stop in front of the $p$-box, and decide how many $p$'s our divisor $d$ shall have. There are $m+1$ available options, namely $0, 1, \dots,m$.

Once we have decided on the number of $p$'s, move over to the $q$-box. For every choice of how many $p$'s the divisor $d$ shall have, there are $n+1$ ways to decide how many $q$'s the divisor $d$ shall have. Thus the total number of choices is $(m+1)(n+1)$.

Comment: Let $N=p_1^{m_1}p_2^{m_2}\cdots p_k^{m_k}$, where the $p_i$ are distinct primes. Using basically the same argument, we can show that $N$ has $(p_1+1)(p_2+1)\cdots(p_k+1)$ positive divisors.

share|improve this answer
But the most nontrivial part of the proof is the unsubstantiated claim in your second sentence, about the possible factors of $p^a q^b$. The rest is, of course, trivial. –  Bill Dubuque Dec 19 '11 at 23:01
@Bill Dubuque: I agree that the structure of the factors, in certain contexts, requires proof. However, for a couple of millenia, people, including Fermat, Euler, and Legendre, did not prove the Unique Factorization Theorem, not because they couldn't have, but because it did not occur to them that there might be an issue. –  André Nicolas Dec 19 '11 at 23:14
And, as emphasized by Gauss, many of those "proofs" were inadequate. The above-suggested "proof" makes no use of the essential hypothesis that $\rm\:p,q\:$ are prime so it is either incomplete or incorrect, since the result is false for $\rm\:p,q\:$ not prime. –  Bill Dubuque Dec 19 '11 at 23:17
@Bill Dubuque: Edited to mention Unique Factorization. –  André Nicolas Dec 19 '11 at 23:22
Great, Gauss would be pleased! It might help to say "by uniqueness of prime factorizations" so to make explicit where the hypothesis on primality is invoked. Note that products of primes factor uniquely in any domain (but products of irreducibles need not). Its the primality of irreducibles that yields uniquness, i.e. $\rm\ p\ |\ ab\ \Rightarrow\ p\ |\ a\ \ or\ \ p\ |\ b\:.\:$ –  Bill Dubuque Dec 19 '11 at 23:23
add comment


$$\begin{array}{r|cc} &1&q&q^2&q^3&q^4&\dots&q^n\\ \hline 1&1&q&q^2&q^3&q^4&\dots&q^n\\ p&p&pq&pq^2&pq^3&pq^4&\dots&pq^n\\ p^2&p^2&p^2q&p^2q^2&p^2q^3&p^2q^4&\dots&p^2q^n\\ p^3&p^3&p^3q&p^3q^2&p^3q^3&p^3q^4&\dots&p^3q^n\\ p^4&p^4&p^4q&p^4q^2&p^4q^3&p^4q^4&\dots&p^4q^n\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\ p^m&p^m&p^mq&p^mq^2&p^mq^3&p^mq^4&\dots&p^mq^n \end{array}$$

share|improve this answer
Worth strong emphasis is that this depends crucially on unique factorization. Failing that there may be factorizations other than than those listed above. –  Bill Dubuque Dec 19 '11 at 21:51
add comment

Hint: start with the question of how many divisors $p^m$ has.

share|improve this answer
add comment

Your Answer


