х + д; + I Hi X* + -\- + X + 1. Деление уголком было бы утомительно, ио если вспомнить, что (х - У) (х + + х + + л + 1) = - 1, то можно сначала разделить на х - 1, а затем nax + c + x + x+ l. Тогда

1х + X + i] = х + X + I, и теперь деление ш х- + х + х + х + I тривиально, так что

1х + х+\] = х + х+1. Другое удобное правило дается следующей теоремой. Теорема 2.7.4.

(i) [а (X) + Ь {X)] = Ri U, [а (х)] + u) [Ь (х)].

(i i) Я J [а (дг). ft = I i? [а (X)] () 1Ь (х)] 1.

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

а(х)+Ь (х) = Q{x)d (х) + Rj [а (х) + Ь (х)]

а(х) + Ь (X) = Q (X) d (X) + R, [а [х)] +

+ Q (х) d (х) + i[b (х)].

Часть (i) вытекает из однозначности алгоритма деления. Часть (ii) доказывается аналогичным образом. □

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

Теорема 2.7.5 (теорема об однозначном разложении). Многочлен над некоторым полем однозначно разлагается в произведение элемента поля и простых над данным полем многочленов, причем степень каждого из них равна по меньшей мере 1.

Доказательство. Ясно, что входящим в произведение элементом поля является коэффициент где п - степень разлагаемого многочлена р (х). Этим элементом можно пренебречь и доказывать теорему для приведенных многочленов.

Предположим, что теорема не верна и пусть р (х) - приве денный многочлен наименьшей степени, для которого она не верна-

Тогда имеются два разложения,

р (х) = % (х) а (х) ... uft (х) = bi (х) Ь (х) ... bi (х),

где а (х) и bj (х) - простые многочлены.

Все многочлены at (х) должны отличаться от всех многочленов bj (х), так как в противном случае можно было бы сократить общие члены и получить многочлен меньшей степени, который можно разложить двумя разными способами.

Без потери общности предположим, что степень многочлена bi (х) не больше степени многочлена % (х). Тогда

а, (X) = Ь, (х) О (х) -f S (X), где deg s (х) < deg ft, (х) < deg а (х). Далее, S (X) а., (х).. .а (X) = Ь (х) [6, (х). ..bi(x)-Q (х) а (х).. .а (х)].

Разложим многочлен s (х) и стоящий в квадратных скобках многочлен на простые множители, разделив, если надо, на соответствующий элемент прля так, чтобы все множители были приведенными. Поскольку (х) не содержится в левой части, мы получили два различных разложения приведенного многочлена, степень которого меньше степени многочлена р (х). Это противоречие доказывает теорему. □

В силу теоремы об однозначном разложении теперь ясно, что НОД ls(x), Мх)1 и НОК [s(x), ((х)1 являются единственными для любых двух многочленов s (х) и f (х), так как наибольший общий делитель равен произведению всех общих для s {х) и t (х) простых делителей, причем каждый делитель входит в наименьшей из степеней, в которой он входит в s (х) и в ( (х), а наименьшее общее кратное равно произведению всех простых делителей, входящих либо в S (х), либо в t (х), причем каждый делитель входит в наибольшей степени, в которых он входит в s (х) или в t(x).

Из алгоритма деления для многочленов вытекает важное следствие, известное под названием алгоритма Евклида для многочленов. Для заданных двух многочленов s (х) и i (х) их наибольший общий делитель может быть вычислен с помощью итеративного применения алгоритма деления. Без потери общности можно полагать, что deg s (х) > deg i (х); алгоритм состоит из последовательности шагов

S (X) = Q(4 (X) t (X) + (X),

t(x) = QW (х)< )(х) + <2) (х), (x) = QW (*) (x) + t> (х), (( -2) Qim ((п-1) (х) + <( ) (х), <( -!) (х) = Qi +i) (х) (х).

Q(-> (X) =

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

Теорема 2.7.6 (Алгоритм Евклида для многочленов). Длядвух Ааданных многочленов s{x) и t (х) с deg s (х) > deg t (х) пусть s( ) (х) = s(x) и С (л;) = t (х). Решение рекуррентных ураенений

О 1 1 Г sC-n (х) I 1 -(X) J L ii - (х) при г - 1, п дается величиной

sC (х) = а НОД [s(x), <(х)1, где п - наименьшее положительное число, для которого С (х) = = О и а =?t О принадлежит полю.

Доказательство. Так как deg ( + (х) < deg (х), то для некоторого п обязательно наступит событие (. ) = О, так что алгоритм будет завершен. Легко проверить, что

sn (X)

Следовательно, s(x)

t{x)i

<(х)

QW (X) 1

так что многочлен s ) (х) должен делить оба многочлена s (х) и ((х) и, следовательно, НОД [s (х), t (х) I. Далее,

-Q< (X).

так что любой делитель обоих многочленов s (х) и ((х) должен делить и многочлен s ) (х). Таким образом, НОД [s(x),f(x)l делит s ) (х) и делится на s (х), и, следовательно,

s )(x) = а НОД [s(x), t(x)], где а - ненулевой элемент поля. Это завершает доказательство теоремы. □

Снова, как и в случае с кольцом целых чисел, получаем два важных следствия. Определим матрицу многочленов

А<> (х) = П

-Q<) (X)

А1-)(х),

где А< ) (х) есть единичная матрица. Тогда мы имеем следующий результат.

Следствие 2.7.7. Для любых двух многочленов s {х) и i (х) над полем F существуют два других многочлена а(х) иЬ (х) над тем же полем, такие что

НОД Is (х), ((х) 1 = а (х) s(x) + b (х) t (х).

Доказательство. Так как

)(х)

= А (X)

six) Их)

и sl ) (х) = я НОД Is (х), t (х) ], то утверждение следствия выполняется при а (х) = а Лп (х) и i (х) = a~A[V (х). □

Многочлены а (х) и А (х) получаются из элементов матрицы А< ) (х) делением на а . Два других элемента матрицы А (х) также имеют прямую интерпретацию, для описания которой нам надо вычислить обратную к матрице А<) (х). Напомним, что

