Math Core

How many divisors does $10!$ have? What is the sum of the divisors of $300$ that are multiples of $5$ ? What is the smallest number with $24$ divisors? These questions all come down to the prime factorization and one structural fact: divisor functions are multiplicative, so you can work one prime at a time.

Counting and adding divisors

Every divisor of $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ has the form $p_1^{a_1} \cdots p_k^{a_k}$ with $0 \le a_i \le e_i$ , and different exponent choices give different divisors (unique factorization). That gives both formulas below.

Divisor count and divisor sum

For $n = p_1^{e_1} \cdots p_k^{e_k}$ :

$d(n) = (e_1 + 1)(e_2 + 1)\cdots(e_k + 1),$

$\sigma(n) = \prod_{i=1}^{k}\left(1 + p_i + p_i^2 + \cdots + p_i^{e_i}\right) = \prod_{i=1}^{k} \frac{p_i^{e_i + 1} - 1}{p_i - 1}.$

Why the sum formula works. Expand the product $\prod (1 + p_i + \cdots + p_i^{e_i})$ . Each term of the expansion picks one power $p_i^{a_i}$ from each factor and multiplies them, which is exactly one divisor. Every divisor appears exactly once. So the expansion is the sum of all divisors.

The same "expand a product" idea lets you sum any restricted set of divisors. For divisors that are multiples of $5$ , use $(5 + 25 + \cdots)$ in the $5$ -factor instead of $(1 + 5 + 25 + \cdots)$ . For odd divisors, drop the $2$ -factor entirely.

Multiplicativity

Definition

Multiplicative function

A function $f$ on positive integers is multiplicative if $f(mn) = f(m) f(n)$ whenever $\gcd(m, n) = 1$ .

$d$ , $\sigma$ and $\varphi$ are all multiplicative: when $\gcd(m, n) = 1$ , each divisor of $mn$ splits uniquely as (divisor of $m$ ) times (divisor of $n$ ). So to compute one of them, compute it on each prime power and multiply.

Product of divisors

Pair each divisor $t$ of $n$ with $n/t$ . Each pair multiplies to $n$ , so

$\prod_{t \mid n} t = n^{d(n)/2}.$

(When $n$ is a perfect square, $\sqrt n$ pairs with itself and the formula still holds.)

Parity facts

$d(n)$ is odd exactly when $n$ is a perfect square: divisors pair up as $t \leftrightarrow n/t$ except $\sqrt n$ .
$\sigma(n)$ is odd exactly when $n$ is a square or twice a square. For odd $p$ , $1 + p + \cdots + p^e$ has $e + 1$ odd terms, so it's odd iff $e$ is even. The factor for $p = 2$ is always odd.

Perfect and abundant numbers

$n$ is perfect if $\sigma(n) = 2n$ and abundant if $\sigma(n) > 2n$ . The ratio $\dfrac{\sigma(n)}{n} = \sum_{t \mid n} \dfrac{1}{t}$ is also multiplicative, and for a prime power it is less than $\dfrac{p}{p-1}$ . This is the tool for abundance questions.

Euclid showed that if $2^k - 1$ is prime then $2^{k-1}(2^k - 1)$ is perfect: $\sigma = (2^k - 1) \cdot 2^k = 2 \cdot 2^{k-1}(2^k - 1)$ . Euler proved every even perfect number has this form: $6, 28, 496, 8128, \dots$

Worked example: Counting divisors

How many positive divisors does $2026^3$ have?

$2026 = 2 \cdot 1013$ with $1013$ prime, so $2026^3 = 2^3 \cdot 1013^3$ and $d = 4 \cdot 4 = 16$ .

Worked example: Smallest number with a given divisor count

Find the smallest positive integer with exactly $12$ divisors.

Write $12$ as a product of factors $e_i + 1$ : $12$ , $6 \cdot 2$ , $4 \cdot 3$ , $3 \cdot 2 \cdot 2$ . Give the largest exponents to the smallest primes:

$2^{11} = 2048$ , $\ 2^5 \cdot 3 = 96$ , $\ 2^3 \cdot 3^2 = 72$ , $\ 2^2 \cdot 3 \cdot 5 = 60$ .

The smallest is $60$ .

Worked example: Counting lcm pairs

How many ordered pairs $(a, b)$ of positive integers have $\operatorname{lcm}(a, b) = 2^3 \cdot 5^2$ ?

Work one prime at a time. For $2$ : exponents $(i, j)$ with $\max(i, j) = 3$ and $0 \le i, j \le 3$ . There are $4^2 - 3^2 = 7$ such pairs. For $5$ : $3^2 - 2^2 = 5$ . In general a prime power $p^e$ contributes $2e + 1$ . The answer is $7 \cdot 5 = 35$ .

Worked example: Divisors of a square

For $n = 2^4 \cdot 3^2$ , how many divisors of $n^2$ are less than $n$ ?

$n^2 = 2^8 \cdot 3^4$ has $9 \cdot 5 = 45$ divisors. They pair up as $t \leftrightarrow n^2/t$ , one smaller than $n$ and one larger, except $t = n$ . So $\frac{45 - 1}{2} = 22$ are less than $n$ .

Common mistake

To minimize a number with a given divisor count, don't automatically use the most primes. Compare every factorization of the count, as in the example: $2^2 \cdot 3 \cdot 5 = 60$ beats $2^3 \cdot 3^2 = 72$ here, but for $d = 8$ , $2^3 \cdot 3 = 24$ beats $2 \cdot 3 \cdot 5 = 30$ .