Практическое вычисление частного и остатка выполняется с помощью простого правила деления многочленов «уголком». Обычно мы будем больше интересоваться не частным, а остатком. Остаток можно также записать в виде s (х) = Rd(x) [с {х)]. Часто остаток называют вычетом многочлена с (х) по модулю многочлена .d {х). Несколько отличным понятием является сравнение

S (х) ~ с {х) (mod d (х)),

которое означает, что при делении на d (х) многочлены s (х) и с (х) дают один и тот же остаток, но степень многочлена с (х) не обязательно меньше степени многочлена d (х).

Иногда при вычислении остатка удобнее разбивать деление на этапы. Это можно осуществить с помощью следующей теоремы.

Теорема 4.3.3. Пусть d (х) кратен многочлену g (х). Тогда для любого а (х)

Rg м [а {X)] = Rg [Ra [а(х)]].

Доказательство. Пусть d (х) = g (х) h (х) для некоторого h (х). Раскрывая правую часть, получаем

а (X) = Q, (X) d (X) -Ь Ra [а (х)] =

= Qdx)g(X) h (X) + (X) g (x) + Rg [Ra [a (x)]],

где степень остатка меньше deg g (x). Раскрывая левую часть, имеем

а(х) = Q(x)g(x) + i?g(;,)(a(x)],

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

Теорема 4.3.4.

(i) Rd w [а (х) f b (X)] = Ra [a (x)] + Ra (.) [b (x)],

(ii) Rd w [a (x) b (x)] = Ra (.) Rd м [a (x)] Ra м [b (x)]}.

Доказательство сводится к упражнению: использовать алгоритм деления для выражений в обеих частях равенства и приравнять остатки. □

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

Теорема 4.3.5 (теорема сб однозначном разложении).

Ненулевой многочлен р (х) над некоторым полем однозначно {с точностью до порядка следования множителей) разлагается в произведение элемента поля и простых многочленов над этим полем.

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

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

Р (х) = 1 (х) «2 (х) ... ак (х) = (х) bi (х) ... bj (х),

где % {х) и bj [х) - простые многочлены.

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

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

«1 {х) = 1 {х) h {х) -\- S {х),

где deg s {х) < deg b- {х) < deg {х). Далее,

s (х) а. {х) ад (х) ... ак (х) =

= bi (х) (х) ... bj (х) -h {х) а [х] ... ак {х) ].

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

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

Из алгоритма деления многочленов вытекает важное следствие, изнестнсе под названием алгоритма Евклида для многочленов.

Теорема 4.3.6 (алгоритм Евклида для многочленов).

Наибольший общий делитель двух многочленов г (х) и s (х) над

Гп 1 (х) = Qn+i (х) /-„ (х),

и процесс обрывается, как только получается равный нулю остаток. Тогда Гп (4 = а НОД [г (х), s (х)], где а - некоторый скаляр.

Доказательство. Отправляясь от первого уравнения, видим, что НОД [г (х), S (х) ] делит и делимое, и делитель, и, следовательно, остаток. Проводя это рассуждение далее по всем уравнениям, видим, что НОД [г (х), S (х)] делит (х). Отправляясь от последнего уравнения, видим,чтог„ (л:) делит делитель и остаток, так что он делит и делимое. Проводя это рассуждение по всемуравне-ниям вплоть до первого, видим, что Гп*{х) делит НОД [г (х), s (х)]. Так какГп (х) делит НОД [г (х), s (х)] и делится на него, то полу-чаемутверждение теоремы. □

Следствие 4.3.7. НОД [г (х), s{x)] = а (х) г (х) + b {х) s {х), где а (х) и b (х) -многочлены над GF (q).

Доказательство. Последнее уравнение с ненулевым остатком в утверждении предыдущей теоремы дает выражение многочлена г„ (х) через r„ i (х) и г„ 2 (х). Перебирая уравнения снизу вверх, исключаем сначала r„ i (х), затем г„ 2 (х) и т. д. и в конце концов получим выражение г„ (х) только через г (х) и s (х). □

Для произвольного элемента р поля GF (q) можно вычислить значение мнсгочлена над GF (q) в этой точке, подставив элемент Р вместо неопределенной переменной. Например, пусть над GF (3)

р (х) = 2x5 4. + + Тогда (см. рис. 4.1) получаем

р (0) = 2-05 + О" + 0 + 2 = 2,

yt7 (1) = 2-15 + 1* + Р + 2 = О, • •

yt7 (2) = 2-2 + 2" + 2 + 2 = 2.

В случае поля вещественных чисел известной процедурой является вычисление значений многочлена в расширении этого поля; широко применяется вычисление значений многочлена с вещественными коэффициентами в поле комплексных чисел. Аналогично

полем GF (q) можно вычислить с помош,ыо итеративного применения алгоритма деления. Если deg s {х) deg г {х) О, то последовательность вычислений такова:

S (х) = Qi (х) г (х) + Г1 (х),

г (х) = Q2 (х) /-1 (х) + г2 (х),

Гг {X) = Qs {X) Г2 ix) + Гз {X),