Additional Examples of Calculating d (n) for Large Integers

# Additional Examples of Calculating d(n) for Large Integers

We are now going to look at some examples of calculating d(n) (the number of positive divisors of n). Before we look at these examples, recall that for any prime p, $d(p^n) = n + 1$. Additionally, recall that d is a multiplicative function, and hence if $n = p_1^{e_1}p_2^{e_2}...p_k^{e_k}$, then $d(n) = d(p_1^{e_1})d(p_2^{e_2})...d(p_k^{e_k})$. We now have all of the tools we need.

## Example 1

Calculate d(12322).

We first note that the prime power decomposition of $12322 = 2 \cdot 61 \cdot 101$. Hence it follows that:

(1)
\begin{align} d(12322) = d(2) d(61) d(101) \\ d(12322) = (2)(2)(2) \\ d(12322) = 8 \end{align}

## Example 2

Calculate d(88888).

The prime power decomposition of $88888 = 2^3 \cdot 41 \cdot 271$. Hence it follows that:

(2)
\begin{align} d(88888) = d(2^3) d(41) d(271) \\ d(88888) = (4)(2)(2) \\ d(88888) = 16 \end{align}

## Example 3

Calculate d(500000).

The prime power decomposition of $500000 = 2^5 \cdot 5^6$. Hence it follows that:

(3)
\begin{align} d(500000) = d(2^5) d(5^6) \\ d(500000) = (6)(7) \\ d(500000) = 42 \end{align}

## Example 4

Calculate d(32930020).

The prime power decomposition of $32930020 = 2^2 \cdot 5 \cdot 17 \cdot 23 \cdot 4211$. Hence it follows that:

(4)
\begin{align} d(32930020) = d(2^2) d(5) d(17) d(23) d(4211) \\ d(32930020) = (3)(2)(2)(2)(2) \\ d(32930020) = 48 \end{align}

## Example 5

Calculate d(9876543210).

The prime power decomposition of $9876543210 = 2 \cdot 3^2 \cdot 5 \cdot 17^2 \cdot 379721$. Hence it follows that:

(5)
\begin{align} d(9876543210) = d(2) d(3^2) d(5) d(17^2) d(379721) \\ d(9876543210) = (2)(3)(2)(3)(2) \\ d(9876543210) = 72 \end{align}

## Example 6

Suppose p is a prime. For what primes p does $p \cdot d(p) ≥ p^2$ ?

We must first note that $d(p) = 2$ for all primes p. Hence we need to find primes p such that $2p ≥ p^2$. We note that this is only true when our prime p = 2, since $4 ≥ 4$. For all other primes, $2p ≤ p^2$. Hence p = 2 is our only solution to this problem.

## Example 7

Suppose that p and q are both prime. For what primes p and q does $pq \cdot d(pq) ≥ p^2q^2$?

Since p and q are both primes, it follows that $(p, q) = 1$, and hence $d(pq) = d(p)d(q) = (2)(2) = 4$. Hence we want to find primes p and q that are true for the inequality $4pq ≥ p^2 q^2$.

First, let's fix p = 2. Hence we want to solve the inequality that $8q ≥ 4q^2$, or more appropriately $2q ≥ q^2$. We've already solved this in example 6 though! Hence q = 2 is our only solution. So if p = 2 and q = 2, then $4pq ≥ p^2q^2$.

Now let's fix p = 3. Hence we now want to solve the inequality that $12q ≥ 9q^2$, or rather $4q ≥ 3q^2$. But if q is prime, then this is never true. In fact, $4pq ≥ p^2 q^2$ is ONLY true if both p and q are 2. Hence we have only one unique solution, that is (p, q) = (2, 2).

## Example 8

Suppose that p and q are both prime. For what values of p and q does $d(p^q) > d(q^p)$.

We note that since p and q are both primes, it follows that $d(p^q) = q + 1$ and $d(q^p) = p + 1$. Hence we want to find values of p and q that satisfy $q + 1 > p + 1$, which reduces down to $q > p$. Hence for all primes q > p, $d(p^q) > d(p^q)$.

## Example 9

Show that if d(n) is odd, then n is a square.

Each set of divisors of n come in pairs. If n is a square, then for some divisor d, d x d = n. But d is only present once in the list, and hence the sum of pairs + 1 will always be odd. Hence d(n) is odd if n is a square.

Alternatively, if n is a square, that $n = d^2$. Suppose the prime power decomposition of $d = p_1^{e_1}p_2^{e_2}...p_k^{e_k}$. It thus follows that $n = p_1^{2e_1}p_2^{2e_2}...p_k^{2e_k}$. Hence it follows that:

(6)
\begin{equation} d(n) = (2e_1 + 1)(2e_2 + 1)...(2e_k + 1) \end{equation}

Since all $2e_i + 1$ are odd, it thus follows that the product will also be odd, and hence $d(n)$ is odd too.