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

  Замечание. Вывод (8) следует из (7) только в том случае, если мы знаем, что t ≠  ,  а это равенство может случиться, если   -  целый корень!

В ситуации равенства (8) (qt-p)  и q  являются взаимно простыми, поэтому из (8) мы делаем вывод:

  (qt-p) | f (t)  (9)

Соотношение (9) удобно переписать и интерпретировать так:

  Z  (10)

  Полученное (выведенное, доказанное) соотношение (10) прочитывается (звучит) следующим образом:

Если f  -  целочисленный многочлен,   -  его рациональный корень, то для любого целого t, не являющегося корнем многочлена f(х), число   является целым.  Если же (10) не выполняется, то не является корнем f(х).

Этот вывод или, что то же самое, соотношение (10) можно использовать для оптимизации вычислительных процедур отыскания рациональных корней целочисленных многочленов. При этом получается  следующий алгоритм,  -  назовем его оптимизатором,  -  описываемый ниже п. п. A, B, C, D, E. 

Итак, пусть ищутся рациональные корни целочисленного многочлена f.

A. Проверяем «на корень» простейшие целые числа 0, ±1. Причем, если какое-то из них является корнем, сразу устанавливаем кратность это корня и исключаем его из дальнейшего рассмотрения. Например, если 1 является  k - кратным корнем многочлена f(х), то делим f(х) на (х - 1), получаем частное g (сделать это можно при помощи мультисхемы Горнера):

  f = (х - 1)g  (11)

Из (11) следует, что все остальные рациональные корни многочлена f, если они существуют, являются корнями многочлена g. Теперь нужно искать рациональные корни многочлена g.  Но для многочлена g целые числа 0, ±1 уже не являются его корнями. Чтобы согласовать наши дальнейшие рассуждения с  проведенными ранее рассуждениями, будем считать, что числа 0, ±1 уже не являются корнями целочисленного многочлена f(х).

  B. По свободному члену и старшему коэффициенту многочлена  f составляем всевозможные дроби   -  «кандидаты на корень».

C. Выбираем поочередно для целого числа t значения ±1 и каждую из испытуемых на корень»  дробей    тестируем на свойство (10). Учитывая выбранные значения t, мы видим, что в знаменаполучается:  q – p  -  при t = 1 и  (–q – p)  -  при  t = - 1. Поскольку знак числа на делимость не влияет, мы, для удобства,  выберем во втором случае  p + q.  Получаем два соотношения

    Z,  Z,

которые можно объединить одной записью:

  Z.  (12)

В единой записи (12) указаны два соотношения, причем нужно обратить внимание на согласованность знаков: знаку  « + »  в числителе соответствует знак  « - »  в знаменателе и наоборот.

  Вывод из соотношения (10) (см. выше) говорит о том, что если для тестируемой «на корень» дроби хотя бы одно из двух требований не выполняется,  то дробь заведомо не является корнем целочисленного многочлена f(х). Следовательно, дальнейшей  проверке «на корень» подлежат лишь дроби , удовлетворяющие двум соотношениям (12).

D. Из всех дробей выбраковываем (отбрасываем) неудовлетворяющие хотя бы одному из требований  (12).

E. Оставшиеся дроби  проверяем «на корень» (прямой подстановкой или по схеме Горнера).

Изложенное  (п. п. A, B, C, D, E)  - один из возможных оптимизаторов отыскания рациональных корней целочисленных многочленов. Существуют и другие. Приведем еще один, основанный на том соображении, что арифметические операции проще осуществлять над целыми чем над дробными (рациональными) числами.

Пусть требуется найти рациональные корни целочисленного многочлена (1) §13. Умножим его на (a) и, сделав замену переменных

  y = ax,  (13)

получим некоторый новый целочисленный многочлен  g  от переменной  y, связанный с f очевидным соотношением:

  (a) f(x)  =  g(y),  (14)

где  g  -  нормированный многочлен той же степени n (именно для этого выбиралась замена (13)). Понятно, что, отыскав корни одного из многочленов f  или  g, мы  -  через (13)  -  найдем корни другого. Но у нормированного многочлена  g  в качестве рациональных корней могут быть только целые. Найдя эти корни  -  целые значения  y  -  (или установив, что их нет), мы, обратной заменой через (13), найдем все рациональные корни исходного многочлена f. Описанная процедура и есть второй оптимизатор отыскания рациональных корней целочисленных многочленов.

Глава II. Расширения числовых полей. Решение геометрических задач на построение циркулем и линейкой.

§1. Простые и составные расширения числовых полей, их строение

Напомним, что числовым полем мы называем любое подполе  поля комплексных чисел C. Числовыми, следовательно, являются стандартные поля Q и R. Но это  -  не единственные числовые поля. Описываемые ниже процедуры расширения доставляют бесконечно много примеров других числовых полей. Строго говоря, эти процедуры применимы для конструкций любых полей. Мы ограничиваемся числовыми полями из чисто утилитарных соображений: эти поля, вместе с их приложениями к геометрическим задачам на построение, непосредственно примыкают к кругу вопросов школьного курса математики.

Определение. Пусть  F  -  произвольное числовое поле и  S  -  любое числовое множество:  F < C,  S C. Расширением поля  F  множеством  S  (при помощи множества  S)  -  обозначается  F(S)  -  называют наименьшее числовое поле, содержащее в себе как F так и  S: 

  F < F(S)    S F(S)  (1)

Во-первых, заметим, что, при выбранных  F и S, числовые поля. удовлетворяющие (1), обязательно существуют, например, само поле C. Поэтому искомое поле F(S) является пересечением всех таких полей.

В дальнейшем мы ограничимся специально отобранными множествами  S:  1. S = {б}  -  состоит из одного числа и 2. S = {б, б, …,б}  -  состоит из n чисел. В первом случае расширение  -  обозначают  F(б)  -  называется простым расширением поля  F  числом  б, во втором  -  F(б, б, …,б)  -  составным расширением этого поля числами  б, б, …,б.

Строение простого и составного расширений. Рассмотрим простое расширение F(б)  числового поля F числом б. Тогда довольно легко усматривается выполнимость следующей цепочки импликаций:

  (f, g  F[x])    (f(б), g(б)    F(б))    (     F(б))  (2)