Finding all the divisors

In this post, we are going to search the all the divisors of an integer, as a warm-up before studying factorizing techniques (see the following posts). A number n is said to be factorized into primes if we can find all of its prime factors (called \(q_0\), \(q_1\)….) and their exponents (\(\alpha_0\), \(\alpha_1\)…). Then we can write \[n = q_0^{\alpha_0}q_1^{\alpha_1}q_2^{\alpha_2}... \] The number of all divisors will then be the product of the powers +1 (the demonstration is easy, see the next part): \[\sigma_0 = (\alpha_0+1)(\alpha_1+1)(\alpha_2+1)... \] Let us take an example. The prime factors of 24 are 2 and 3 so if we decompose it into primes : \[ 24 = 2^3 \cdot 3\] The number of divisors is \((3+1).(1+1) = 8\).

Now that we have this factorization, finding all the divisors is just a matter of trying all the possible combinations of the prime factors. In our example, its divisors are : 1,2,3,4,6,8,12,24 so eight in total.

Beware : 1 and the number itself are counted as divisors !

Divisor function For proving the number of divisors is the product of the powers+1, let us examine the number of divisors. We will use a function called the divisor function. It is defined at the sum of all the divisors of our number (let us call it n) at a given power (for example k), noted as \(\sigma_k(n)\).

If we choose \(k=0\), we get what we want : the divisor function is then simply the sum of the divisors (because a number at the power 0 is 1, and there are as many 1 as there are divisors).

Now, the divisors of \(q_0^{\alpha_0}\) are only the powers of \(q_0\) (as it is prime). Thus there are \(\alpha_0 + 1\) divisors.

Finally, we just have to see that (the number of divisors of a product is the product of the number of the divisors of each term) : \[\begin{aligned} \sigma_0(n) &= \sigma_0 (q_0^{\alpha_0}q_1^{\alpha_1}q_2^{\alpha_2})\\ &= \sigma_0(q_0^{\alpha_0}) \sigma_0(q_1^{\alpha_1}) \sigma_0(q_2^{\alpha_2}) \end{aligned}\] And using the previous remark, we find that \[ \sigma_0(n) = (\alpha_0+1)(\alpha_1+1)(\alpha_2+1)...\]