АЛГЕБРА (3-й семестр)

– многочлен с коэффициентами из K.
Для любого c K положим
,
где выражение в правой части понимается как результат операций в кольце K.
Получаемый при этом элемент f(c) кольца K называется значением многочлена f(x) при x=c
(или в точке с по аналогии со случаем , когда с можно представлять как точку действительной оси).
Следовательно, многочлен f(x) определяет функцию f : K  K.

что мы дали формально-алгебраическое определение равенства двух многочленов, согласно которому

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

что два многочлена равны с функциональной точки зрения.
Обязательно ли

они равны с алгебраической точки зрения?
Ответ на этот вопрос будет отрицательным для любого конечного кольца K={c1,c2,…, cn}. Над таким кольцом одну и ту же функцию определяют два различных многочлена
f(x)=(x-c1)(x-c2)…(x-cn)+x и g(x)=x.
Значит, если K – конечное кольцо, то алгебраическая и функциональная точки зрения на многочлен не совпадают.
Основная цель этого пункта доказать, что если K – бесконечная область целостности, то обе эти точки зрения на многочлен совпадают, т.е. различные с алгебраической точки зрения многочлены определяют различные функции.

(1*)
Отметим сначала еще одно следствие теоремы о делении с остатком.
Следствие 2 (теорема Безу). Остаток от деления многочлена f(x) на двучлен x-c равен значению многочлена f(x) при x=c.
◘ Полагая x=c в равенстве (1*) , получим f(c)=r. ◙
(Этьен Безу (1730–1783) – французский математик).
Введем теперь понятие корня многочлена.
Определение 1. Элемент c кольца K называется корнем многочлена f(x), если f(c)=0.
Частным случаем теоремы Безу является
Следствие 3. Если элемент c кольца K является корнем многочлена , то остаток от деления многочлена f(x) на двучлен x-c равен 0. ◙

следствий 1 и 3 легко вытекает
Следствие 4 (характеристическое свойство корня).

Элемент c кольца K является корнем многочлена f(x) тогда и только тогда, когда f(x) делится на двучлен x-c. ◙
Определение 2. Элемент c кольца K называется корнем многочлена f(x) кратности k, если f(x) делится на (x-c)k и не делится на (x-c)k+1. Корни кратности 1 называются простыми корнями.

дальнейшем полезной будет следующая
Т е о р е м

а 2 (о числе корней). Число корней (с учетом их кратности) ненулевого многочлена f(x) над областью целостности K не превосходит его степени.
◘ Докажем это утверждение с помощью индукции по степени n многочлена f(x).
Многочлен нулевой степени вообще не имеет корней, так что для него теорема 2 справедлива.
Предположим теперь, что n>0 и теорема 2 справедлива для всех многочленов степени n-1, и докажем её для любого многочлена f(x) степени n.
Если f(x) не имеет корней, то теорема 2 верна.

с – корень f(x) степени n .
По характеристическому

свойству корня f(x) делится на x-c, т.е.
f(x)=(x-c)q(x), (4)
где q(x) – некоторый многочлен степени n-1, имеющий по предположению индукции не более n-1 корней.
Из равенства (4) видно, что любой корень многочлена q(x) является корнем многочлена f(x).
С другой стороны, поскольку K – целостное кольцо, любой отличный от с корень многочле-на f(x) является корнем многочлена q(x).
Отсюда следует, что f(x) имеет не более чем n корней. ◙

е о р е м а 3 (тождественности многочленов). Если

K – бесконечная область целостности, то два многочлена f(x) и g(x) кольца K[x] равны между собой тогда и только тогда, когда они принимают равные значения при любом значении x из K.
Эта теорема показывает, что алгебраическая и функциональная точки зрения на многочлен над бесконечной областью целостности совпадают.
Доказательство теоремы 3 непосредственно будет вытекать из одной леммы, следствия из нее и очевидного факта, что равные многочлены определяют равные функции.

