Многочлены от одной переменной. Лекция 2

1. АЛГЕБРА (4-й семестр)

2023-24
учебный год

2. МНОГОЧЛЕНЫ ОТ ОДНОЙ ПЕРЕМЕННОЙ

ЛЕКЦИЯ 2

3. § 2. Делимость многочленов

Основными задачами этого параграфа
являются рассмотрение вопросов:
1.
Деление многочленов с остатком.
2.
Корни многочлена и теорема тождественности
для мночленов.
3.
НОД многочленов и его нахождение с помощью
алгоритма Евклида.
4.
Линейное представление НОД многочленов и
свойства взаимно простых многочленов.
5.
НОК многочленов.

4. 1. Деление многочленов с остатком.

В дальнейшем будем предполагать, что K – область
целостности. Согласно теореме 2 из § 1 K[x] также есть
область целостности и поэтому для K[x] применимы
определения и результаты о делимости в коммутативных
кольцах.
В частности, если для многочленов f(x) и h(x) из K[x]
существует такой многочлен , что f(x) = h(x)q(x), то будем
говорить, что f(x) делится на h(x) и писать
f ( x ) h( x )
.
Как и в кольце целых чисел, в кольце многочленов деление
в этом смысле не всегда возможно. Однако в справедлива

5. 1. Деление многочленов с остатком.

Т е о р е м а 1 (о делении с остатком).
Пусть f(x) и h(x) – произвольные
многочлены кольца K[x], причем старший
коэффициент многочлена h(x) обратим
в K. Тогда существуют однозначно
определенные многочлены q(x), r(x) K[x]
такие, что
f(x) = h(x)q(x)+r(x) и degr(x) < degh(x). (1)

6. 1. Деление многочленов с остатком.

f(x) = h(x)q(x)+r(x) и degr(x) < degh(x).
◘ 1) Существование представления (1). Пусть
f ( x) an x n ... a1 x a0 ,
h( x) bm x m ... b1 x b0 ,
где n= degf(x), m= degh(x), bm – обратимый элемент в K
(в частности, bm 0 ).
Если n=0 и m>n, то положим q(x)=0, r(x) = f(x).
Если n=m=0, то положим r(x)=0 и q( x) an bm 1 .
Пусть n > 0. Мы можем предполагать, что degh(x)
degf(x)(иначе возьмем q(x)=0 и r(x) = f(x) ).
n m
a
b
Умножив многочлен h(x) на
, получим
n m x
1 n m
многочлен anbm x h( x)
, старший
коэффициент которого равен старшему
коэффициенту многочлена f(x).
Поэтому многочлен f1 ( x) f ( x) anbm 1x n mh( x) будет
иметь степень n1 < n.
(1)

7. 1. Деление многочленов с остатком.

f(x) = h(x)q(x)+r(x) и degr(x) < degh(x).
◘ 1) Существование представления (1). Пусть
f ( x) an x n ... a1 x a0 ,
h( x) bm x m ... b1 x b0 ,
где n= degf(x), m= degh(x), bm – обратимый элемент в K
(в частности, bm 0 ).
(1)
Если по-прежнему n1 m, то из f1(x) вычтем
многочлен an1 bm 1 x n1 m h( x)
, где an1 – старший
коэффициент многочлена f1(x).
Степень полученного при этом многочлена f2(x)
будет меньше n1.
Ясно, что продолжая этот процесс, после конечного
числа шагов обязательно получим многочлен
r(x) , степень которого будет меньше m.

8. 1. Деление многочленов с остатком.

f(x) = h(x)q(x)+r(x) и degr(x) < degh(x).
(1)
◘ 1) Существование представления (1).
Выпишем получающиеся при этом равенства:
f ( x) an bm 1 x n m h( x) f1 ( x),
n m
f1 ( x) an1 bm 1 x 1
h( x) f 2 ( x),
n m
f 2 ( x) an 2 bm 1 x 2
h( x) f 3 ( x),
(2)
....................................
n m
f k ( x) an k bm 1 x k
h( x ) r ( x )
(здесь ni=degfi(x), ani – старший коэффициент
многочлена fi(x) ).
Складывая равенства (2), получим
f ( x) h( x)(an bm x n m an bm x n m an bm x n m h ... ank bm x nk m ) r ( x)
или, обозначив через q(x) стоящий в скобках многочлен,
получим представление вида (1).

