Application - Count and Sum An Integer's Divisors Basic

Video tutorial

Lecture Notes

Even though this is a typical number theory problem, this can also be solved with basic counting principles.

Given a positive integer $N$ whose prime factorization is $N=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$, then the number of $N$'s divisors is $$(a_1+1)(a_2+1)\cdots(a_k+1)$$

A slightly more challenging and related question is to find the sum of all these divisors. The result is $$\left(1+p_1+p_1^2+\cdot+p_1^{a_1}\right)\left(1+p_2+p_2^2+\cdot+p_2^{a_2}\right)\cdots\left(1+p_k+p_k^2+\cdot+p_k^{a_k}\right)$$

Examples

 (2481) How many positive divisors does $20$ have?