Число делителей по разложению
Чтобы пересчитать все делители числа, не нужно их выписывать. Любой делитель числа \(n = p_1^{a_1} \cdot \dots \cdot p_k^{a_k}\) составлен из тех же простых множителей в степенях от 0 до \(a_i\).
Формула. Число натуральных делителей \[\tau(n) = (a_1 + 1)(a_2 + 1) \cdot \dots \cdot (a_k + 1).\] Показатель каждого простого множителя можно выбрать \(a_i + 1\) способами (от 0 до \(a_i\)), и выборы независимы.
Как это работает. Сколько делителей у числа 360?
- Разложение: \(360 = 2^3 \cdot 3^2 \cdot 5^1\).
- Увеличиваем каждый показатель на 1 и перемножаем: \((3 + 1)(2 + 1)(1 + 1) = 4 \cdot 3 \cdot 2 = 24\).
- Проверка на маленьком числе: у \(12 = 2^2 \cdot 3\) формула даёт \(3 \cdot 2 = 6\) делителей: 1, 2, 3, 4, 6, 12. Ответ: 24.
Ещё пример. Найдите наименьшее натуральное число, у которого ровно 6 делителей.
Решение. \(6 = 6 \cdot 1 = 3 \cdot 2\). Первый вариант — \(p^5\), наименьшее \(2^5 = 32\). Второй — \(p^2 q\): наименьшее \(2^2 \cdot 3 = 12\). Ответ: 12.
Лайфхак. Нечётное число делителей бывает только у точных квадратов: делители разбиваются на пары \(d\) и \(\dfrac{n}{d}\), и лишь у квадрата один делитель \(\sqrt n\) парный сам себе. Это ключ к задачам про «лампочки» и «шкафчики», которые переключают по номерам.
На ЕГЭ. В задании 20 просят найти число с заданным количеством делителей или доказать, что у числа «не больше» делителей, чем указано. Формула \(\tau(n)\) превращает такую задачу в разбор произведений вида \((a + 1)(b + 1)\).
Закрепите теорию: 11 заданий с проверкой и подсказками, урок зачитывается от 70 %.
Пройти урок arrow_forward