Глава 5. Наибольшие общие делители полиномов над целыми числами и последовательности полиномиальных остатков

В этой главе мы продолжаем обсуждать вычисление наибольших общих делителей полиномов и последовательностей полиномиальных остатков (PRS). (Читателю следует в этом месте вновь просмотреть разд. 3.2.1 и 3.2.2.) Однако, как отмечено в заглавии, мы ограничиваем изучение полиномами над кольцом целых чисел, где ключевой проблемой является ограничение роста коэффициентов. Мы детально исследуем два классических метода, существующие в литературе: метод Сильвестра-Габихта псевдоделения субрезультантных PRS (состоящий из двух алгоритмов), предложенный Сильвестром в 1853 г. и дополненный Габихтом в 1948 г., и метод матричной триангуляризации субрезультантных PRS, разработанный автором в 1986 г. (Akritas, 1986, 1988) (см. также историческое замечание 1 и рис. 5.1).

Рис. 5.1. Обзор исторического развития двух классических методов субрезультантных PRS. Метод, разработанный Сильвестром, следует использовать только для полных PRS, в то время как методом Габихта следует пользоваться, когда PRS неполна. Метод матричной триангуляризации может быть использован в обоих случаях.

Как мы убедимся позже, при использовании метода матричной триангуляризации коэффициенты полиномиальных остатков в определенных случаях меньше коэффициентов, полученных методом Сильвестра-Габихта; следовательно, первый метод лучше.

5.1. Введение и обоснование

Как мы уже видели, не является ни полем, ни евклидовой областью, однако по теореме 3.2.10 — это область с однозначным разложением на множители, т.е. каждый необратимый элемент (по существу) единственным образом может быть представлен в виде произведения неприводимых полиномов. (Напомним, что каждое поле является областью с однозначным разложением на множители, в которой каждый ненулевой элемент является обратимым (единицей) и нет простых элементов. Целые числа образуют область с однозначным разложением на множители, где обратимыми являются ±1, а простыми

В разд. 3.2.3 мы сказали, что полином в кольце называется примитивным, если его коэффициенты взаимно просты; это определение, так же как и утверждение теоремы 3.2.12, переносится на полиномы над произвольной областью с однозначным разложением на множители. Имеет место также следующая

Теорема 5.1.1. Пусть J — область с однозначным разложением на множители и — ненулевой полином. Тогда может быть единственным образом представлен в виде произведения где с а полином примитивен. Это разложение единственно с точностью до единиц кольца т.е. если то где b — единица кольца

Доказательство. Локазательство очевидным образом следует из результатов гл.

Константа с в теореме 5.1.1 — это наибольший общий делитель коэффициентов полинома называемый содержанием полинома и обозначаемый очевидно, что тогда полином называемый примитивной частью полинома и обозначаемый является примитивным полиномом в [Обычно

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

Например, рассмотрим два полинома Тогда

Отметим, что мы воспользовались теоремой 3.2.12.

Обратимся теперь к задаче нахождения наибольшего общего делителя двух полиномов в кольце являющемся не полем, а только областью с однозначным разложением на множители. Из приведенных выше рассуждений ясно, что мы можем вывести следующие важные соотношения:

Поэтому задача нахождения наибольшего общего делителя произвольных полиномов сводится к задаче нахождения наибольшего общего делителя примитивных полиномов.