Ключевые свойства и наблюдения
- Остаток при делении на $x-1$ равен значению в точке $1$: $$p(x)=(x-1)q(x)+p(1),$$ поэтому $p(1)=0$ тогда и только тогда $x-1$ делит $p(x)$ (корень $x=1$).
- Аналогично для $x+1$: $$p(x)=(x+1)r(x)+p(-1),$$ поэтому $p(-1)=0$ ⇔ $x=-1$ — корень.
- Если целое число $t$ — корень $p(t)=0$, то из первой формулы при подстановке $x=t$ получаем: $$(t-1)\mid p(1).$$ Из второй: $$(t+1)\mid p(-1).$$ - По теореме о рациональных корнях (для целых коэффициентов) любое целое корень $t$ делит свободный член $a_0$: $$t\mid a_0.$$
Следовательно для любого целого корня $t$ одновременно выполняются три необходимых условия:
$$t\mid a_0,(t-1)\mid p(1),(t+1)\mid p(-1).$$ Это сильно сужает кандидатов, но не даёт достаточного условия (последняя тройка условий не гарантирует $p(t)=0$).
Алгоритм проверки целых корней (практически эффективный)
1. Вычислить свободный член $a_0$, значения $p(1)$ и $p(-1)$.
2. Найти все целые делители $D=\{\pm d:d\mid a_0\}$.
3. Для каждого $t\in D$ отсеять, если не выполняются: $(t-1)\mid p(1)$ или $(t+1)\mid p(-1)$.
4. Для оставшихся кандидатов вычислить $p(t)$. Если для некоторого $t$ $p(t)=0$, то найден целый корень.
5. Если нужно все целые корни, при каждом найденном целом корне выполнить деление многочлена на $(x-t)$ и повторить процесс для многочлена меньшей степени.
Анализ границ применимости и замечания
- Условия из пункта 3 являются необходимыми, но не достаточными: кандидат может пройти проверки делимости, но не быть корнем (нужно проверять $p(t)=0$).
- Метод особенно эффективен, когда $|a_0|$, $|p(1)|$ и $|p(-1)|$ малы (мало делителей). В худшем случае число кандидатов — число делителей $a_0$ (обычно экспоненциально меньше по сравнению с перебором больших диапазонов).
- Если $p(1)=0$ или $p(-1)=0$, соответствующие корни сразу обнаруживаются.
- Этот подход применим ко всем многочленам с целыми коэффициентами любой степени (не зависит от того, что степень равна 5); степень влияет только на скорость деления и число потенциальных целых корней.
- Для дополнительного отсева можно использовать модульные проверки по простым числам (например, если $p(t)\not\equiv 0(\mathrm{mod}m)$ для некоторого $m$, то $t$ не корень), или теоремы о границах корней (например, оценки Коши) чтобы ограничить абсолютное значение возможных корней.