А<) (х) = П

1 -Q<)(x)

Отсюда видно, что определитель матрицы Al (х) равен (-1), а обратная матрица дается равенством

А\[\х) AlJix) .ДЙ(х) Лй()

ЛЙ(х) -л!;(х) 1-ЛЙ(х) Л1(х)]

Следствие 2.7.8. Вычисляемые в процессе алгоритма Евклида эле.иенты ЛИ (х) и ЛЙ (х) удовлетворяют равенствам

S (х) = (-1) A[V (х) а НОД [S (х), t (х)), .

((X) = - (1) ЛЙ) (х) а НОД [S (X), ((X)).

Доказательство. Обратим первое равенство в доказательстве следствия 2.7.7, используя выведенную формулу для [А (х)]:

= (-1)

Л1?)(х) -ЛЙ)(. ) . -Л) (X) Л1?) (X)

Отсюда утверждение следствия очевидно. □

s(x) t(x)

sl ) (X)

В качестве примера использования алгоритма Евклида для многочленов вычислим НОД [s (х), ((х)1 при s (х) = х* - 1 и ((х) = г + + 2х + 1. Имеем

(X)

-\х-\ ix-ix+i x-l

jx + 5x + f -fx + W - fx + !][x= + 2x= + 2x + I

\h{x + 1) L 0 J

Таким образом, НОД [x* - 1, х + гх + 2x + 1 ] = x + 1. Кроме того.

х+ 1 = --)s(x) +

2 2 \

-g-X - X -г -g-j t (Х),

3 3 как обещано следствием 2.7.7.

Можно вычислить значение многочлена р (х) над полем F в любом элементе р этого поля. Для этого надо вместо неопределенной переменной х подставить соответствующий элемент fi и найти элемент р (Р) этого поля. Можно также вычислить значение многочлена в элементе из любого большего поля, содержащего поле F. Для этого надо- вместо неопределенной переменной х подставить значение элемента из расширения поля. Если F - поле вещественных чисел, то вычисление многочлена в расширении поля является знакомой операцией. Многочлены с вещественными коэффициентами часто приходится вычислять в поле комплексных чисел.

Элемент р поля называется корнем многочлена р (х), если р (Р) = 0. Корни многочлена не обязательно лежат в его собственном поле. Многочлен р (х) = х + I не имеет корней в поле вещественных чисел.

Теорема 2.7.9. Элемент р поля является корнем ненулевого многочлена р (х) тогда и только тогда, когда (х - р) является делителем многочлена р (х). Более того, если степень многочлена равна п, то многочлен имеет в поле не более п корней.

Доказательство. Согласно алгоритму, деления,

р (X) = (х - р) Q (х) -f S (х),

где степень многочлена s {х) меньше единицы, так что s {х) является элементом поля, s. Следовательно,

о = р (Р) = (Р - Р) Q (Р) -f So,

так что S {х) = So = 0. Наоборот, если {х - делит р (х), то р (X) = (X - Р) Q (х)

и р (Р) = (Р - W Q Ф) = 0. так что р является корнем многочлена р (х).

Теперь разложим многочлен Ь произведение скаляра и простых многочленов. Степень многочлена р (х) равна сумме степеней простых делителей, и один такой простой делитель имеется для каждого корня. Следовательно, число корней не может превосходить п. □

Теорема 2.7.10 (Интерполяция Лагранжа). Пусть ро, .... р,г - множество из п ~\- I различных точек, и пусть р фк) заданы для всех k ~ О, 1, п. Тогда найдется в точности один многочлен р (х) степени п или меньше, принимаюиий значения р (Pfe) для всех k = О..... п. Этот многочлен дается равенством

П(Х~{1;)

р{х) =

П (fii - Р;) 1Ф1

Доказательство. Непосредственной подстановкой р вместо х можно убедиться, что многочлен р (х) принимает в этих точках указанные значения. Однозначность представления следует из того, что если р (х) и р (х) - два таких многочлена, то многочлен Р (х) = р (х) - р (х) имеет степень, не превосхоД!щую п, но rt -f 1 корней Pft при А = О, п. Следовательно, Р (х) является нулевым многочленом. □

2.8. Китайские теоремы об остатках

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

Прежде чем строить формальную теорию, приведем простой пример. Выберем в качестве модулей т, = 3, mj = 4 и mj = 5 и положим М = ттт = 60. Для заданного числа с, лежащего в интервале О < с < 60, обозначим cj = [с1. Китайская теорема утверждает, что между шестьюдесятью такими числами с и шестьюдесятью векторами \с , с, Cj) соответствующих вычетов