Алгебра : Теоремы и алгоритмы. Яцкин Н.И. - 392 стр.

392                    Алгебра многочленов                     Гл. 6

   В связи с тем что список "подозрительных" дробей может ока-
заться довольно длинным, при ручном счете бывает уместным со-
кратить перебор с помощью некоторых "тестов". Опишем два из
них (наиболее употребительные).
   Прежде всего заметим, что множество C для многочлена f (x) обя-
зательно содержит числа ±1. Именно с проверки этих чисел мы ре-
комендуем начинать работу.
   Допустим, что число 1 является корнем f (x) кратности k, а число
−1 — корнем кратности l. (Не исключается случай, когда одна или
обе из этих кратностей обращаются в нуль.)
   Тогда можно записать разложение на множители

                     f (x) = (x − 1)k (x + 1)l g(x),           (42.9)

где многочлен

              g(x) = b0 xm + b1 xm−1 + ... + bm−1 x + bm      (42.10)

имеет степень m = n − k − l и числа ±1 не являются его корнями,
т. е. g(1) 6= 0 и g(−1) 6= 0.
   Отбор остальных "подозрительных" дробей, т. е. формирование
множеств

       S = {s ∈ Z : s|bm }, T = {t ∈ Z : (t|b0 ) ∧ (t > 0)}   (42.11)

и
                           s
                      C = { ∈ Q : s ∈ S, t ∈ T },             (42.12)
                           t
следует производить уже для многочлена g(x), причем числа ±1 из
множества C можно сразу исключить.
   (Напомним, что повторений в множестве C быть не должно и что
все включенные в него дроби должны быть нормализованными. Це-
лые числа, принадлежащие C, мы также будем представлять как
дроби с единичным знаменателем.)
   Для дальнейшего понадобятся значения g(1) и g(−1), также опре-
деляемые по Горнеру.
   Два обещанных теста таковы:
   (test 1) если c = s/t является корнем g(x), то t − s|g(1);
   (test 2) если c = s/t является корнем g(x), то t + s|g(−1).
   Оба этих теста основываются на третьем утверждении предложе-
ния 42.1 (применяемом к многочлену g(x) при u = ±1).