1. Пусть K – область целостности. Если многочлены f(x) и

g(x), степени которых не превышают числа n, принимают равные значения для n+1 различных элементов кольца K, то f(x)=g(x).
◘ Пусть f(ci) = g(ci) (i=1,2,…, n, n+1). Предположим, что f(x)  g(x) и рассмотрим многочлен h(x)= f(x)-g(x).
Он ненулевой, его степень не превосходит числа n и в тоже время он имеет n+1 корней c1,c2,…, cn, cn+1, что противоречит теореме 2.
Следовательно, f(x)=g(x). ◙
Из леммы 1 вытекает
Следствие 5. Если многочлены f(x) и g(x) принимают равные значения на некотором бесконечном подмно-жестве области целостности K, то f(x)=g(x). ◙

вопросов:
Обоснование алгоритма нахождения НОД многочленов с помощью алгоритма Евклида. Нахождение

линейного представления НОД многочленов.
Свойства взаимно простых многочленов.
НОК многочленов и его нахождение .

над произвольным полем P.
Определение 1. Наибольшим общим делителем (НОД)

многочленов
f1(x), f2(x), …, fm(x) из кольца P[x]
называется многочлен d(x), обладающий следующими свойствами:
1) каждый из многочленов f1(x), f2(x), …, fm(x) делится на d(x), т.е. d(x) является их общим делителем;
2) d(x) делится на любой общий делитель многочленов f1(x), f2(x), …, fm(x).
Обозначение: НОД(f1(x), f2(x), …, fm(x)).

определяется с точностью до множителя нулевой степени (любые два НОДа

должны делиться друг на друга);
нормированный НОД определяется однозначно.
НОД двух многочленов f(x) и h(x) может быть найден при помощи алгоритма Евклида.
Прежде всего, ясно, что если ,
то НОД(f(x),h(x)) = h(x).

.
Делим с остатком многочлен f(x)

на многочлен h(x),
затем многочлен h(x) – на остаток от первого деления,
затем остаток от первого деления – на остаток от второго деления и т.д.,
пока не получится нулевой остаток (последнее неизбежно, так как степени остатков строго убывают).

е о р е м а 3. Для любых многочленов

f(x) и h(x) из P[x] существует их НОД(f(x),h(x)), причем если
, то он совпадает с последним неравным нулю остатком в равенствах (E) Евклида, т.е.
НОД(f(x),h(x))=rk(x). ◙

rk(x) является общим делителем многочленов f(x) и h(x).
Учитывая последнее

равенство в (Е), из предпоследнего равенства получим, что ,
из третьего снизу равенства в (Е) имеем и т.д.
Поднимаясь снизу вверх по равенствам (Е) через конечное число шагов получим, что и . .
Таким образом, условие 1) определения 1 для многочлена rk(x) выполнено.

любой общий делитель многочленов f(x) и h(x).
Из первого равенства

системы (Е) легко получаем, что ;
из второго – ; из третьего – и т.д.
Спускаясь по равенствам (Е), через конечное число шагов получим, что .
Таким образом, и условие 2) определения 1 для многочлена rk(x) выполнено.
Итак, НОД(f(x),h(x))=rk(x). ◙

действительными коэффициентами найдем НОД многочленов

и .
◘ Делим f(x) на h(x) с остатком:

константы, для удобства можно разделить полученный остаток на -3

и выполнять деление многочлена h(x) на r1(x) : (-3), что не скажется на результате.
Однако, имея в виду дальнейшее линейное представление НОД, мы не будем делать этого и все вычисления будем производить точно.

остаток r2(x)=0 равен нулю, то НОД(f(x),h(x))= x+1. ◙

fm(x) может быть найден индуктивным способом на основании следующей формулы:
.
Таким

образом, для того чтобы найти наибольший общий делитель многочленов f1(x), f2(x), ..., fm(x) , следует в соответствии с этой формулой найти сначала
d1(x)=НОД(f1(x),f2(x)), затем
d2(x)=НОД(d1(x),f3(x)) и т.д.;
и, наконец, найти многочлен
dm-1(x)=НОД(dm-2(x),fm(x)) ,
который и будет искомым наибольшим делителем.

