The Number of Positive Divisors of an Integer

We will now begin to look at some very important functions in number theory. The first is the number of positive divisors function which we define below.

Definition: Let $n \in \mathbb{Z}$. The function $d : \mathbb{Z} \to \mathbb{N}$ defined by $\displaystyle{d(n) = \sum_{d \mid n}_{d > 0} 1}$ is the Number of Positive Divisors Function.

For conventional purposes we define $d(0) = \infty$. Furthermore, note that $d(n) = d(-n)$ for all $n \in \mathbb{Z}$, so we will often times only make mention of $d(n)$ for $n \in \mathbb{N}$.

For example, let $n = 18$. Then the positive divisors of $n$ are $1$, $2$, $3$, $6$, $9$, and $18$. There are $6$ of them, and so $d(18) = 6$.

We will now look at some results regarding the number of positive divisors of an integer.

Proposition 1: Let $p \in \mathbb{N}$. Then $p$ is prime if and only if $d(p) = 2$.

• Proof: $\Rightarrow$ Suppose that $p$ is prime. Then the only positive divisors of $p$ are $1$ and $p$ by definition, so $d(p) = 2$.

• $\Leftarrow$ Conversely, suppose that $d(p) = 2$. Then we must have that $1$ and $p$ are the only divisors of $p$, i.e., $p$ is prime. $\blacksquare$

Proposition 2: Let $p \in \mathbb{N}$ be a prime number. Then $d(p^2) = 3$.

• Proof: Let $p$ be prime. Then the positive divisors of $p^2$ are $1$, $p$, and $p^2$ (all of which values are distinct) and there exists no other positive divisors since $p^2$ can be factored into $p^2 = p \cdot p$ and we have already covered all divisors of the factors of $p^2$. So $d(p^2) = 3$. $\blacksquare$

Proposition 3: Let $p \in \mathbb{N}$ be a prime number. Then for all $n \in \mathbb{N}$, $d(p^n) = n + 1$.

• Proof: Use Proposition 2 and carry out by induction. $\blacksquare$

Proposition 4: Let $p, q \in \mathbb{N}$ be prime numbers. Then $d(pq) = d(p)d(q)$.

• Proof: Let $p, q \in \mathbb{N}$ be prime. Then the positive divisors of $pq$ are $1$, $p$, $q$, and $pq$, so $d(pq) = 4$. But by Proposition 1, since $p$ and $q$ are prime we have that $d(p) = d(q) = 2$, so indeed:

(1)

\begin{align} \quad d(pq) = d(p)d(q) \quad \blacksquare \end{align}

Proposition 5: Let $n \in \mathbb{N}$, $n > 1$, and let $n = p_1^{e_1}p_2^{e_2}...p_k^{e_k}$ be the prime power decomposition of $n$. Then $d(n) = d(p_1^{e_1})d(p_2^{e_2})...d(p_n^{e_n})$.

• Proof: Use Proposition 4 and carry out by induction. $\blacksquare$