|
|
 |
Условие
Натуральное число b назовём удачным, если для любого натурального a, такого, что a5 делится на b², число a² делится на b.
Найдите количество удачных натуральных чисел, меньших 2010.
Решение
Лемма. Число b является удачным тогда и только тогда, когда каждое простое число входит в разложение b на простые множители с одним из следующих показателей: 0, 1, 2, 3, 4, 6, 8.
Доказательство. Назовем целое неотрицательное число k счастливым, если не существует такого целого m, что 2m < k ≤ 2,5m. Заметим, что счастливыми являются в точности числа 0, 1, 2, 3, 4, 6, 8. При k ≤ 9 в этом можно убедиться прямой проверкой. Если же k > 9, то выберем такое максимальное число m, что 2m < k. Тогда m > 4, и 2,5m > 2m + 2 = 2(m + 1) > k по выбору m, то есть k несчастливо.
Пусть число b неудачно, то есть a5 делится на b2, но a² не делится на b для некоторого a. Тогда некоторое простое p входит в разложение a2 в меньшей степени, чем в разложение b. Пусть p входит в разложения a и b в степенях m и k соответственно; тогда 2m < k, но 5m ≥ 2k. Значит, число k – несчастливое. Итак, если все степени вхождения простых чисел в b счастливы, то b удачно.
Если же b = pkb', где b' не кратно p и k несчастливо (2m < k ≤ 2,5m), то при a = pmb' число a5 делится на b², а a² не делится на b, то есть b неудачно.
Согласно лемме, каждое неудачное число имеет простой делитель, входящий в разложение на простые множители с показателем 5, 7 или более 8. Поскольку 210 < 2010 < 211, 36 < 2010 < 37, 25·35 > 2010 и 55 > 2010, каждое неудачное число, меньшее 2010, принадлежит одному из следующих непересекающихся классов:
1) числа вида 25q, где q нечётно и q ≤ 61 (25·61 < 2010 < 25·63);
2) числа вида 27q, где q нечётно и q ≤ 15 (27·15 < 2010 < 27·17);
3) числа вида 29q, где q = 1 или 3 (29·3 < 2010 < 29·5);
4) число 210;
5) числа вида 35q, где q не кратно 3 и q ≤ 8 (35·8 < 2010 < 35·10).
Таким образом, общее количество неудачных чисел, меньших 2010, равно 31 + 8 + 2 + 1 + 6 = 48, а количество удачных чисел равно
2009 – 48 = 1961.