9. 1. Деление многочленов с остатком.

f(x) = h(x)q(x)+r(x) и degr(x) < degh(x).
(1)
◘ 2) Единственность представления (1).
Предположим, что
f(x) = h(x)q1(x)+r1(x)= h(x)q2(x)+r2(x),
где degr1(x) < degh(x) и degr2(x) < degh(x).
Тогда
h(x)(q1(x)-q2(x))=r2(x)-r1(x)
(3).
В силу равенства (6) из §1
deg(h(x)(q1(x)-q2(x)))=degh(x)+deg(q1(x)-q2(x)). (4)
Поскольку deg(r2(x)-r1(x))<degh(x) и из (3)
следует, что deg(h(x)(q1(x)-q2(x)))= deg(r2(x)-r1(x))
, то равенство (4) может выполняться только при
q1(x)-q2(x)=0, т.е. q1(x)=q2(x) и, следовательно,
r2(x)=r1(x), что и требовалось показать. ◙

10. 1. Деление многочленов с остатком.

f(x) = h(x)q(x)+r(x) и degr(x) < degh(x).
(1)
Многочлен q(x) в (1) называется неполным
частным, а r(x) – остатком от деления
многочлена f(x) на многочлен h(x) в кольце K[x] .
Замечание 1. Так как единица кольца K
обратима в K, деление на нормированный
многочлен h(x) в кольце K[x] всегда возможно.
Замечание 2. Если K – поле, то теорема о
делении с остатком справедлива для любых
многочленов f(x) и h(x) кольца K[x].
Замечание 3. При доказательстве
существования представления (1) указан
алгоритм деления с остатком многочлена на
многочлен в кольце , который обычно
реализуется как деление «уголком».

11. 1. Деление многочленов с остатком.

Пример 1. Многочлен f ( x) x 4 6x3 4x 2 6x 1 нельзя
разделить с остатком на многочлен h( x) 2x 2 4x 8
в кольце Z[x], так как 2 – необратимый элемент в
кольце Z. Однако в кольце Q [x] это сделать
возможно:
x 4 6x3 4x 2 6x 1 | 2x 2 4x 8
1 2
x 4 x 4 q( x)
2
8 x 3 8 x 2 6 x 1 f1 ( x)
x 4 2x3 4x 2
8 x 3 16 x 2 32 x
8 x 2 26 x 1 f 2 ( x)
8 x 2 16 x 32
10 x 33 r ( x)
.

12. Схема Горнера

Ближайшей нашей задачей будет обоснование алгоритма
деления многочлена на двучлен x-c при c K, называемого
схемой Горнера (1786–1837, английский математик).
Прежде всего, по теореме 1 деление с остатком многочлена
на x-c в кольце K[x] всегда возможно:
f(x)=(x-c)q(x)+r
(5)
и при этом r K, так как остаток имеет степень меньше 1 и
поэтому является элементом из K.
В равенстве (5) введем обозначения
n 1
f ( x) an x n ... a1 x a0 , q( x) bn 1 x ... b1 x b0
и перепишем его в развернутом виде:
an x n an 1 x n 1 ... a1 x a0 ( x c)(bn 1 x n 1 bn 2 x n 2 ... b1 x b0 ) r .

13. Схема Горнера

