Все формулы РФ

Математика / Арифметика и теория чисел

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

Число положительных делителей n равно произведению увеличенных на единицу показателей в его простом разложении. Каждый делитель получается независимым выбором допустимой степени каждого простого множителя.

Опубликовано: Обновлено:

Теория чиселАлгебраСтраницы с задачами и решениямиЕсть историческая справка

Формула

$$n=\prod_{i=1}^{r}p_i^{a_i},\qquad \tau(n)=\prod_{i=1}^{r}(a_i+1)$$
Схема Выбор степеней для делителя 360
Выбор степеней для делителя 360Выбор степеней для делителя 360ПростойДопустимые степениВариантов20,1,2,3430,1,2350,124 · 3 · 2 = 24

Четыре, три и два независимых варианта дают 24 делителя.

Обозначения

$n$
положительное целое число, безразмерная величина
$pᵢ$
различные простые множители, безразмерная величина
$aᵢ$
их показатели в разложении n, безразмерная величина
$r$
число различных простых множителей, безразмерная величина
$τ(n)$
число положительных делителей, безразмерная величина
$i$
индекс простого множителя, безразмерная величина

Условия применения

Число n положительное целое, pᵢ — различные простые, aᵢ — положительные целые показатели. Считаются все положительные делители, включая 1 и само n. Для n=1 пустое произведение равно единице: у единицы один положительный делитель.

Ограничения

Отрицательные делители здесь не считаются; если нужны все целые делители ненулевого n, их вдвое больше. Формула требует простого разложения и неверна для произвольного произведения составных оснований. По одному количеству делителей само число однозначно не восстанавливается.

Подробное объяснение

Положительный делитель не может содержать простого множителя, которого нет в n. Кроме того, показатель каждого простого в делителе не превосходит его показателя в n: иначе частное не было бы целым. Значит, делитель полностью задаётся набором выбранных показателей.

Для простого pᵢ доступны степени от нулевой до aᵢ включительно. Вариантов aᵢ+1, поскольку нулевая степень тоже считается. Выборы для разных простых независимы, а правило произведения даёт количество всех наборов показателей.

Единственность простого разложения гарантирует, что два разных набора показателей не создают один делитель. Она же гарантирует полноту: любой положительный делитель соответствует одному набору. Поэтому формула не пропускает единицу и не считает ни один делитель дважды.

Для простого p показатель равен одному, и делителей два: 1 и p. Для квадрата простого показатель равен двум, делителей три. Вообще число делителей нечётно ровно у полных квадратов: тогда все показатели чётные и все множители aᵢ+1 нечётны.

Другой способ проверки — объединение делителей в пары d и n/d. У неквадрата все пары состоят из разных чисел, поэтому итог чётный. У квадрата средний делитель √n остаётся без отдельного партнёра и делает итог нечётным.

Как пользоваться формулой

  1. Приведите разложение к различным простым основаниям, объединив повторяющиеся множители в степени.
  2. Для каждого показателя a выпишите a+1: единица добавляется из-за допустимой нулевой степени.
  3. Перемножьте полученные количества вариантов, не заменяя правило произведения сложением показателей.
  4. Проверьте чётность ответа через наличие целого квадратного корня и при малом n перечислите делители.

Историческая справка

Подсчёт делителей опирается на классическое изучение делимости и простых чисел. Современная формула возникает из единственности разложения целого числа и комбинаторного правила произведения. В литературе XX–XXI веков эта арифметическая функция обычно обозначается τ(n) или d(n); NIST DLMF использует d(n) и рассматривает её рядом с другими мультипликативными функциями. Различие букв не меняет определение. В учебном изложении удобно сначала перечислить делители степени простого, затем перейти к произведению независимых выборов. Единственный автор такой элементарной формулы здесь не устанавливается: её значение в теории чисел определяется общим принципом факторизации. Более сложные исследования рассматривают среднее поведение числа делителей при росте n, что выходит за рамки точного подсчёта для одного числа.

Историческая линия формулы

Функция числа делителей — стандартная арифметическая функция, обозначаемая τ или d в разных источниках. Произведение aᵢ+1 следует из единственности простого разложения и независимого выбора степеней; эта страница не приписывает элементарный подсчёт одному исследователю.

Пример

Пусть n = 360. Разложение 360 = 2³ · 3² · 5¹. Делитель выбирает степень двойки 0,1,2 или 3 — четыре варианта; степень тройки — три, пятёрки — два. Поэтому τ(360) = (3+1)(2+1)(1+1) = 24. Проверка: 360 не квадрат, значит делители объединяются в 12 пар d и 360/d; число 24 чётно. Ответ: 24 положительных делителя. Например, выбор показателей (0,1,1) даёт 15, а (3,2,1) даёт 360. Ни один выбор не повторяется благодаря единственности разложения, и каждый положительный делитель получается ровно один раз. Это подтверждает именно произведение числа вариантов, а не сумму.

Частая ошибка

Не перемножайте сами простые числа вместо увеличенных показателей. Не забывайте нулевую степень, иначе исчезнет часть делителей. Не подставляйте разложение с составными основаниями, например 36=4·9, как каноническое. Не исключайте само n, если задача спрашивает все положительные делители.

Практика

Задачи с решением

Квадрат 36

Условие. Найдите число положительных делителей 36.

Решение. 36=2²·3². Получаем (2+1)(2+1)=9. Делители: 1,2,3,4,6,9,12,18,36.

Ответ. 9

Простое число

Условие. Сколько положительных делителей у 13?

Решение. 13 простое и имеет показатель 1. Формула даёт 1+1=2: это 1 и 13.

Ответ. 2

Дополнительные источники

  • https://dlmf.nist.gov/27.3
  • https://www.cs.ucf.edu/~dmarino/ucf/bhcsi/lectures/compprog/Day09-NumTheory-V2.pdf

Связанные формулы

Математика

Сумма делителей по простому разложению числа

$n=\prod_{i=1}^{r}p_i^{a_i},\qquad \sigma(n)=\prod_{i=1}^{r}(1+p_i+\cdots+p_i^{a_i})$

Сумма положительных делителей n получается перемножением сумм степеней каждого простого множителя от нуля до его показателя. В сумму входят единица и само число; для собственных делителей затем вычитают n.

Математика

Функция Эйлера: произведение по простым делителям

$\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right)$

Функция Эйлера φ(n) считает положительные целые числа от 1 до n, взаимно простые с n. Для вычисления достаточно знать различные простые делители n: каждый входит в произведение ровно один раз.

Математика

Правило произведения в комбинаторике

$N=m_1m_2\cdots m_k$

Формула описывает прием «умножение последовательных шагов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.