((n-2) Q(n)(ln-1) ( )

где остановка процесса наступает прн получении нулевого остатка. Последний ненулевой остаток, Р \ равен наибольшему общему делителю. Этот фаИг будет доказан в следующей теореме. Матричные обозначения позволяют кратко записать шаги алгоритма Евклида в виде

Теорема 2.6.3 (Алгоритм Евклида). Для двух заданных положительных чисел S и t, где s> t, пусть s<°> = s и = t. Решение рекуррентных уравнений

при г = 1 ,

sC) 1 г о 1 1 г (10 J [ 1 -QC) J [ п дается величиной

s< >-= НОД Is, (1, где п равно наименьшему целому числу, для которого = 0.

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

Поэтому

так что s > должно делить оба числа s и ( и, следовательно, делит НОД [s, Ц. Далее,

I -Q

так что любой делитель чисел s и t делит s* . Следовательно, НОД [s, i\ делит s и делится на s >..Таким образом,

sCi = НОД [s, П.

Это завершает доказательство. □

Из этой теоремы вытекает несколько важных следствий. Пусть

А 1 = П

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

Следствие 2.6..4. Для любых целых чисел s и t найдутся такие целые числа а и Ь что /

НОД [S, t] = as-hbt.

Доказательство. Достаточно доказать следствие для положительных S и t. Так как

и 6 = A\V.

□

Al) = П

s< > = НОД [s, t], то утверждение выполняется при а = Ли

Из доказательства этого следствия видно, как целые числа а и 6 вычисляются в виде элементов матрицы А. Остальные два элемента матрицы также имеют свою интерпретацию, для описания которой нам понадобится обратная к матрице А<>. Напомним, что О I 1 -QI) .

Отсюда видно, что определитель матрицы А равен (-l). Обратная к А<> матрица равна

.лй Air

Следствие 2.6.5. Получаемые в процессе алгоритма Евклида матричные элементы ЛИ Ли удовлетворяют равенствам s = (-l)M;) Н0Д(5, (], t = - (-1) ЛИ! НОД [S, 1].

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

= (-1)

-л!У

Утверждение вытекает отсюда непосредственно. □

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

Из этих вычислений сразу следует, что НОД [814, 187] равен 11 и что НОД 1814, 1871 = 3=Х 814-13 X 187.

2.7. Кольца многочленов

Для каждого поля F имеется кольцо F 1х], называемое кольцом многочленов на F. Во многих отношениях кольцо многочленов аналогично кольцу целых чисел. Чтобы сделать эту аналогию очевидной, в изложении данного раздела мы следуем разд. 2.6.

Многочленом над полем F называется математическое выражение

/ (х) = / л + / ,х -> + ...+f,x + U=t !,.

где символ х называется неопределенной переменной, а коэффициенты f . .... / принадлежат полю. Нулевым многочленом называется многочлен / (х) = 0. Степень многочлена обозначается deg / (х) и определяется как индекс старшего ненулевого коэффи-. циента. По определению степень нулевого многочлена полагается равной отрицательной бесконечности (-оо). Приведенным многочленом называется многочлен, старший коэффициент / которого равен 1. Два многочлена равны, если равны все их коэффициенты fi.

В кольце всех многочленов над заданным полем сложение и умножение определяются как обычные сложение и умножение многочленов. Такое кольцо многочленов определено для каждого поля F и обозначается символом F [х]. В исследованиях по этому кольцу элементы поля F иногда называются скалярами.

Суммой двух многочленов из F [х] называется другой многочлен из F [х], определяемый равенством

f{x) + g{x)=t(h + gi)x.

где, конечно, члены с индексом, ббльшим наибольшей из степеней многочленов f (х) я g (х), равны нулю. Степень суммы не превосходит наибольшей из этих двух степеней. Произведением двух

многочленов из F [х] называется многочлен из F [х], определяемый равенством

i \/=о

Степень произведения равна сумме степеней множителей. Если f (х) 7 О и g {х) О, то / {x)-g [х] Ф О, так как deg р (х) равно отрицательной бесконечности тогда и только тогда, когда р {х) = 0.

В кольце многочленов вычитание возможно всегда, а деление не всегда. Будем писать r{x]\s{x) и говорить, что многочлен S [х) делится на многочлен г (х), нли что многочлен г (х) делит S (х), или что г (х) явЛ-яется делителем многочлена s [х), если существует многочлен а [х), такой что г {х) а {х) = s {х). Ненулевой многочлен р [х], делящийся только на р {х) или на произвольный элемент а поля, называется неприводимым многочленом. Приведенный неприводимый многочлен называется простым многочленом.

Чтооы выяснить, является лн многочлен простым, надо знать поле, над которым он рассматривается. Многочлен д:* - 2 является простым над полем рациональных чисел, но не над полем вещественных чисел, над которым он распадается в произведение двух простых многочленов: р {х) = (х - i/2) (х + 7/2). Над полем комплексных чисел каждый из последних многочленов не является простым.

Если г {х) и делит s (jt), и делится на s {х), то г {х) = as (х). где к - элемент поля F. Это доказывается следующим образом. Должны существовать многочлены а (х) и b (х), такие что г (х) = = .s (х) а (х) и S (х) - г {х) b (х). Следовательно, г (х) = г (х) X X 6 (х) а (х). Но степень стоящего справа многочлена равна сумме степеней многочленов г (х), а (х) и (х). Так как эта сумма должна равняться степени многочлена, стоящего слева, то многочлены а (х) и b (х) должны иметь степени, равные нулю, т. е. являться скалярами.

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

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

В поле вещественных чисел операция дифференцирования вводится через операцию предельного перехода. Это определение возможно не всегда, так как в некоторых полях отсутствует по-

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

Определение 2.7.1. Пусть г (х) = тх + r ix; - Л-----h

+ гх + г есть многочлен над полем F. Формальной производной от г (х) называется многочлен вида

г (к) = (ПГ ) + ((я - 1) Г .0 X- +...+/

где новые коэффициенты вычисляются в поле F как суммы i копий элемента rj:

(iri) = Ti + О + ... +Г(. Легко проверить, что сохраняются многие полезные свойства производных, а именно, что

[r{x)s(x)V = г {x)s(x) + г(х) S (х),

и что если {х) делит г (х), то а (х) делит г (х).

В кольце многочленов над полем возможно сокращение; если с (х) а{х) = с (х) b {х) и с (х) отличен от нуля, то а (х) = b (х). Кроме того, в кольце многочленов имеется слабая форма деления, известная под названием деления с остатком или алгоритма деления.

Теорема 2.7.2 (Алгоритм деления для многочленов). Для каждого многочлена с {х) и ненулевого многочлена d (х) существует единственная пара многочленов Q (х) [частное) и s (х) {остаток), таких что

c{x) = Q (х) d{x) + s (X) и deg S (х) < deg d (х).

Доказательство. Частное и остаток находятся по элементарному правилу деления многочленов. Они единственны, так как если

с {X) = Qi (X) d (х) + Sl (х) = Q, (X) d{x) + s, (х),

d {X) 1С, (х) - Q, (X) 1 = S, (х) - S, (х). В правой части равенства стоит ненулевой многочлен, степень которого меньше deg d {х), а в левой - ненулевой многочлен, степень которого не меньше deg d (х). Следовательно, оба многочлена равны нулю, и представление единственно. □

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

Qix) =

с (X)

d(x)

Обычно мы будем больше интересоваться остатком, чем частным. Остаток часто записывается в виде

S (х) = R,( [с (х) 1,

s(x) = c(x) (modd(x)).

Можно записать также сравнение

s{x) = с (х) (mod d (х)),

которое обозначает, что многочлены s (х) и с (х) имеют один и тот же остаток при делении на d (х). Чтобы найти Rjix) Ic (х)1, казалось бы, надо выполнить деление. Однако имеется несколько приемов, позволяющих сократить и упростить необходимую для этого работу. Прежде всего заметим, что

R<nx) [с (х) 1 = R.ij [с (х) + a{x)d (х) I.

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

d(x) = x + Ed,x,

для упрощения можно член х заменить многочленом - Цйд: всюду, где это удобно. Такой прием упрощает вычисление остатка путем деления многочленов уголком .

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

Теорема 2.7.3. Если многочлен d (х) кратен многочлену g{x),

Rii..) 1 (x)] = R,w (й,., [а (х)11 для любого а (х).

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

а (х) = Qi (X) d (X) + [а {х)] =

= Q. (X) h (X) g {X) + Q2 (X) g {X) + Rj , [a (x)]), V

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

имеем

a{x) = q (X) g [х) + R, la (х) 1,

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

В качестве примера использования теоремы 2.7.3 разделим

3 Блейхуг Р.