f(x)=(x-c)q(x)+r
,
q( x) bn 1 x n 1 ... b1 x b0
f ( x) a x n ... a x a
n
1
(5)
0
a n x n an 1 x n 1 ... a1 x a0 ( x c)(bn 1 x n 1 bn 2 x n 2 ... b1 x b0 ) r
.
Сравнение коэффициентов многочлена в левой части последнего
равенства с коэффициентами многочлена, полученного после
раскрытия скобок и приведения подобных, в правой части этого
равенства приводит к цепочке равенств:
откуда последовательно определяют коэффициенты h(x) и остаток
r:
bn 1 a n ,
an bn 1,
bn 2 a n 1 cbn 1 ,
an 1 bn 2 cbn 1,
bn 3 a n 2 cbn 2 ,
(6)
an 2 bn 3 cbn 2 ,
....................
....................
b0 a1 cb1 ,
a1 b0 cb1,
r a 0 cb0 .
a0 r cb0 ,

14. Схема Горнера

bn 1 a n ,
bn 2 a n 1 cbn 1 ,
bn 3 a n 2 cbn 2 ,
(6)
....................
,
b0 a1 cb1 ,
r a 0 cb0 .
Вычисление коэффициентов неполного частного q(x) и остатка r
по рекуррентным формулам (6) удобно расположить в виде
таблицы, которую и называют схемой Горнера.
В верхней строке таблицы выписывают коэффициенты
многочлена f(x) , а в нижней строке – вычисленные по формулам
(6) коэффициенты неполного частного q(x) и остатка r от деления
на двучлен x-c :
an
c
bn-1
an-1
bn-2
an-1
bn-3
…
…
a1
b0
a0
r

15. Схема Горнера

bn 1 a n ,
bn 2 a n 1 cbn 1 ,
bn 3 a n 2 cbn 2 ,
(6)
....................
b0 a, 1 cb1 ,
r a 0 cb0 .
c
an
an-1
an-1
…
a1
a0
bn-1
bn-2
bn-3
…
b0
r
Элементы нижней строки вычисляются
последовательно по формулам (6): bn-1=an , a
каждый последующий элемент равен сумме
элемента, находящегося над ним, и предыдущего
элемента нижней строки, умноженного на с.

16. Схема Горнера

c
an an-1 an-1 …
bn-1 bn-2 bn-3 …
a1
b0
a0
r
Элементы нижней строки вычисляются последовательно по
формулам (3): bn-1=an , a каждый последующий элемент
равен сумме элемента, находящегося над ним, и
предыдущего элемента нижней строки, умноженного на с.
Пример 2. С помощью схемы Горнера разделить с остатком многочлен
f ( x) 2 x 4 5x3 4 x 2 2 x 3 на двучлен x-2:
2
2
2
-5
-1
4
2
-2
2
3
7
Таким образом, q( x) 2 x x 2 x 2 и r = 7.
3
2

17. 1. Деление многочленов с остатком.

f(x) = h(x)q(x)+r(x) и degr(x) < degh(x).
(1)
Непосредственно из теоремы 1
вытекает
Следствие 1. Многочлен f(x) делится
на многочлен h(x) в кольце K[x] тогда
и только тогда, когда остаток от
деления f(x) на h(x) равен 0. ◙

18. 2. Корни многочлена. Алгебраическая и функциональная точки зрения на многочлен.

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

19. 2. Корни многочлена. Алгебраическая и функциональная точки зрения на многочлен.

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

20. 2. Корни многочлена. Алгебраическая и функциональная точки зрения на многочлен.

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

21. 2. Корни многочлена. Алгебраическая и функциональная точки зрения на многочлен.

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

22. 1. Деление многочленов с остатком.

Из следствий 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 называются простыми
корнями.

23. 2. Корни многочлена. Алгебраическая и функциональная точки зрения на многочлен.

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

24. 2. Корни многочлена. Алгебраическая и функциональная точки зрения на многочлен.

Пусть с – корень f(x).
По характеристическому свойству корня 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
корней. ◙

25. 2. Корни многочлена. Алгебраическая и функциональная точки зрения на многочлен.

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

26. 2. Корни многочлена. Алгебраическая и функциональная точки зрения на многочлен.

Лемма 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). ◙