Prime factorization, distinct primes

Question

Let $n=p^eq^f$ where $p$ and $q$ are distinct primes and $e$ and $f$ are positive integers.

Show that $n$ has $(e + 1)(f + 1)$ distinct factors in $N$, and that the sum of all these factors is $(p^{e+1} −1)(q^{f+1} −1) / (p − 1)(q − 1)$ (You may assume the uniqueness of prime factorization).

What if $n$ has more than two distinct prime factors? (Hint: you may wish to warm up by doing n = pe first.)

Sorry I have no idea where to start :(

Would doing $n=p^e$ first be easiest?

Answer 1

I'll do a warm up for you. Warm-ups help us understand the nature of a problem and how all of the relevant parts interact. Therefore when an exercise comes with warm-ups and you want to understand how to do the exercise, it's a good idea to try your hand at the warm-ups. Just for future reference. If you followed the directions and did work on the warm-up, then note you should talk about what you've tried and anywhere you got stuck whenever you post a question here.

Here are all factors of $648=2^33^4$

$$\begin{array}{|c|c|c|}\hline \color{Red}{2^0} \color{Blue}{3^0} & \color{Red}{2^1} 3^0 & \color{Red}{2^2}3^0 & \color{Red}{2^3} 3^0 \\ \hline 2^0 \color{Blue}{3^1} & 2^1 3^1 & 2^23^1 & 2^3 3^1 \\ \hline 2^0 \color{Blue}{3^2} & 2^13^2 & 2^23^2 & 2^3 3^2 \\ \hline 2^0 \color{Blue}{3^3} & 2^1 3^3 & 2^2 3^3 & 2^3 3^3 \\ \hline 2^0 \color{Blue}{3^4} & 2^1 3^5 & 2^23^4 & 2^3 3^4 \\ \hline \end{array}$$

Make sure you understand why the divisors can all be listed in this way (via prime factorization).

Homework.

1. How many columns are there (red)? How many rows are there (blue)? Entries total?
2. How are the number of rows and columns related to the powers of $2$ and $3$ in $648$?
3. Can you now argue why the number of divisors of $p^eq^f$ is $(e+1)(f+1)$?
4. Generalize to $p_1^{e_1}\cdots p_g^{e_g}$: how many divisors do you think it will have and why?
5. In the blanks below, fill each entry of the bottom row (except the last) with the sum of the divisors in that column, fill each entry of the right column (except the last) with the divisors of that row, and fill the corner in with the sum of all of the divisors of the whole array.
6. How would you sum $p^rq^0+p^rq^1+\cdots p^rq^f$ in general, where $r$ remains fixed? Or what about $p^0q^s+p^1q^s+\cdots+p^eq^s$ where $s$ remains fixed?
7. Write the sum of all divisors of $p^eq^f$ as a double summation. Evaluation the double summation using the geometric sum formula. Note $\sum_{i,j}a_ib_j=(\sum_ia_i)(\sum_jb_j)$.

$$\begin{array}{|c|c|c|c|}\hline \color{Red}{2^0} \color{Blue}{3^0} & \color{Red}{2^1} 3^0 & \color{Red}{2^2}3^0 & \color{Red}{2^3} 3^0 & \phantom{--} \\ \hline 2^0 \color{Blue}{3^1} & 2^1 3^1 & 2^23^1 & 2^3 3^1 \\ \hline 2^0 \color{Blue}{3^2} & 2^13^2 & 2^23^2 & 2^3 3^2 \\ \hline 2^0 \color{Blue}{3^3} & 2^1 3^3 & 2^2 3^3 & 2^3 3^3 \\ \hline 2^0 \color{Blue}{3^4} & 2^1 3^5 & 2^23^4 & 2^3 3^4 \\ \hline \phantom{r} \\ \hline \end{array}$$

Answer 2

OK, suppose $n=3^4\cdot 5^2$.

Then a factor will be $3^j\cdot 5^k$, where $j\in\{0,1,2,3,4\}$ and $k\in\{0,1,2\}$.

So the question is: How many ways are there to choose one member of $\{0,1,2,3,4\}$ and one member of $\{0,1,2\}$?