Разложение на простые множители и число делителей

Если \(n = p_1^{e_1} p_2^{e_2} \cdots p_m^{e_m}\) — разложение на простые множители, то любой делитель имеет вид \(p_1^{f_1} \cdots p_m^{f_m}\), где \(0 \le f_i \le e_i\). Поэтому число делителей

\[\tau(n) = (e_1 + 1)(e_2 + 1) \cdots (e_m + 1).\]

Делители разбиваются на пары \(d\) и \(\dfrac{n}{d}\); без пары остаётся только \(\sqrt n\). Поэтому число делителей нечётно тогда и только тогда, когда \(n\) — точный квадрат.

Пример. Сколько делителей у числа 360?
Решение. \(360 = 2^3 \cdot 3^2 \cdot 5\), \(\tau = 4 \cdot 3 \cdot 2 = 24\).

Пример. Найдите наименьшее натуральное число, у которого ровно 12 делителей.
Решение. Переберём разложения 12 на множители, больше 1: \(12\), \(6 \cdot 2\), \(4 \cdot 3\), \(3 \cdot 2 \cdot 2\). Показатели на единицу меньше множителей; наименьшее число получается, когда больший показатель стоит у меньшего простого: \(2^{11} = 2048\), \(2^5 \cdot 3 = 96\), \(2^3 \cdot 3^2 = 72\), \(2^2 \cdot 3 \cdot 5 = 60\). Ответ: 60.

Пример. Сколько делителей может быть у числа, если их количество — простое число \(p\)?
Решение. \((e_1 + 1) \cdots (e_m + 1) = p\) возможно только при одном множителе: \(n = q^{p - 1}\), где \(q\) — простое. Например, ровно 7 делителей у чисел \(2^6 = 64\), \(3^6 = 729\) и т. д.