разложения называется прумитивным, если его коэффициенты взаимно просты (не путайте это понятие с совершенно другим понятием примитивных полиномов по модулю р, которое обсуждалось в разделе 3.2.2). Следующий факт, представленный для полиномов над целыми числами К. Ф. Гауссом (С. F. Gauss) в 42 разделе его знаменитой книги Disquisitiones Arithmetics (Leipzig, 1801), имеет первостепенную важность.

Лемма G (Лемма Гаусса). Произведение примитивных полиномов над областью ед1тственного разложения примитивно.

Доказательство. Пусть и{х) = UmX" Ч-----huo и v{x) = VnX" Ч-----\-vo - примитивные полиномы. Пусть р - любой простой элемент области; тогда следует показать, что р не делит все коэффициенты u{x)v{x). По условию имеется такой индекс j, что Uj не делится на р, и такой индекс к, что Vk не делится на р. Пусть j и к - наименьшие такие индексы; тогда коэффициент при х в u{x)v{x) равен

UjVk + Uj+iVk-i Ч- • • • Ч- Uj+kVo Ч- Uj-iVk+i Ч- • • • Ч- uoVk+j.

Так как первый член этой суммы не делится на р, а все остальные делятся, на р не делится и вся сумма.

Если ненулевой полином и{х) над областью единственного разложения 5 не примитивен, можно записать и{х) = pi ui{x), где pi-простой элемент из 5, делящий все коэффициенты и{х), а ui{x)-другой ненулевой полином над S. Все коэффициенты uj (х) имеют на один простой множитель меньше соответствующих коэффициентов и{х). Теперь, если ui(x) не примитивен, можно записать ui{x) = Р2 • U2{x) и т. д. Этот процесс безусловно прекратится при представлении и{х) = с • Uk{x), где с е 5 и Uk{x)-примитивен. Фактически имеется соответствующая лемме G лемма Н.

Лемма Н. Любой ненулевой полином и{х) над областью единственного разложения S можно разложить на множители в виде и{х) = с • t;(a;), где с представляет собой элемент S, а t;(a;)-примитивный полином. Кроме того, это представление единственно в том смысле, что если и = ci vi{x) = С2 V2{x), го ci = ас2 и V2{x) = at;i(a;), где а - обратимый элемент S.

Доказательство. Мы уже показали, что такое разложение существует, так что доказательства требует только единственность разложения. Положим, что ci • vi (х) = С2 • V2{x), где t;i(a;) и иг (г) -примитивные полиномы. Пусть р - некоторое простое из 5. Если р* делит ci, то оно делит и сг; в противном случае р* должно делить все коэффициенты сг • иг (г) и р должно делить все коэффициенты иг (г). Таким образом, получается противоречие с посылкой примитивности V2{x). Точно так же р* делит С2 только в том случае, если р* делит ci. Следовательно, в силу единственности разложения cj = асг, где а обратимо; поскольку О = асг • t;i(a;) - сг • V2(x) = Сг • (at;i(a;) - V2{x)), получаем at;i(a;) - V2{x) = 0.

Таким образом, можно записать любой ненулевой полином и{х) в виде

и(х) = соЩ(м) • рр(и(а;)), (3)

где cont(u) - содержание (content) и, представляющее собой элемент 5, а рр (и(а;))- примитивная часть {primitive part) и{х), являющаяся примитивным полиномом

над 5. В случае, когда и{х) = О, удобно определить cont(u) = pp(u(a:)) = 0. Комбинация лемм G и Н приводит к соотношениям

cont(u v) = a cont(u) cont(u),

pp(u(a;) -vix)) =bpp{u{x)) pp{v{x)),

где a и b - обратимые элементы, зависящие от пути вычисления содержимого, причем а6 = 1. При работе с полиномами над целыми числами обратимыми элементами являются только -Ы и -1, и поэтому удобно определить рр(и(а:)) так, чтобы ее старший коэффициент был положителен; тогда (4) истинно при а - b = I. При работе с полиномами над полем можно принять cont(u) = £{и), так что рр(и(а:)) будет нормированным полиномом; в этом случае (4) вновь выполняется при а - 6=1 для всех и{х) и v{x).

Например, пусть мы работаем с полиномами над целыми числами и пусть и{х) = -26х + 39 и v{x) = 21х + 14. Тогда

cont(u) = -13, рр{и{х)) = 2х - 3,

cont(t;) = -Ь7, pp{v{x)) = За; -Ь 2,

cont(u • v) - -91, pp(u(a;) • t;(a;)) = ба; + 4x -9x -6.

