Question

Петя выбрал натуральное число a>1a>1 и выписал на доску пятнадцать чисел 1+a,1+a2,1+a3,…,1+a151+a,1+a2,1+a3,…,1+a15. Затем он стёр несколько чисел так, что каждые два оставшихся числа взаимно просты. Какое наибольшее количество чисел могло остаться на доске?

Answer 1

Все числа 1+a^k при нечетном k делятся на 1+а. Всего нечетных степеней 8 штук: 1, 3, 5, 7, 9, 11, 13. 15, поэтому чтобы оставшиеся были взаимно просты необходимо выкинуть как минимум 7 штук таких чисел.

Все числа  1+a^k при k∈{2, 6, 10, 14} делятся на 1+а², поэтому нужно выкинуть еще 3 числа.

Все числа  1+a^k при  k∈{4,12} делятся на 1+а⁴, поэтому нужно выкинуть еще 1 число.
Итак, останется не больше 15-7-3-1=4 чисел.
Действительно, например при а=2, можно оставить 1+а, 1+а², 1+а⁴, 1+а⁸, т.е. 3, 5, 17, 257, которые взаимно просты. Ответ: 4 числа.