а 4 (о линейном представлении НОД): Если d(x) = НОД(f(x),h(x)),

где f(x) и h(x) – многочлены из кольца P[x], то в P[x] существуют такие многочлены u(x) и v(x), что
f(x)u(x) + h(x)v(x)=d(x) . (5)
◘ Для доказательства этого утверждения достаточно выразить НОД(f(x),h(x))=d(x)=rk(x) из предпоследнего равенства системы (Е), затем заменить в нем rk-1(x) выражением его из предшествующего равенства и т.д. Продолжая этот процесс, поднимаемся по равенствам Евклида снизу вверх до тех пор, пока не исключим все остатки и получим выражение вида (5). ◙

(5)
◘

Действительно из (Е)




Имеем НОД(f(x),h(x))=d(x)=rk(x) = rk-2(x)- rk-1(x)qk-1(x) = = rk-3(x)(-1) + rk-2(x)(1+qk-1(x)qk-2(x)) = … = = f(x)u(x)+h(x)v(x).

(5)
Пример

4. Проиллюстрируем теорему 4, опираясь на вычисления примера 3.
Запишем равенства (Е) для выполненных там делений, при этом будем использовать пока буквенные обозначения:

Выражая r2(x) из последнего равенства (напомним, что в примере 3 НОД(f(x),h(x))= r2(x)) и подставляя в него выражение из первого равенства, получим

(5)


или

f(x)u(x) + h(x)v(x)=d(x) , где ,
и d(x)=x+1.
Таким образом,
,
где и ,
искомое линейное представление
НОД(f(x),h(x))= x+1. ◙

из кольца P[x] называются взаимно простыми, если их НОД равен

некоторому элементу с из поля P.
Поскольку НОД многочленов определяется с точностью до множителей нулевой степени, то можно считать, что для взаимно простых многочленов f(x) и h(x) их НОД равен 1.
Отметим два следствия из теоремы 4.
Следствие 5. Многочлены f(x) и h(x) взаимно просты тогда и только тогда, когда в кольце P[x] существуют такие многочлены u(x) и v(x), что
f(x)u(x) + h(x)v(x)=1 . (6)

тогда и только тогда, когда в кольце P[x] существуют такие

многочлены u(x) и v(x), что
f(x)u(x) + h(x)v(x)=1 . (6)
◘ Пусть f(x) и h(x) взаимно просты, т.е. НОД(f(x),h(x))= 1. Тогда равенство (6) вытекает непосредственно из теоремы 4.
Обратно, пусть равенство (6) выполняется и d(x) – общий делитель многочленов f(x) и h(x).
Тогда из равенства (6) получаем, что .
Это означает, что d(x)P.
Следовательно, f(x) и h(x) – взаимно простые многочлены. ◙

– многочлены из кольца P[x], d(x)=НОД(f(x),h(x)), то многочлены

и взаимно просты.
◘ В самом деле, по теореме 4 справедливо равенство
(5).
Поделив его на d(x), получим равенство
,
из которого вытекает взаимная простота многочленов f1(x) и h1(x). ◙

Если многочлен f(x) взаимно прост с многочленами g(x) и h(x),

то он взаимно прост и с их произведением g(x)h(x).
◘ Ввиду взаимной простоты многочленов f(x) и g(x) по следствию 5 для них существует представление вида
f(x)u(x) + g(x)v(x) = 1.
Умножая это равенство на h(x) получим равенство
f(x)(u(x)h(x)) + (g(x)h(x))v(x) = h(x). (7)
Предположим, что НОД(f(x), g(x)h(x))= d(x). Из равенства (7) вытекает, что d(x) – общий делитель многочленов f(x) и h(x). Но многочлены f(x) и h(x) взаимно простые и поэтому d(x)=1.
Таким образом, многочлен f(x) взаимно прост с произведением g(x)h(x). ◙

