Question

Очень срочно Артур и Саша играли в игру — по очереди выписывали натуральные числа на бумагу. В итоге оказалось, что на бумаге выписано 15 чисел, причем, наименьшее из чисел можно представить как х+1, x>1, а все остальные числа — последовательность (1+хn), где n — натуральный показатель степени, изменяющийся от 2 до 15. Артуру показалось, что выписанных чисел слишком много и он зачеркнул часть из них таким образом, чтобы все оставшиеся на бумаге числа были взаимно простыми. Какое наименьшее количество чисел мог зачеркнуть Артур?

Answer 1

Ответ: 11

Без решения, ибо знаю, что оно не нужно.

Answer 2

Поскольку первое число можно записать в виде х+1, то оно является четным числом, а значит не может быть взаимно простым с остальными числами. Следовательно, первое число необходимо зачеркнуть.

Для того чтобы определить, какие еще числа нужно зачеркнуть, рассмотрим их наибольший общий делитель. Заметим, что для любых двух чисел вида 1+xn (где n — натуральный показатель степени, изменяющийся от 2 до 15) и 1+xm (где m — другой натуральный показатель степени) их разность будет равна x(n-m). Если n и m различны, то разность будет содержать множитель x, а значит, она не может быть равна 1, то есть числа не будут взаимно простыми. Если же n=m, то разность будет равна нулю.

Таким образом, чтобы оставшиеся числа были взаимно простыми, необходимо оставить только числа вида 1+x², 1+x³, 1+x⁴, ..., 1+x¹⁵. Очевидно, что таким образом на бумаге останется 14 чисел.

Ответ: Артур должен зачеркнуть 1 число, то есть оставить 14 чисел на бумаге.