Теория чисел на устном туре Турнира Городов

Нечётные не подходят. В самом деле, рассмотрим многочлен и различные натуральные Так как нечётно, делится на а тогда не делится, поскольку

Осталось доказать, что все чётные подходят. Рассмотрим произвольный многочлен степени Представим его в виде суммы где в все мономы чётной степени, а в — нечётной. Заметим, что при всех натуральных сумма делится на Докажем, что найдутся такие что и делится на Заметим, что степень равна

Рассмотрим случай, когда старший коэффициент положителен (в случае отрицательного старшего коэффициента проведём дальнейшее доказательство для многочлена Так как то найдётся такое натуральное что Докажем, что подходят. В силу выбора они оба натуральные, причём Далее, по модулю выполняются сравнения (очевидно) и (в силу чётности многочлена . Значит, что и требовалось.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. В случае чётного можно проделать подобное рассуждение и без разбиения на чётную и нечётную компоненты. Поскольку степень многочлена равна существует такое натуральное , что . Тогда подойдут числа Действительно, тогда и по модулю верно сравнение