h(x) и многочлены g(x) и h(x) взаимно просты, то многочлен

f(x) делится на h(x).
◘ Из взаимной простоты многочленов g(x) и h(x) по следствию 5 следует существование многочленов u(x) и v(x) со свойством
g(x)u(x) + h(x)v(x) = 1.
Умножая это равенство на f(x), получим равенство
(f(x)g(x))u(x) + h(x) (f(x)v(x)) = f(x).
Из последнего равенства легко вытекает делимость f(x) на h(x). ◙

g(x) и h(x), которые взаимно просты между собой, то f(x)

делится и на их произведение g(x)h(x).
◘ Пусть f(x) делится на g(x) и h(x).
Тогда f(x)=g(x)s(x) и g(x)s(x) делится на h(x).
Отсюда, ввиду взаимной просты многочленов g(x) и h(x), по свойству 2° получаем, что s(x) делится на h(x), т.е. s(x)= h(x)t(x) для некоторого многочлена t(x).
Подставляя найденное выражение для s(x) в равенство f(x)=g(x)s(x) окончательно получим f(x)=(g(x)h(x))t(x). ◙

многочленов f1(x), f2(x), …, fm(x) из кольца P[x] называется многочлен

k(x), обладающий следующими свойствами:
1) k(x) делится на каждый из многочленов f1(x), f2(x), …, fm(x), т.е. является их общим кратным;
2) любое общее кратное многочленов делится на k(x).
Обозначение: НОК(f1(x), f2(x), …, fm(x)).

НОК определяется с точностью до множителя нулевой степени (любые два

НОК должны делиться друг на друга); нормированное НОК определяется однозначно.
Т е о р е м а 5 (о НОК двух многочленов). Любое общее кратное многочленов f(x) и h(x) имеет вид

, где t(x) P[x] . (8)
При этом
. (9)

и

.
Используя эти обозначения, перепишем равенство
(8)
в виде
.
Отсюда видно, что любой многочлен вида (8) является общим кратным многочленов f(x) и h(x).

многочленов f(x) и h(x). Покажем, что оно имеет вид
(8).

По условию k(x) делится на f(x) и поэтому k(x)=f(x)q(x). С другой стороны, поскольку , то , и, следовательно, .
Так как по следствию 6 многочлены f1(x) и h1(x) взаимно просты, отсюда и из свойства 2° взаимно простых многочленов получаем, что , т.е. q(x)=h1(x)t(x). Но тогда имеем
.
Таким образом, любое общее кратное k(x) многочленов f(x) и h(x) имеет вид (8) и первое утверждение теоремы 5 доказано.

из равенства
(8)

следует, что многочлен

есть общее кратное многочленов f(x) и h(x) и, что любое общее кратное f(x) и h(x) на него делится.
Таким образом,
. ◙

а 5 (о НОК двух многочленов). Любое общее кратное многочленов

многочленов f(x) и h(x) имеет вид
, где t(x) P[x] . (8)
При этом
. (9)

Из теоремы 5 вытекает
Следствие 7. Наименьшее общее кратное двух взаимно простых многочленов равно их произведению. ◙

R[x] с действительными коэффициентами найдем НОК многочленов

и .
Согласно вычислениям примера 1 НОД(f(x),h(x)=x+1. По формуле (8) имеем
.

Поделив сначала многочлен на двучлен x+1, получим многочлен .
Теперь =
= = .

…, fm(x) может быть найден индуктивным способом на основании следующей

формулы:
.
Таким образом, для нахождения НОК(f1(x), f2(x), …, fm(x)) следует в соответствии с этой формулой найти сначала k1(x)=НОK(f1(x),f2(x)), затем k2(x)=НОК(k1(x),f3(x)) и т.д.; и, наконец, многочлен km-1(x)=НОК(km-2(x),fm(x)), который и будет искомым НОК.