Во-первых, заменой если определить полином

, то это тоже будет полином с целыми коэффициентами. Другими словами, целочисленная константа

особой роли в поставленной задачи не играет.
В частности, если

, то

.
Во-вторых, если полином

задан значениями в узлах

для

, то можно понизить размерность задачи

на 1. А именно, если

для

, то полином

будет принимать значения

для

, которые обязаны быть целыми. При этом полином

выражается через

как

.
Для

понижение размерности даст полином со значениями

, а затем

. Как видим, последнее значение не является целым, а потому полинома удовлетворяющего пункту 1 не существует.
В-третьих, из процедуры понижения размерности описанной выше следует, что полином

в случае, когда он существует, может быть выбран степени

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