ВсОШ 2023, 11 класс, задача 7

Решение. Многочлен называется целозначным, если - целое число при любом целом . Нам надо доказать, что, если многочлены и целозначны, причём степень равна , то старший коэффициент многочлена - целый.

Лемма. Пусть - целозначный многочлен степени . Тогда все коэффициенты многочлена целые.

Доказательство. Рассмотрим многочлен

Его степень не больше , и его значения совпадают с соответствующими значениями в точках . Это означает, что многочлен имеет степень не выше , а также обнуляется в точке. Поэтому он нулевой, то есть . (Формула выше - это частный случай интерполяционной формулы Лагранжа.)

Осталось заметить, что в формуле выше в -м слагаемом знаменатель равен ; это число делит , поскольку . Значит, при умножении каждого слагаемого на получается многочлен с целыми коэффициентами.

Перейдём к решению задачи. Индукция по . База при тривиальна. Для перехода индукции рассмотрим бицелозначный многочлен степени ; пусть его старший коэффициент равен .

Если не является простым числом, то . Заметим, что многочлен также бицелозначный, имеет степень и старший коэффициент . По предположению индукции, число является целым, что и требовалось доказать.

Пусть теперь - простое число; тогда , и то же рассуждение даёт, что число является целым. Предположим, что - нецелое число; тогда знаменатель числа (в несократимой записи) делится на простое число . Заметим, что сумма всех коэффициентов многочлена - это целое число . Поскольку знаменатель числа делится на , среди коэффициентов многочлена найдётся ещё один, у которого знаменатель делится на ; пусть это коэффициент при , . Заметим, что , так как число целое.

Но тогда у целозначного многочлена коэффициент при равен и также имеет знаменатель, кратный . Поскольку - простое число, отсюда вытекает, что коэффициент при у многочлена нецелый, что противоречит лемме.

Замечание 1. Случай простого можно разобрать и другими способами. Приведём один из них.

Предположим, что число целое, а - нет, так что для некоторого целого , не кратного . Рассмотрим многочлен

Он целозначен, поскольку при любом целом число делится на . Кроме того, его степень меньше . Из леммы вытекает, что знаменатели коэффициентов многочлена не делятся на .

Рассмотрим теперь целое число . Из формулы нетрудно получить, что

При этом первое слагаемое - это несократимая дробь со знаменателем, не делящимся на , а второе - с делящимся. Это невозможно для целого .

Замечание 2. Как доказали D. Brizolis и E. G. Straus, наименьшее , для которого старший коэффициент многочлена обязательно целый, равно

где произведение берётся по всем простым , а - это наибольшее целое неотрицательное число , для которого верно неравенство .