Кратко — методы и что ещё нужно.
Методы для оценки целочисленных делителей значений $P(n)$:
- Факторная/модульная проверка (теорема о делении полинома): для любых целых $n$ $$P(n)-P(1)\text{делится на}n-1,P(n)-P(2)\text{делится на}n-2,$$ поэтому
$$P(n)\equiv 2(\mathrm{mod}n-1),P(n)\equiv 3(\mathrm{mod}n-2).$$ Это даёт явные делители числа $P(n)-2$ и $P(n)-3$.
- Конечные разности и факториалы: для многочлена степени $4$ четвёртая конечная разность постоянна и равна
$${\Delta }^{4}P=4!a_4=24a_4,$$ где $a_4$ — старший коэффициент. Это даёт информацию о делимости значений разностей и, косвенно, об арифметических свойствах самих $P(n)$.
- Биномиальная базисная запись (удобно для делимости):
$$P(x)=\sum _{k=0}^4{c}_k\left(\genfrac{}{}{0ex}{}{x}{k}\right),$$ причём при целых коэффициентах $c_k\in \mathbb{Z}$. Из этого видно, какие факториалы и биномиальные множители обязательно входят в разности значений.
- Интерполяция и модульные методы: подбирая значения $P(x)$ по модулю различных простых чисел и применяя КТМ, можно ограничивать возможные остатки и делители; полезно оценивать коэффициенты по модулю больших чисел.
- Вспомогательно — вычисление $\gcd$ различных разностей $P(n)-P(m)$ для разных $m$ даёт общие делители.
Какие дополнительные данные нужны для однозначного определения $P(x)$:
- Нужно знать ещё $3$ значений в различных точках (всего $5$ значений для многочлена степени $4$), например $P(0),P(3),P(4)$. Пять значений в разных точках однозначно определяют все коэффициенты.
- Альтернативы: знать все коэффициенты (т.е. сами числа $a_0,\dots ,a_4$), или знать достаточно модульных значений коэффициентов (по разным модулям) с учётом оценки на величину коэффициентов (чтобы восстановить их по КТМ).
- Ещё вариант: знать старший коэффициент $a_4$ и ещё $4$ независимых условия (значения или остатки) — тоже хватит.
Этого достаточно для практических шагов: использовать указанные делимости и разности, набирать дополнительные значения/остатки и затем восстановить $P$ однозначно.