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?


Assignment >>>
Comments

Note that the way to find the sum of all divisors relies on the power of polynomial expansion.

Polynomial expansion is also the core of the powerful Generating Function method. We also cover the Generating Function in the course 25 - Advanced Combinatorics.