Интерполяция

Рассмотрим многочлен от одной переменной

Поскольку степень не превосходит При значения пробегают квадраты целых чисел а потому по условию — целые числа.

Докажем стандартную лемму о целочисленности многочлена.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Пусть — многочлен степени Если — целые числа, то для всех целых

Доказательство. Доопределим число сочетаний и для отрицательных чисел: пусть

при целых и Это число при неотрицательном — целое по комбинаторному определению числа сочетаний, а при отрицательном оно тоже целое, ведь

Тогда из теоремы Лагранжа об интерполяции

где крышечка означает отсутствие скобки. Из рассуждений выше понимаем, что каждое слагаемое — целое, а значит, в любой целой точке значение многочлена является целым.

_________________________________________________________________________________________________________________________________________________________________________________

Применяя лемму к (с ), получаем, что для всех целых В частности, для произвольного целого имеем

Это и требовалось доказать.