Math Core

On the AMC 10 and 12, "how many divisors" is only the warm-up. The real questions ask for the sum of the divisors, their product, divisors with a special property, or pairs of numbers with a given GCD and LCM. Every one of these is answered the same way: write the number as a product of prime powers and think about each prime separately.

Divisors are exponent choices

If $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ , then every divisor of $n$ looks like $p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ with $0 \le e_i \le a_i$ , and different exponent choices give different divisors. So a divisor is nothing more than a list of independent choices, one per prime. That single fact gives you all of the formulas below.

Counting. Prime $p_i$ has $a_i + 1$ exponent choices, so $d(n) = (a_1 + 1)(a_2 + 1)\cdots(a_k + 1)$ .
Restricted counting. To count divisors with a property (perfect square, multiple of $12$ , odd), restrict the exponent choices for each prime and multiply. A square divisor needs every exponent even; an odd divisor needs the exponent of $2$ to be $0$ .

The sum of the divisors

Expand the product

$(1 + 2 + 2^2 + 2^3)(1 + 3 + 3^2).$

Each term of the expansion picks one power of $2$ and one power of $3$ and multiplies them, so the expansion lists every divisor of $2^3 \cdot 3^2 = 72$ exactly once. The sum of the divisors of $72$ is $15 \cdot 13 = 195$ .

Divisor formulas

For $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ :

Number of divisors: $d(n) = (a_1 + 1)(a_2 + 1) \cdots (a_k + 1)$ .
Sum of divisors: $\sigma(n) = (1 + p_1 + \dots + p_1^{a_1}) \cdots (1 + p_k + \dots + p_k^{a_k})$ , and each factor equals $\dfrac{p_i^{a_i + 1} - 1}{p_i - 1}$ .
Product of divisors: $n^{d(n)/2}$ .

The product of the divisors

Divisors come in pairs $d$ and $\dfrac{n}{d}$ whose product is $n$ . There are $d(n)$ divisors, so there are $\dfrac{d(n)}{2}$ pairs and the product of all the divisors is $n^{d(n)/2}$ . This works even when $n$ is a perfect square: the middle divisor $\sqrt{n}$ pairs with itself and contributes $n^{1/2}$ , which is exactly what the formula gives.

GCD and LCM, one prime at a time

For each prime, $\gcd(a, b)$ uses the smaller exponent and $\operatorname{lcm}(a, b)$ uses the larger one. So if you know the LCM (or both the GCD and LCM), you can count pairs $(a, b)$ prime by prime:

If $\operatorname{lcm}(a, b)$ has $p^k$ , the exponents of $p$ in $a$ and $b$ are at most $k$ and at least one equals $k$ : that's $(k+1)^2 - k^2 = 2k + 1$ ordered choices.
If $\gcd(a, b)$ has $p^j$ and $\operatorname{lcm}(a, b)$ has $p^k$ with $j < k$ , one number gets $j$ and the other gets $k$ : $2$ ordered choices. If $j = k$ there is only $1$ .

Worked example: A sum of divisors

What is the sum of the positive divisors of $720$ ?

$720 = 2^4 \cdot 3^2 \cdot 5$ , so

$\sigma(720) = (1 + 2 + 4 + 8 + 16)(1 + 3 + 9)(1 + 5) = 31 \cdot 13 \cdot 6 = 2418.$

Worked example: Pairs with a given LCM

How many ordered pairs of positive integers $(a, b)$ have $\operatorname{lcm}(a, b) = 72$ ?

$72 = 2^3 \cdot 3^2$ . For the prime $2$ , the exponents in $a$ and $b$ lie in $\{0, 1, 2, 3\}$ with at least one equal to $3$ : $4^2 - 3^2 = 7$ choices. For the prime $3$ : $3^2 - 2^2 = 5$ choices. The primes are independent, so there are $7 \cdot 5 = 35$ ordered pairs.

Worked example: Divisors of the square

Let $n = 432 = 2^4 \cdot 3^3$ . How many positive divisors of $n^2$ are less than $n$ but do not divide $n$ ?

$n^2 = 2^8 \cdot 3^6$ has $9 \cdot 7 = 63$ divisors. Apart from $n$ itself, they pair up as $d$ and $\dfrac{n^2}{d}$ with exactly one of each pair below $n$ , so $\dfrac{63 - 1}{2} = 31$ divisors of $n^2$ are less than $n$ .

Every divisor of $n$ also divides $n^2$ . The number $n$ has $5 \cdot 4 = 20$ divisors, and $19$ of them are less than $n$ . So the answer is $31 - 19 = 12$ .

Worked example: Working backward from the product

The product of all the positive divisors of a positive integer $n$ is $2^{30} \cdot 3^{15}$ . Find $n$ .

The product is $n^{d(n)/2}$ , so $n$ uses only the primes $2$ and $3$ : say $n = 2^a 3^b$ and $d = (a+1)(b+1)$ . Comparing exponents, $\dfrac{ad}{2} = 30$ and $\dfrac{bd}{2} = 15$ , so $a = 2b$ . Then $\dfrac{bd}{2} = 15$ becomes $b(2b + 1)(b + 1) = 30$ , and $b = 2$ works: $2 \cdot 5 \cdot 3 = 30$ . So $a = 4$ and $n = 2^4 \cdot 3^2 = 144$ .

Common mistake

The divisor-count formula uses exponent plus one, and it needs the full prime factorization. A common slip is factoring $720$ as $8 \cdot 90$ and multiplying divisor counts: $d(8) \cdot d(90) = 4 \cdot 12 = 48$ , but $d(720) = 30$ . You can only multiply $d$ (or $\sigma$ ) across factors that share no prime.

Tip

$\sigma(n)$ is odd exactly when every odd prime appears to an even power: then each factor $1 + p + \dots + p^{a}$ for an odd $p$ has an odd number of odd terms. The factor for $p = 2$ is always odd. So $\sigma(n)$ is odd exactly when $n$ is a perfect square or twice a perfect square.

Practice

Practice 1

How many positive divisors of $10{,}800 = 2^4 \cdot 3^3 \cdot 5^2$ are perfect squares?

Practice 2

How many positive divisors of $6^{10}$ are multiples of $6^7$ ?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 3

What is the sum of all the positive odd divisors of $1800$ ?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 4

What is the smallest positive integer that has exactly $18$ positive divisors?

Practice 5

How many ordered pairs of positive integers $(a, b)$ satisfy $\gcd(a, b) = 12$ and $\operatorname{lcm}(a, b) = 2520$ ?

Practice 6

A positive integer $N$ has only $2$ and $3$ as prime factors. $N$ has exactly $30$ positive divisors and $6N$ has exactly $42$ . How many positive divisors does $N^2$ have?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 7

The product of all the positive divisors of $n$ is $n^{12}$ , and $n = 2^a \cdot 3^b$ for positive integers $a$ and $b$ . What is the smallest possible value of $n$ ?

Practice 8

For how many positive integers $n \le 50$ is the sum of the positive divisors of $n$ odd?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Real contest practice

2008 AMC 12B, Problem 23: the product of the divisors of $10^n$ , disguised as a sum of logarithms.
2019 AMC 10B, Problem 19: products of two distinct divisors, counted through exponents.