Глава
Теория
Подсчет делителей превращает число в набор показателей простых множителей. Если \(n=p_1^{a_1}\cdots p_s^{a_s}\), то каждый делитель получается независимым выбором показателей \(0,1,\ldots,a_i\).
Олимпиадная сила метода появляется тогда, когда нужно не просто посчитать, а восстановить форму числа по количеству делителей или найти наименьшее число с заданным количеством делителей.
Если условие говорит “ровно \(k\) делителей”, сразу разложите \(k\) на множители вида \(a_i+1\). Если требуется наименьшее число, перебирайте не сами числа, а возможные наборы показателей.
Если нужны нечетные делители, отбросьте степень двойки. Если нужно доказать нечетность \(\tau(n)\), используйте парность делителей вокруг \(\sqrt{n}\).
Примеры
Главное - перейти от числа к показателям простых множителей.
Задача. Найдите число положительных делителей \(360\).
\(360=2^3\cdot3^2\cdot5\). Делитель имеет вид \(2^a3^b5^c\), где \(a=0,1,2,3\), \(b=0,1,2\), \(c=0,1\). Поэтому \(\tau(360)=4\cdot3\cdot2=24\).
Комментарий. Нулевой показатель означает, что простой множитель не входит в делитель.
Чтобы считать нечетные делители, степень двойки не нужна.
Задача. Сколько нечетных положительных делителей у числа \(720\)?
\(720=2^4\cdot3^2\cdot5\). Нечетный делитель не содержит множитель \(2\), поэтому выбираем только показатели при \(3\) и \(5\). Получаем \((2+1)(1+1)=6\) нечетных делителей.
Комментарий. Нечетная часть числа равна \(3^2\cdot5\).
Делители обычно идут парами; квадрат дает один непарный делитель.
Задача. Докажите, что \(\tau(n)\) нечетно тогда и только тогда, когда \(n\) - квадрат.
Если \(d\mid n\), то \(\frac{n}{d}\mid n\). Обычно делители разбиваются на пары \(d\) и \(\frac{n}{d}\). Непарный делитель возможен только когда \(d=\frac{n}{d}\), то есть \(d^2=n\). Значит, число делителей нечетно ровно для квадратов.
Комментарий. Это доказательство не требует формулы для \(\tau(n)\), но хорошо ее объясняет.
Минимизация идет по наборам показателей, а не перебором чисел.
Задача. Найдите наименьшее натуральное число, имеющее ровно \(12\) положительных делителей.
Нужно разложить \(12\) как произведение чисел \(a_i+1\). Возможные важные варианты: \(12\), \(6\cdot2\), \(4\cdot3\), \(3\cdot2\cdot2\). Они дают кандидаты \(2^{11}\), \(2^5\cdot3=96\), \(2^3\cdot3^2=72\), \(2^2\cdot3\cdot5=60\). Наименьший кандидат \(60\). Ответ: \(60\).
Комментарий. Большие показатели ставим на меньшие простые.
Хотя модуль про \( au\), полезно увидеть соседнюю функцию \(\sigma\).
Задача. Найдите сумму положительных делителей \(72\).
\(72=2^3\cdot3^2\). Сумма делителей равна \((1+2+2^2+2^3)(1+3+3^2)=15\cdot13=195\).
Комментарий. Эта идея вернется в поздних модулях об арифметических функциях.
У \(n^2\) все показатели удваиваются.
Задача. Если \(n=2^3\cdot3^2\cdot5\), найдите \(\tau(n^2)\).
Тогда \(n^2=2^6\cdot3^4\cdot5^2\). Поэтому \(\tau(n^2)=(6+1)(4+1)(2+1)=7\cdot5\cdot3=105\).
Комментарий. Не надо сначала вычислять само число \(n^2\).
Заданное количество делителей ограничивает форму числа.
Задача. Опишите все натуральные \(n\), у которых ровно \(4\) положительных делителя.
Нужно \((a_1+1)\cdots(a_s+1)=4\). Возможности: \(4\) или \(2\cdot2\). Поэтому \(n=p^3\) для простого \(p\), либо \(n=pq\), где \(p\) и \(q\) - различные простые.
Комментарий. Это первый шаг к обратным задачам на \(\tau(n)\).
Парность делителей помогает находить их произведение.
Задача. Докажите, что произведение всех положительных делителей \(n\) равно \(n^{\tau(n)/2}\).
Каждому делителю \(d\) соответствует делитель \(\frac{n}{d}\), и произведение пары равно \(n\). Поэтому произведение всех делителей равно \(n\), умноженному по одной раз за каждую пару. Число пар равно \(\frac{\tau(n)}{2}\). Если \(n\) квадрат, средний делитель \(\sqrt{n}\) учитывается дважды в записи \(n^{\tau(n)/2}\), и формула все равно верна.
Комментарий. Для квадрата показатель может быть полуцелым, но значение остается целым.
Задачи
Найдите число положительных делителей \(84\).
Разложите \(84\) на простые множители.
\(84=2^2\cdot3\cdot7\). Поэтому \(\tau(84)=(2+1)(1+1)(1+1)=12\).
Найдите \(\tau(144)\).
\(144=12^2\).
\(144=2^4\cdot3^2\). Тогда \(\tau(144)=(4+1)(2+1)=15\).
Сколько положительных делителей у числа \(2^5\cdot3^3\)?
Выберите показатель при \(2\) и показатель при \(3\).
Показатель при \(2\) можно выбрать \(6\) способами, при \(3\) - \(4\) способами. Итого \(6\cdot4=24\) делителя.
Докажите, что у \(p^a\), где \(p\) - простое, ровно \(a+1\) положительных делителей.
Какие степени \(p\) могут делить \(p^a\)?
Каждый положительный делитель \(p^a\) имеет вид \(p^k\), где \(k=0,1,\ldots,a\). Таких значений \(k\) ровно \(a+1\). Поэтому делителей \(a+1\).
Сколько нечетных положительных делителей у \(48\)?
Разложите \(48=2^4\cdot3\).
Нечетный делитель не содержит \(2\), поэтому он может быть только \(1\) или \(3\). Ответ: \(2\) нечетных делителя.
Найдите \(\tau(360)\).
Используйте \(360=2^3\cdot3^2\cdot5\).
\(\tau(360)=(3+1)(2+1)(1+1)=4\cdot3\cdot2=24\).
Найдите число положительных делителей \(1000\).
\(1000=10^3\).
\(1000=2^3\cdot5^3\). Поэтому \(\tau(1000)=(3+1)(3+1)=16\).
Сколько нечетных делителей у числа \(720\)?
Отбросьте множитель \(2^4\).
\(720=2^4\cdot3^2\cdot5\). Нечетная часть \(3^2\cdot5\), поэтому число нечетных делителей равно \((2+1)(1+1)=6\).
Не вычисляя всех делителей, объясните, почему \(\tau(225)\) нечетно.
Проверьте, является ли \(225\) квадратом.
\(225=15^2\) является квадратом. У квадрата число положительных делителей нечетно, потому что делитель \(\sqrt{225}=15\) остается без пары. Значит, \(\tau(225)\) нечетно.
Найдите наименьшее натуральное число с ровно \(8\) положительными делителями.
Разложения \(8\): \(8\), \(4\cdot2\), \(2\cdot2\cdot2\).
Кандидаты: \(2^7=128\), \(2^3\cdot3=24\), \(2\cdot3\cdot5=30\). Наименьший \(24\). Ответ: \(24\).
Найдите наименьшее натуральное число с ровно \(10\) положительными делителями.
Возможности: \(10\) или \(5\cdot2\).
Кандидаты: \(2^9=512\) и \(2^4\cdot3=48\). Наименьшее число равно \(48\).
Найдите все натуральные числа меньше \(100\), у которых ровно \(3\) положительных делителя.
Число с тремя делителями имеет вид \(p^2\).
Если \(\tau(n)=3\), то \(n=p^2\) для простого \(p\). Нужно \(p^2<100\), значит, \(p<10\). Простые \(p=2,3,5,7\). Получаем \(4,9,25,49\).
Докажите, что натуральное число имеет нечетное количество положительных делителей тогда и только тогда, когда оно является квадратом.
Разбейте делители на пары \(d\) и \(\frac{n}{d}\).
Если \(d\mid n\), то \(\frac{n}{d}\mid n\). Делители идут парами, кроме случая \(d=\frac{n}{d}\), то есть \(d^2=n\). Поэтому непарный делитель существует ровно тогда, когда \(n\) квадрат. Значит, число делителей нечетно ровно для квадратов.
Найдите наименьшее натуральное число с ровно \(15\) положительными делителями.
\(15=15\) или \(15=5\cdot3\).
Варианты показателей: \(14\), либо \(4\) и \(2\). Кандидаты: \(2^{14}\) и \(2^4\cdot3^2=144\). Наименьшее число \(144\).
Найдите наименьшее натуральное число с ровно \(24\) положительными делителями.
Проверьте разложения \(24\) на множители \(a_i+1\).
Важные кандидаты: \(2^7\cdot3^2=1152\), \(2^5\cdot3^3=864\), \(2^5\cdot3\cdot5=480\), \(2^3\cdot3^2\cdot5=360\), \(2^2\cdot3\cdot5\cdot7=420\). Наименьший из них \(360\), и остальные варианты с еще большими показателями дают большие числа. Ответ: \(360\).
Найдите \(\tau(360^2)\).
Не вычисляйте \(360^2\); удвойте показатели.
\(360=2^3\cdot3^2\cdot5\). Тогда \(360^2=2^6\cdot3^4\cdot5^2\), поэтому \(\tau(360^2)=7\cdot5\cdot3=105\).
Найдите произведение всех положительных делителей числа \(36\).
Используйте формулу \(n^{\tau(n)/2}\).
\(36=2^2\cdot3^2\), поэтому \(\tau(36)=9\). Произведение делителей равно \(36^{9/2}=6\cdot36^4\). Это и есть точное значение.
Опишите все натуральные числа, имеющие ровно \(4\) положительных делителя.
Разложите \(4\) как \(4\) и \(2\cdot2\).
Если \(\tau(n)=4\), то возможны показатели \(3\), либо \(1\) и \(1\). Поэтому \(n=p^3\) для простого \(p\), либо \(n=pq\), где \(p,q\) - различные простые.
Опишите все натуральные \(n\), у которых ровно два нечетных положительных делителя.
Рассмотрите нечетную часть числа.
Пусть \(n=2^a m\), где \(m\) нечетно. Нечетные делители \(n\) - это делители \(m\). Нужно \(\tau(m)=2\), значит, \(m\) - нечетное простое число. Поэтому \(n=2^a p\), где \(a\ge0\), а \(p\) - нечетное простое.
Найдите число положительных делителей \(10^6\).
\(10^6=2^6\cdot5^6\).
\(10^6=2^6\cdot5^6\), значит, \(\tau(10^6)=(6+1)(6+1)=49\).
Найдите наименьшее натуральное число с ровно \(36\) положительными делителями.
Сравните основные разложения \(36\): \(9\cdot4\), \(6\cdot6\), \(6\cdot3\cdot2\), \(4\cdot3\cdot3\), \(3\cdot3\cdot2\cdot2\).
Кандидаты: \(2^8\cdot3^3=6912\), \(2^5\cdot3^5=7776\), \(2^5\cdot3^2\cdot5=1440\), \(2^3\cdot3^2\cdot5^2=1800\), \(2^2\cdot3^2\cdot5\cdot7=1260\). Наименьший \(1260\). Другие разложения с большим одиночным показателем дают еще большие числа. Ответ: \(1260\).
Найдите наименьшее нечетное натуральное число, имеющее ровно \(12\) положительных делителей.
Используйте простые \(3,5,7,\ldots\) вместо \(2,3,5,\ldots\).
Для \(12\) делителей варианты как раньше. Кандидаты среди нечетных: \(3^{11}\), \(3^5\cdot5\), \(3^3\cdot5^2\), \(3^2\cdot5\cdot7=315\). Наименьший \(315\). Ответ: \(315\).
Найдите все натуральные \(n\), для которых \(\tau(2n)=2\tau(n)\).
Пусть \(n=2^a m\), где \(m\) нечетно.
Пусть \(n=2^a m\), \(m\) нечетно. Тогда \(\tau(n)=(a+1)\tau(m)\), а \(\tau(2n)=(a+2)\tau(m)\). Условие дает \(a+2=2(a+1)\), откуда \(a=0\). Значит, \(n\) должно быть нечетным. Все нечетные \(n\) подходят.
Найдите наименьшее натуральное число, имеющее ровно \(60\) положительных делителей.
Расположите показатели по убыванию и сравните мультипликативные разложения \(60\).
Чтобы число было минимальным, достаточно рассматривать \(2^{a_1}3^{a_2}5^{a_3}\cdots\), где \(a_1\ge a_2\ge a_3\ge\cdots\). Нужно \((a_1+1)(a_2+1)\cdots=60\). Основные кандидаты: \(2^9\cdot3^2\cdot5=23040\), \(2^5\cdot3^4\cdot5=12960\), \(2^4\cdot3^3\cdot5^2=10800\), \(2^4\cdot3^2\cdot5\cdot7=5040\). Варианты с одним или двумя очень большими показателями еще больше. Наименьший кандидат \(5040\), и \(\tau(5040)=\tau(2^4\cdot3^2\cdot5\cdot7)=5\cdot3\cdot2\cdot2=60\). Ответ: \(5040\).
Лестницы