|
|
 |
Условие
Петя выбрал натуральное число a > 1 и выписал на доску пятнадцать чисел 1 + a, 1 + a², 1 + a³, ..., 1 + a15. Затем он стёр несколько чисел так, что каждые два оставшихся числа взаимно просты. Какое наибольшее количество чисел могло остаться на доске?
Решение
Заметим, что если k нечётно, то число 1 + ank делится на 1 + an. Каждое из чисел 1, 2, ..., 15 имеет один из видов k, 2k, 4k, 8k, где k нечётно. Таким образом, каждое из выписанных чисел делится либо на 1 + a, либо на 1 + a², либо на 1 + a4, либо на 1 + a8. Поэтому, если мы возьмём хотя бы пять чисел, то среди них найдутся два, кратных одному и тому же числу, большему 1; значит, они не будут взаимно просты. Итак, оставшихся чисел не более четырёх.
Четыре числа могли остаться: если a = 2, то можно оставить числа 1 + 2 = 3, 1 + 2² = 5, 1 + 24 = 17 и 1 + 28 = 257. Все они попарно взаимно просты.
Ответ
4 числа.
Замечания
Можно показать, что при любом чётном a числа 1 + a, 1 + a², 1 + a4, 1 + a8 попарно взаимно просты.
