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.

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
2  
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

3 Answers 3

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

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

share|improve this answer

HINT:

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

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.