Числовые многочлены Учебно-методическое пособие (стр. 15 )

Ценность этого необходимого условия заключается в том, что если  для несократимой дроби не выполняется хотя бы одно требование (13) или (14), то эта дробь заведомо не является рациональным корнем целочисленного многочлена f. С другой стороны нужно иметь в виду, что если даже условия (13), (14) выполняются, еще не факт, что дробь является корнем многочлена f(x): ее свойство «быть корнем» требует дополнительной проверки, например схемой Горнера.  Таким образом, требования (13), (14) дают нам возможность составить список чисел p и q, из которых затем составляется список дробей    - всех  «кандидатов в рациональные корни»  многочлена f.

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

Пусть дан целочисленный многочлен  fx (см. (1)) и требуется найти все его рациональные корни (или установить, что таковых нет). Для этого выполняем следующие шаги:

Выписываем все целые делители p свободного члена a (см. (13)); Выписываем все натуральные делители q старшего коэффициента a (см. (14)); Из найденных чисел p и q составляем всевозможные дроби ; Каждую из построенных дробей испытываем (проверяем) «на корень» многочлена f(x). Делать это можно либо находя значение f(), либо применяя к числу = схему Горнера; Дроби, выдержавшие испытание «на корень», и будут всеми искомыми рациональными корнями исходного целочисленного многочлена f(x). Если же таковых не оказалось, многочлен рациональных корней не имеет. Задача решена!

§14.  Целые корни целочисленных многочленов. Оптимизация вычислительных процедур при отыскании рациональных корней

Вернемся к необходимому условию рационального корня целочисленного многочлена f и к соотношениям (13), (14) §13, определяющим это условие. Небольшие рассуждения помогают получить два важных вывода. Допустим, что в качестве рационального мы ищем целый корень многочлена f. Несократимая дробь является целым числом только в случае, когда ее знаменатель равен 1. Тогда сама дробь совпадает со своим числит

  (q = 1)    (= p  Z)  (1)

Но при q = 1 соотношение (14) §13 заведомо выполнимо. Следовательно,  остается только соотношение (13) §13 и, поэтому, необходимое условие рационального корня целочисленного многочлена f(х) для случая целого корня перефразируется так (это  - первый из заявленных выводов):

Вывод 1. Необходимое условие целого корня целочисленного многочлена. Если целое число p Z  является корнем целочисленного многочлена f, то p является делителем свободного члена этого многочлена. т. е удовлетворяется соотношение (13) §13.

Понятно, как надлежит действовать, если мы решаем задачу нахождения целых корней целочисленного многочлена f. Для этого используем тот же алгоритм нахождения рациональных корней, описанный в §13, с поправками: опускаем п. п. 2, 3 алгоритма, а в п. 4 тестируем только делители свободного члена, выписанные в п.1.

Допустим теперь, что у целочисленного многочлена f старший коэффициент равен 1. Тогда соотношение (14) §13 примет вид:  q│1. Это означает, что q = 1. Следовательно, искомый рациональный корень  целочисленного многочлена f является целым числом. Это и есть

Вывод 2. У целочисленного многочлена  со старшим  коэффициентом, равным 1,  в качестве рациональных могут быть только целые корни. 

Вычислительная сторона алгоритма отыскания рациональных корней может быть очень объемной, громоздкой. Можно оптимизировать (сократить) объем этих вычислений. Для этого обратимся к алгебраическому определению корня многочлена, т. е.  соотношению (7) § 3. Итак, пусть дробь  является корнем целочисленного многочлена f(х). Согласно (6)  §3 имеем:

  (х - ) │f  (2)

В соотношении (2) нужно иметь в виду, что деление производится в кольце Q[x[. Если обозначить через g(х) частное от деления f(х) на (х - ), то (2) перепишется  так:

  f(х) = (х - ) g(х)  (3)

В (3) многочлены (х - ) и  g(х)  -  рациональные, а f(х)  -  целочисленный. Причем, как это следует из (3), если deg f(x) = n, то deg g(x) = n-1. Если обратиться к схеме Горнера (9) §2 и заменить там б на , то, оставляя в стороне собственно значения коэффициентов многочлена g(х), при внимательном прочтении схемы Горнера  мы усматриваем, что все дробные коэффициенты  многочлена g(х) в качестве знаменателей имеют степень числа q. А поскольку  deg g = n-1, то  n-1  -  самая большая степень q в знаменателях коэффициентов многочлена g(х). Отсюда следует, что многочлен

  q g   Z[x]  (4)

Опираясь на вывод (4), мы преобразуем (3), умножив обе части этого равенства на q. Причем в правой части  q разобьем на два cомножителя  -  q  и  q:

  q f (х)  =  q (х - )  q g  (5)

Анализируя правую часть (5) мы видим, что q (х - )  -  это целочисленный многочлен. А поскольку, в силу (4), целочисленным многочленом является и второй сомножитель  q g.  Используя этот факт, проделаем следующие операции. В обе части равенств (5) внесем вместо х произвольное целое число t  Z, то получим

  q f (t)  =  q (t - )  q g(t)  (6)

Если (t - ) и g(t) целыми числами могут и не быть, то числа  q (t - ) и  q g(t) обязательно целые:

  (t  Z )   (q (t - ),  q g(t)  Z)  (7)

Понятно, что f(t)  Z  (f  -  целочисленный многочлен), а значит и  qf (t)  Z. Если учесть, что q(t - ) = qt-p, то (6) можно интерпретировать как делимость целых чисел:

  (qt-p) |  q f (t)  (8)