Divisors of an Integer

Definition

What is a divisor of a number $N$? We say that $m$ is a divisor of $N$, if there exists an integer $k$ such that $N = km$.

In general, the divisors of a number refer to the positive divisors, unless otherwise noted. Since the negative divisors will be the negative of a positive divisor (and vice versa), we shall just consider positive divisors.

We also tend to ignore 0 the possibility for any of these numbers to be 0. Since $0 = 0 \times m$ our definition above gives us that every integer is a divisor of $0$.

Technique

Let the integer $N$ have a prime factorization $p_1 ^{q_1} p_2^{q_2} \ldots p_n ^ {q_n}$, where $p_1, p_2 \ldots , p_n$ are distinct prime numbers, and $q_1, q_2 \ldots q_n$ are positive integers. Let $d$ be a divisor of $N$; then any prime factor $p$ that divides $d$ must divide $N$, hence it must be one of $p_1, p_2, \ldots , p_n$.

Without loss of generality, set $p = p_i$. Let the highest power of $p$ that divides $d$ be $p_i^{r_i}$. Then, $p_i^{r_i}$ divides $d$, which in turn divides $N$, hence, $p_i^{r_i}$ must divide $p_i ^{q_i}$, which means that $r_i \leq q_i$. Thus, by considering all the prime factors of $d$, we get that it must have the form $d = p_1^{r_1} p_2^{r_2} \ldots p_n^{r_n}$ where $0 \leq r_i \leq q_i$ for all $i$.

Conversely, given a number $d$ that has the form $d = p_1^{r_1} p_2^{r_2} \ldots p_n^{r_n}$ where $0 \leq r_i \leq q_i$ for all $i,$ it is clear that $d$ is a divisor of $N$. As such, we have a complete classification of all the divisors.

Divisor Function

How many divisors does the number $N$ have? From the above classification, we can set up a direct bijection between $d = p_1^{r_1} p_2^{r_2} \ldots p_n^{r_n}$ and sets of $n$ integers $( r_1, r_2, \ldots r_n )$ that satisfy $0 \leq r_i \leq q_i$. For each $r_i$, there are $q_i - 0 + 1 = q_i + 1$ possibilities. Hence, by the product rule, there are going to be $(q_1 +1) (q_2 +1) \ldots (q_n + 1)$ divisors in all. The number of divisors of an integer $N$ is often denoted as the $\phi (N)$ or $\sigma_0 (N)$.

How many divisors does the number $2000$ have?

We have $2000 = 2^4 5^3$. Hence, from the above discussion, it has $(4+1)(3+1)=20$ divisors.

We can list them out as 1, 2, 4, 8, 16, 5, 10, 20, 40, 80, 25, 50, 100, 200, 400, 125, 250, 500, 1000, 2000.

(Can you see why we listed out the divisors this way, instead of in increasing order?)

What is the sum of all divisors of the number $2000$?

Consider the product $(1+2+2^2+2^3+2^4)(1+5+5^2+5^3)$ when expanded out. From the classification of the divisors, each divisor would appear exactly once as a term. Moreover, every term would be a divisor of the number $2000$. Hence the product represents the sum of all the divisors of the number $2000$, which is $31\times 156 = 4836$.

(Pop quiz: How would you generalize this to find the sum of all divisors of the number $N$? It is sometimes denoted as $\sigma (N)$ or $\sigma_1(N)$.)

Application and Extensions

Show that an integer $N$ has an odd number of divisors if and only if it is a perfect square.

Since $\phi(N) = (q_1 +1)(q_2+1) \ldots (q_n+1)$, this product is odd if and only if every term is odd, which happens if and only if every value $q_i$ is even, which happens if and only if $N$ is a perfect square.

What is the smallest integer $N$ that has exactly 14 divisors?

Since $14 = 2 \cdot 7$, an integer has exactly 14 divisors if it has the form $p^{13}$ or $p_1 \cdot p_2 ^6$. The smallest number in the first case and second case are, $2^{13} = 8192$ and $3 \cdot 2^6 = 192$, respectively. Hence 192 is the smallest integer that has exactly 14 divisors.