4
$\begingroup$

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!

  • 2
    Hint: How must a divisor of $p^m q^n$ look like? How many choices does this leave you?2011-12-19

3 Answers 3

1

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

2

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

  • 0
    Worth strong emphasis is that this depends crucially on **unique factorization**. Failing that there may be factorizations other than than those listed above.2011-12-19
2

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.

  • 0
    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\:.\:$2011-12-19