ВсОШ 2019, 11 класс, задача 7
Даны непостоянный многочлен с целыми коэффициентами и натуральное число . Положим , при всех натуральных . Оказалось, что для любого натурального в последовательности есть число, являющееся -й степенью натурального числа, большего . Докажите, что многочлен - линейный.
(М. Антипов)
Решение.
Заметим сразу, что при каждом натуральном в последовательности встретится бесконечно много -х степеней натуральных чисел, больших единицы. Действительно, если их количество конечно, и наибольшая из них - это , то в последовательности не встретится ни одной -й степени, что невозможно.
Положим ; тогда . Поскольку все коэффициенты многочлена целые, из следует . Отсюда непосредственной индукцией по получаем, что , то есть при всех .
Лемма.
делится на .
Доказательство.
Пусть - максимальная степень простого числа , делящая ; достаточно показать, что делится на . Положим ; согласно замечанию выше, найдется такой индекс , что при натуральном ; при этом .
Если не делится на , то по теореме Эйлера , откуда . Если же делится на , то делится на , а значит, и тоже. В любом случае делится на , что и требовалось.
Согласно лемме, для любого число делится на ; при этом по условию среди целых чисел бесконечно много различных. В частности, при бесконечном количестве целых значений (где ).
Предположим теперь, что степень многочлена (и, как следствие, многочлена ) больше . Тогда неравенство выше может выполняться для бесконечно многих целых лишь тогда, когда - квадратный трехчлен со старшим коэффициентом , то есть . В этом последнем случае значения многочлена делятся на для бесконечного количества целых ; это может быть лишь если , то есть или .
В первом случае , то есть не может быть нечетной степенью натурального числа, если не является таковой степенью. Во втором случае при всех , то есть не может быть степенью натурального числа, большего . В обоих случаях условие задачи не выполнено; значит, линеен.