3.2. Наибольшие общие делители полиномов над полем

В этом разделе мы ограничиваем наш анализ полиномами над полем. Глава 5 целиком посвящена вычислению наибольших общих делителей полиномов над кольцом целых чисел — гораздо более захватывающему сюжету (большой интерес представляет кйига Нетто (Netto, 1896)).

3.2.1. Делимость полиномов

Мы начнем со следующего определения:

Определение 3.2.1. Евклидоза область — это область целостности J вместе с функцией «степени» (или «порядка») такой, что

2. Для любых элементов из в J существуют элементы q и , обладающие евклидовым свойством или

Пример (евклидовы области). — евклидова область, потому что существуют такие, что

Отметим, что если , то также обладает свойством евклидовости; единственность здесь получается требованием неотрицательности . Кроме того, если 3 — поле, то — евклидова область, потому что в предыдущем

разделе мы видели, что для любых существуют единственные полиномы такие, что

Пример (неевклидовы области). поле рациональных чисел, с не является евклидовой областью, потому что и первое условие определения 3.2.1 не выполняется. Кольцо также не является евклидовой областью, потому что если мы разделим, например, на то частное не принадлежит кольцу

Определение 3.2.2. Пусть J — область целостности и Полином из назьшается наибольшим общим делителем полиномов что обозначается если выполняются следующие условия:

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

Мы можем найти наибольший общий делитель двух полиномов где J — область целостности и , используя несколько раз теорему о делимости (теорема 3.1.1). Соответствующий процесс назван алгоритмом Евклида для полиномов и работает следующим образом:

Поскольку для гарантировано, что эта последовательность делений заканчивается после самое большее шагов,

Теорема 3.2.3. Пусть J — область целостности и описанном выше алгоритме Евклида для полиномов последний отличный от нуля остаток это наибольший общий делитель полиномов

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

Последовательность остатков полиномов, полученная при выполнении алгоритма Евклида, называется последовательностью полиномиальных остатков

Следует, однако, заметить, что бессмысленно (в общем случае) говорить о «единственном» наибольшем общем делителе двух полиномов, поскольку в алгебраической системе 3 может быть много обратимых элементов, т.е. если — наибольший общий делитель полиномов то им является и если а - обратимый элемент, и, обратно, если — два наибольших общих делителя одних и тех же полиномов то для некоторого обратимого элемента а.

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

Стоит упомянуть, что в наибольший общий делитель двух целых чисел не единствен, если мы определяем его как «наибольший по абсолютной величине»; например, числа 6 и 9 будут иметь два наибольших по абсолютной величине общих делителя:

Два полинома в называются взаимно простыми, если любой их наибольший общий делитель — обратимая константа из J. В этом случае мы будем говорить, что единичный элемент кольца J — их наибольший общий делитель.

Ниже мы исследуем алгоритм Евклида для полиномов над полем — относительно простая процедура. Напротив, вычисление наибольшего общего делителя полиномов может значительно усложняться главным образом потому, что не евклидова область. При попытке вычислять полиномиальный коэффициенты полиномов в последовательности остатков могут становиться очень большими, и это замедляет вычисления. Мы будем в гл. 5 исследовать способы обхода этой трудности.