2008-09 учебный год Доцент Мартынова Т. А.
ЛЕКЦИЯ 3 Доцент Мартынова Т.А.
Пусть – многочлен с коэффициентами из K. Для любого c K положим , где выражение в правой части понимается как результат операций в кольце K. Получаемый при этом элемент f(c) кольца K называется значением многочлена f ( x ) при x=c (или в точке с по аналогии со случаем, когда с можно представлять как точку действительной оси). Следовательно, многочлен f ( x ) определяет функцию f : K K.
Напомним, что мы дали формально-алгебраическое определение равенства двух многочленов, согласно которому два многочлена считаются равными, если их степени и соответствующие коэффициенты равны. Ясно, что равные многочлены определяют одну и ту же функцию, т.е. если многочлены равны с алгебраической точки зрения, то они равны и с функциональной точки зрения.
Предположим, что два многочлена равны с функциональной точки зрения. Обязательно ли они равны с алгебраической точки зрения? Ответ на этот вопрос будет отрицательным для любого конечного кольца K = { c 1, c 2,…, c n }. Над таким кольцом одну и ту же функцию определяют два различных многочлена f ( x )=( x - c 1 )( x - c 2 )…( x - c n )+ x и g ( x )= x. Значит, если K – конечное кольцо, то алгебраическая и функциональная точки зрения на многочлен не совпадают. Основная цель этого пункта доказать, что если K – бесконечная область целостности, то обе эти точки зрения на многочлен совпадают, т.е. различные с алгебраической точки зрения многочлены определяют различные функции.
f(x)=(x-c)q(x)+r (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 ( c i ) = g ( c i ) ( i= 1,2,…, n, n+ 1). Предположим, что f ( x ) g ( x ) и рассмотрим многочлен h ( x )= f ( x )- g ( x ). Он ненулевой, его степень не превосходит числа n и в тоже время он имеет n + 1 корней c 1, c 2,…, c n, c n+1, что противоречит теореме 2. Следовательно, f ( x )= g ( x ). ◙ Из леммы 1 вытекает Следствие 5. Если многочлены f ( x ) и g ( x ) принимают равные значения на некотором бесконечном подмно-жестве области целостности K, то f ( x )= g ( x ). ◙
Основными задачами этого раздела являются рассмотрение вопросов: Обоснование алгоритма нахождения НОД многочленов с помощью алгоритма Евклида. Нахождение линейного представления НОД многочленов. Свойства взаимно простых многочленов. НОК многочленов и его нахождение.
В этом разделе будем рассматривать многочлены над произвольным полем P. Определение 1. Наибольшим общим делителем ( НОД) многочленов f 1 ( x ), f 2 ( x ), …, f m ( x ) из кольца P [ x ] называется многочлен d ( x ), обладающий следующими свойствами: 1) каждый из многочленов f 1 ( x ), f 2 ( x ), …, f m ( x ) делится на d ( x ), т.е. d ( x ) является их общим делителем; 2) d ( x ) делится на любой общий делитель многочленов f 1 ( x ), f 2 ( x ), …, f m ( x ). Обозначение: НОД ( f 1 ( x ), f 2 ( x ), …, f m ( x )).
Понятно, что в случае существования НОД определяется с точностью до множителя нулевой степени (любые два НОДа должны делиться друг на друга); нормированный НОД определяется однозначно. НОД двух многочленов f ( x ) и h ( x ) может быть найден при помощи алгоритма Евклида. Прежде всего, ясно, что если, то НОД ( f ( x ), h ( x ) ) = h ( x ).
Пусть. Делим с остатком многочлен f(x) на многочлен h ( x ), затем многочлен h ( x ) – на остаток от первого деления, затем остаток от первого деления – на остаток от второго деления и т.д., пока не получится нулевой остаток (последнее неизбежно, так как степени остатков строго убывают).
Это дает следующую цепочку равенств: (E)
(Е) Из которых получаем доказательство следующего утверждения. Т е о р е м а 3. Для любых многочленов f(x) и h ( x ) из P [ x ] существует их НОД( f ( x ), h ( x )), причем если , то он совпадает с последним неравным нулю остатком в равенствах ( E ) Евклида, т.е. НОД( f ( x ), h ( x ))= r k ( x ). ◙
(Е) НОД( f ( x ), h ( x ))= r k ( x ). ◘ Покажем сначала, что многочлен r k ( x ) является общим делителем многочленов f(x) и h ( x ). Учитывая последнее равенство в (Е), из предпоследнего равенства получим, что, из третьего снизу равенства в (Е) имеем и т.д. Поднимаясь снизу вверх по равенствам (Е) через конечное число шагов получим, что и.. Таким образом, условие 1) определения 1 для многочлена r k ( x ) выполнено.
(Е) НОД( f ( x ), h ( x ))= r k ( x ). Пусть теперь d ( x ) – любой общий делитель многочленов f(x) и h ( x ). Из первого равенства системы (Е) легко получаем, что ; из второго – ; из третьего – и т.д. Спускаясь по равенствам (Е), через конечное число шагов получим, что. Таким образом, и условие 2) определения 1 для многочлена r k ( x ) выполнено. Итак, НОД( f ( x ), h ( x ))= r k ( x ). ◙
Пример 3. В кольце многочленов с действительными коэффициентами найдем НОД многочленов и. ◘ Делим f(x) на h ( x ) с остатком:
Поскольку НОД находится с точностью до константы, для удобства можно разделить полученный остаток на -3 и выполнять деление многочлена h ( x ) на r 1 (x) : (-3), что не скажется на результате. Однако, имея в виду дальнейшее линейное представление НОД, мы не будем делать этого и все вычисления будем производить точно.
Выполним деление h ( x ) на r 1 (x) :
Выполним деление r 1 (x) на r 2 (x) : Поскольку остаток r 2 ( x ) = 0 равен нулю, то НОД ( f(x),h(x) )= x +1. ◙
НОД нескольких многочленов f 1 ( x ), f 2 ( x ),..., f m ( x ) может быть найден индуктивным способом на основании следующей формулы: . Таким образом, для того чтобы найти наибольший общий делитель многочленов f 1 ( x ), f 2 ( x ),..., f m ( x ), следует в соответствии с этой формулой найти сначала d 1 ( x )=НОД( f 1 ( x ), f 2 ( x )), затем d 2 ( x )=НОД( d 1 ( x ), f 3 ( x )) и т.д.; и, наконец, найти многочлен d m -1 ( x )=НОД( d m-2 ( x ), f m ( 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)=r k (x) из предпоследнего равенства системы (Е), затем заменить в нем r k -1 (x) выражением его из предшествующего равенства и т.д. Продолжая этот процесс, поднимаемся по равенствам Евклида снизу вверх до тех пор, пока не исключим все остатки и получим выражение вида (5). ◙
f(x)u(x) + h(x)v(x)=d(x). (5) ◘ Действительно из (Е) Имеем НОД ( f(x),h(x) )= d(x)= r k (x) = r k -2 (x) - r k -1 (x) q k -1 (x) = = r k -3 (x)(-1) + r k -2 (x)(1+q k -1 (x) q k - 2 (x) ) = … = = f(x)u(x)+h(x)v(x).
f(x)u(x) + h(x)v(x)=d(x). (5) Пример 4. Проиллюстрируем теорему 4, опираясь на вычисления примера 3. Запишем равенства (Е) для выполненных там делений, при этом будем использовать пока буквенные обозначения: Выражая r 2 (x) из последнего равенства (напомним, что в примере 3 НОД ( f(x),h(x) ) = r 2 (x) ) и подставляя в него выражение из первого равенства, получим
f(x)u(x) + h(x)v(x)=d(x). (5) или f(x)u(x) + h(x)v(x)=d(x), где, и d(x)=x+1. Таким образом, , где и, искомое линейное представление НОД ( f(x),h(x) ) = x +1. ◙
Определение 3. Многочлены f(x) и h(x) из кольца 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)
Следствие 5. Многочлены и взаимно просты тогда и только тогда, когда в кольце 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) – взаимно простые многочлены. ◙
Следствие 6. Если f(x) и h(x) – многочлены из кольца P [ x ], d(x) = НОД ( f(x),h(x) ), то многочлены и взаимно просты. ◘ В самом деле, по теореме 4 справедливо равенство (5). Поделив его на d(x), получим равенство , из которого вытекает взаимная простота многочленов f 1 (x) и h 1 (x). ◙
Отметим еще три свойства взаимно простых многочленов. 1°. Если многочлен 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 ). ◙
2°. Если произведение f ( x ) g ( 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 ). ◙
3°. Если многочлен f ( 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 ). ◙
Определение 4. Наименьшим общим кратным многочленов f 1 ( x ), f 2 ( x ), …, f m ( x ) из кольца P [ x ] называется многочлен k(x), обладающий следующими свойствами: 1) k(x) делится на каждый из многочленов f 1 ( x ), f 2 ( x ), …, f m ( x ), т.е. является их общим кратным; 2) любое общее кратное многочленов делится на k(x). Обозначение: НОК( f 1 ( x ), f 2 ( x ), …, f m ( x ) ).
Понятно, что, в случае существования, НОК определяется с точностью до множителя нулевой степени (любые два НОК должны делиться друг на друга); нормированное НОК определяется однозначно. Т е о р е м а 5 (о НОК двух многочленов). Любое общее кратное многочленов f ( x ) и h ( x ) имеет вид , где t(x) P [ x ]. (8) При этом . ( 9 )
◘ Пусть d ( x )=НОД( f ( x ), h ( x )), и. Используя эти обозначения, перепишем равенство (8) в виде . Отсюда видно, что любой многочлен вида (8) является общим кратным многочленов f ( x ) и h ( x ).
Пусть теперь k ( x ) – общее кратное многочленов f ( x ) и h ( x ). Покажем, что оно имеет вид (8). По условию k ( x ) делится на f ( x ) и поэтому k ( x )= f ( x ) q ( x ). С другой стороны, поскольку, то, и, следовательно,. Так как по следствию 6 многочлены f 1 ( x ) и h 1 ( x ) взаимно просты, отсюда и из свойства 2° взаимно простых многочленов получаем, что, т.е. q ( x )= h 1 ( x ) t ( x ). Но тогда имеем . Таким образом, любое общее кратное k ( x ) многочленов f ( x ) и h ( x ) имеет вид (8) и первое утверждение теоремы 5 доказано.
Докажем равенство (9). В самом деле, из равенства (8) следует, что многочлен есть общее кратное многочленов f ( x ) и h ( x ) и, что любое общее кратное f ( x ) и h ( x ) на него делится. Таким образом, . ◙
Т е о р е м а 5 (о НОК двух многочленов). Любое общее кратное многочленов многочленов f ( x ) и h ( x ) имеет вид , где t(x) P [ x ]. (8) При этом . ( 9 ) Из теоремы 5 вытекает Следствие 7. Наименьшее общее кратное двух взаимно простых многочленов равно их произведению. ◙
Пример 5. В кольце многочленов R [ x ] с действительными коэффициентами найдем НОК многочленов и. Согласно вычислениям примера 1 НОД ( f(x),h(x) = x+ 1. По формуле ( 8 ) имеем . Поделив сначала многочлен на двучлен x+1, получим многочлен. Теперь = = =.
НОК нескольких многочленов f 1 ( x ), f 2 ( x ), …, f m ( x ) может быть найден индуктивным способом на основании следующей формулы: . Таким образом, для нахождения НОК ( f 1 ( x ), f 2 ( x ), …, f m ( x ) ) следует в соответствии с этой формулой найти сначала k 1 ( x )=НО K ( f 1 ( x ), f 2 ( x )), затем k 2 ( x )=НОК( k 1 ( x ), f 3 ( x )) и т.д.; и, наконец, многочлен k m -1 ( x )=НОК( k m-2 ( x ), f m ( x )), который и будет искомым НОК.