Наибольшие общие делители. В случае единственного разложения можно говорить о наибольшем общем делителе двух элементов; это общий делитель, который делится на наибольшее количество простых элементов (см. формулу 4.5.2-(б)). Однако, поскольку область единственного разложения может иметь много обратимых элементов, в определении наибольшего общего делителя присутствует некоторая неоднозначность. Если w - наибольший общий делитель и и v, то а w, где а - обратимый элемент, тоже является наибольшим общим делителем. И обратно, предположение о единственности разложения на множители влечет за собой вывод о том, что если и wi, и шг представляют собой наибольшие общие делители и и V, то wi = а W2, где а - некоторый обратимый элемент. Другими словами, не имеет смысла говорить о конкретном наибольшем общем делителе (в оригинале - "to speak of the greatest common divisor". - Прим. перев.) и-a v. Существует целое множество наибольших общих делителей, каждый из которых отличается от других на обратимый множитель.

Рассмотрим теперь задачу поиска наибольшего общего делителя двух данных полиномов над алгебраической системой S, первоначально поставленную Пабло Ну-ньесом (Pablo Nunez) в работе ЫЪю de Algebra (Antwerp, 1567). Если 5 -поле, то проблема относительно проста; наш алгоритм деления, алгоритм D, может быть расширен до алгоритма вычисления наибольшего общего делителя так же, как алгоритм Евклида (алгоритм 4.5.2А), находящий наибольший общий делитель двух целых чисел, получается на основе алгоритма деления целых чисел:

если t;(a;) = О, то gcd{u{x),v{x)) = и{х);

в противном случае gcd(u(a;),t;(a;)) = gcd(t;(a;),r(a;)),

где г(а;) определяется (1). Эта процедура называется алгоритмом Евклида для полиномов над полем. Впервые она была использована Симоном Стевином (Simon Stevin) в LArithtnetique (Leiden, 1585); см. А. Girard, Les (Euvres Mathematiques de Simon Stevin 1 (Leiden, 1634), 56.

Например, необходимо найти gcd + + 10x + Юх + Sa: + 2а: + 8 и За;® + 5а;* + 9а;2 + 4а; + 8, mod 13, используя алгоритм Евклида для полиномов над полем целых чисел по модулю 13. Сначала запишем только коэффициенты для того, чтобы показать шаги алгоритма D.

9 0 7

3050948)1010 10 10 82 1 0 6 0 3 10 7

0 8 0 7 О 12 8 8 0 9 О 11 2 4

О 11 О 3 0 4 Так что х +х + 10а;* + Юа; + Sa; + 2а; + 8 равно

{9х + 7)(3х® + 5х* + 9х + 4х + 8) + (Их* + Зх + 4).

Аналогично

Зх® + 5х* + 9x2 + 4х + 8 = (52 + 33.2 + 4) + (4; + 1);

Их* + 3x2 + 4 = (g3 5Д.2 5(4 1) 12;. (6)

4х + 1 = (9х + 12) -12 + 0.

(Знак равенства здесь означает равенство по модулю 13, так как все арифметические действия над коэффициентами выполняются по модулю 13.) Проведенное вычисление показывает, что 12 является наибольшим общим делителем двух исходных полиномов. Так как любой ненулевой элемент поля представляет собой обратимый элемент области полиномов над полем, для полей принято делить результат выполнения алгоритма на его старший коэффициент, получая нормированный полином, и именно его имеют в виду, говоря о наибольшем общем делителе (в оригинале - "is called the greatest common divisor". - Прим. перев.) двух данных полиномов, gcd, вычисленный в (6), таким образом, оказывается равным 1, а не 12. Последний шаг в (6) может быть опущен, так как если deg(u) = О, то gcd(m(x),t;(x)) = 1 безотносительно к выбору полинома и{х). В упр. 4 определяется среднее время работы алгоритма Евклида над случайными полиномами по модулю р.

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

cont(gcd(u,u)) = а gcd(cont(u),cont(u)),

pp(gcd(u(x),u(x))) = 6-gcd(pp(u(x)),pp(u(x))),

где а и Ь - обратимые элементы. Здесь gcd(u(x), и(х)) означает любой полином от X, являющийся наибольшим общим делителем и{х) и v{x). Формулы (7) сводят проблему поиска наибольшего общего делителя произвольных полиномов к поиску наибольшего общего делителя примитивных полиномов.

Алгоритм D деления полиномов над полем может быть обобщен для псевдоделения полиномов над любой алгебраической системой, представляющей собой коммутативное кольцо с единицей. Можно заметить, что алгоритм D требует явного деления только на i{v), старший коэффициент - v(x) и шаг D2 вьшолняется в точности m - п -Н 1 раз. Таким образом, если и{х) и v{x) начинаются с целых коэффициентов