НО_лекция--10

ЛЕКЦИЯ 10

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

КАНОНИЧЕСКОЕ РАЗЛОЖЕНИЕ МНОГОЧЛЕНОВ

В5-й лекции была доказана разложимость любого целого на простые множители

вкольце целых чисел. Аналогичное разложение возможно и в кольце многочленов P [t]. Здесь в роли простых чисел выступают неприводимые многочлены.

Определение 1. Отличный от константы многочлен f (f 2 P [t]) называется неприводимым над полем P (или неприводимым в поле P ), если он не делится ни на какой многочлен g (g 2 P [t]), у которого 0 < deg g < deg f. В противном случае он называется приводимым. /

Неприводимость многочлена связана с наличием у него корней и таким образом зависит от поля. Например, многочлен f(t) = t2 + 1 неприводим над полем вещественных чисел, в то же время он приводим над полем комплексных чисел, а именно: f(t) = (t + i)(t i), i 2 C, т.е. для многочлена f 2 C[t], f = t2 + 1; deg f = 2 существует многочлен g 2 C[t]; g = t + i; deg g = 1 такой, что f jj g; 0 < deg g < deg f: Далее показано, что неприводимыми над полем C являются только многочлены первой степени, а над полем R многочлены первой степени и многочлены второй степени с отрицательным дискриминантом.

Из опр. 1 следует, что все делители неприводимого многочлена либо константы, либо ассоциированные с ним многочлены.

Свойства неприводимых многочленов

1. Любой многочлен первой степени неприводим над любым полем.

Доказательство следует из опр.1, так как не существует целого положительного числа (степени многочлена), большего нуля и меньшего единицы. /

2. Многочлен, ассоциированный с неприводимым многочленом, неприводим.

Доказательство от протвного. Пусть многочлен f 2 P [t] неприводим, а многочлен g 2 P [t], ассоциированный с f, является приводимым. В общем случае ассоциированный с f многочлен g имеет вид (лекция 8):

g = f; 6= 0; 2 P; deg g = deg f:

Приводимость многочлена g означает, что существует многочлен h 2 P [t], такой, что

g = h'; h 2 P [t]; 0 < deg h < deg g:

Многочлен h является делителем многочлена g и одновременно делителем f, так как

f = 1g = 1h':

1

Кроме того, степень h удовлетворяет неравенствам

0 < deg h < deg f = deg g;

из чего следует приводимость многочлена f, что противоречит условию. /

3. Пусть f 2 P [t] и многочлен g неприводим в поле P . Тогда либо f делится на g, либо f взаимно прост с g.

Доказательство. Пусть d (d 2 P [t]) унитарный наибольший общий делитель многочленов f и g. Многочлен g должен делиться на d, неприводимый многочлен g делится только на 1 и на ассоциированный с ним многочлен, следовательно, d либо ассоциирован с g, либо равен 1. Если d ассоциирован с g, то djj g, тогда f должен

делиться на g, так как

f jj d; djj g ) f jj g:

Во втором случае, если d равен 1, многочлены f и g взаимно просты. /

4. Множество унитарных многочленов неприводимых над полем бесконечно.

Доказательство для произвольного поля здесь не рассматривается, отметим только, что оно аналогично доказательству теоремы Евклида о бесконечности множества простых чисел. Для бесконечных полей доказательство очевидно, так как по св-ву 1 многочлен (t c), c 2 P неприводим над любым полем, а число таких многочленов

вбесконечном поле бесконечно. /

5.Пусть f; h; ' 2 P [t] и многочлен ' неприводим над полем P , пусть, кроме того, f 6jj ' и h 6jj '. Тогда произведение fh не делится на '.

Доказательство. Из св-ва 3 неприводимых многочленов и заданных условий f 6jj ' и h 6jj ' следует, что многочлены f и h взаимно просты с неприводимым многочленом ', т.е.

(f; ') = 1; (h; ') = 1:

По утв.7 лекции 9 отсюда следует, что произведение fh тоже взаимно просто с ', т.е. (fh; ') = 1, следовательно, fh 6jj '. /

6. Если произведение многочленов fh делится на неприводимый многочлен ', то по крайней мере один из них делится на '.

Доказательство. Используя эквивалентность логических высказываний (замечание 2 лекции 1), можно переформулировать св-во 5, в результате этого приходим к формулировке св-ва 6. /

Свойство 6 обобщается на k многочленов f1; f2; : : : ; fk.

7. Если произведение f1 : : : fk многочленов fi 2 P [t] делится на неприводимый в поле P многочлен ' (' 2 P [t]), то по крайней мере один из многочленов f1; : : : ; fk делится на '.

Доказательство проводится индукцией по k с использованием св-ва 6. /

В произвольном кольце K с единицей неприводимым называется элемент, не имеющий делителей, отличных от единицы кольца и от ассоциированных с ним элементов.

2

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

В кольце целых чисел Z неприводимыми элементами являются простые числа и любое целое раскладывается в произведение простых чисел (лекция 5), т.е. кольцо целых чисел Z факториально.

Докажем, что кольцо многочленов P [t] является факториальным.

Утверждение 1. Любой отличный от константы многочлен f (f 2 P [t]) может быть представлен в виде произведения неприводимых в поле P многочленов:

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

Доказательство. Первую часть утверждения докажем от противного. Пусть в P [t] существуют отличные от констант многочлены, не представимые в виде (1), т.е. не являющиеся произведениями неприводимых. Выберем среди них многочлен f наименьшей степени. Многочлен f должен быть приводимым,так как иначе он представлялся бы в виде (1). Разложим f в произведение многочленов f1 и f2 меньшей степени:

f = f1f2; deg f1 < deg f; deg f2 < deg f:

f выбран как многочлен наименьшей степени, не являющийся произведением неприводимых, следовательно, многочлены f1 и f2 (степени меньшей, чем deg f) являются произведениями неприводимых, но тогда из равенства f = f1f2 следует, что и многочлен f разложим в произведение неприводимых. Это противоречие доказывает первую часть утверждения.

Вторую часть докажем индукцией по степени многочлена.

База. При n = 1 для двух разложений многочлена f (deg f = 1) выполняется равенство

a0(t c) = b0(t d); a0 6= 0; b0 6= 0;

из которого следует:

a0 = b0; a0c = b0d ) c = d:

Индукционное предположение: пусть утверждение верно для всех многочленов, степень которых меньше, чем deg f.

Индукционный переход. Пусть многочлен f допускает два разложения (1):

hi (i = 1; : : : ; k); qj (j = 1; : : : ; l) многочлены неприводимые в поле P . Положим для определенности k l: Из (2) следует, что многочлен q1q2 : : : ql должен делиться на h1. Среди многочленов q1; q2; : : : ; ql должен быть хотя бы один многочлен qi, делящийся на h1 (св-во 7), и он должен быть ассоциированный с h1, так как многочлен qi неприводим, а неприводимый многочлен может делиться либо на константу, либо на ассоциированный с ним многочлен. Переставляя сомножители в q1q2 : : : ql, добьемся,

3

чтобы это был q1. Следовательно, многочлен h1 ассоциирован с q1, это позволяет записать:

В кольце многочленов P [t] допустимо сокращение (следствие 1 лекция 8). В результате сокращения на h1 приходим к многочлену f~:

f~ = h2 : : : hk = q2 : : : ql; f = h1f~; deg f~ < deg f:

По индукционному предположению для многочлена f~ должно выполняться равенство: k 1 = l 1, следовательно, k = l для многочлена f. Кроме того, по индукционному предположению в любых двух разложениях f~ можно переставить сомножители так, чтобы сомножители с одинаковыми номерами были ассоциированы, следовательно, в многочлене f можно переставить сомножители так, чтобы многочлен h2 был ассоциирован с q2, h3 с q3; : : : ; многочлен hk был ассоциирован с qk. Таким образом, и вторая часть утверждения доказана. /

Вывод 1. Каноническое разложение многочлена в поле P .

Из утв. 1 следует, что разложение многочлена в произвольном поле P на неприводимые неоднозначно по двум причинам:

1)множители определены с точностью до ассоциированности,

2)порядок следования множителей произволен.

Первую причину легко устранить, переходя к унитарным многочленам, а именно, выбирая при доказательстве второй части утв. 1 не многочлен q1, ассоциированный с h1, а выбирая из всех ассоциированных c h1 многочленов унитарный многочлен p1. Тогда из утв. 1 следует разложение любого отличного от константы многочлена f в виде:

a0 старший коэффициент многочлена f, многочлены pi унитарные и неприводимые в поле P . Среди многочленов pi могут быть одинаковые. Собирая вместе одина-

Каноническое разложение (5) единственно с точностью до порядка следования сомножителей pki i . Показатели ki называются кратностями соответствующих неприводимых многочленов в разложении (5). Если унитарный неприводимый многочлен p не входит в разложение (5), ему приписывается кратность нуль. /

Как отмечалось, неприводимость многочлена из кольца P [t] зависит от поля P .

Определение 2. Поле P называется алгебраически замкнутым, если любой многочлен f 2 P [t] степени больше нулевой имеет хотя бы один корень в P . /

Можно доказать, что поле комплексных чисел C является алгебраически замкнутым. Другие бесконечные числовые поля, такие как поле вещественных чисел, поле рациональных чисел, не являются алгебраически замкнутыми. Последнее непосредственно следует из простых примеров. Легко видеть, что, например, многочлен t2 3 не имеет корней в поле рациональных чисел, а многочлен t2 + 3 не имеет корней в поле вещественных чисел.

4

Утверждение 2. В алгебраически замкнутом поле P любой многочлен f 2 P [t] степени n (n 1) имеет n корней в поле P , среди которых могут быть равные, и допускает разложение на линейные множители следующего вида:

Разложение (6) единственно с точностью до порядка следования множителей.

Доказательство существования разложения (6) проведем индукцией по степени многочлена.

База: при n = 1 многочлен f(t) = a0t + a1 = a0(t c), a0 6= 0 имеет один корень c = a1=a0; c 2 P и представим в виде (6).

Индукционное предположение: пусть утверждение выполнено для любого многочлена h степени deg h = n 1, n > 1, т.е. пусть многочлен h имеет (n 1) корней в поле P и допускает разложение

Индукционный переход. По определению алгебраически замкнутого поля P , многочлен f 2 P [t] степени n в P имеет по крайней мере один корень c (c 2 P ), следовательно, его можно представить в виде f(t) = (t c )h(t), где многочлен h имеет степень n 1. В силу индукционного предположения f можно записать, положив c = cn, следующим образом:

т.е. многочлен f имеет n корней, среди которых могут быть равные, и допускает разложение на линейные множители (6).

Докажем, что многочлен f не может иметь корней, отличных от c1; : : : ; cn. Предположим противное, пусть c (c 2 P ) корень многочлен f, отличный от c1; : : : ; cn. Тогда по теореме Безу f делится на t c , следовательно:

f = (t c )h; deg h = n 1:

Как показано выше, многочлены h и f можно представить в виде (7) и (8) соответственно. Учтем эти представления в равенстве f = (t c )h, в результате получим:

В кольцо многочленов P [t] допустимо сокращение на ненулевые множители, в результате такого сокращения в (9) приходим к равенству t cn = t c , из которого следует, что c = cn. Это противоречит предположению о наличии у многочлена f корня, отличного от c1; : : : ; cn.

Единственность (с точностью до порядка следования множителей) разложения

(6) следует из доказанного выше утв. 1, верного для кольца многочленов над любым полем. /

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

5

Доказательство. Из утв. 2 следует, что любой многочлен степени больше 1 имеет в алгебраически замкнутом поле более одного корня и раскладывается в произведение многочленов меньшей степени, т.е. не является неприводимым, а из св-ва 1 неприводимых многочленов следует, что многочлены первой степени неприводимы над любым полем. /

Каноническое разложение многочленов над алгебраически замкнутым полем

В разложении (6) могут быть равные множители, объединяя их, приходим к каноническому разложению многочлена f 2 P [t] степени n (n 1) над алгебраически замкнутым полем P , это разложение, как доказано в утв. 2, единственно с точностью до порядка следования множителей:

a0; c1; : : : ; cs 2 P , ci 6= cj при i 6= j , i; j = 1; : : : ; s;

k1; : : : ; ks 2 N, k1 + : : : + ks = deg f.

Здесь c1; : : : ; cs попарно различные корни многочлена f в поле P . Из разложения (10) и его единственности следует, что других корней многочлен f в поле P не имеет. Кроме того, из канонического разложения (10) следует, что для каждого из корней ci (i = 1; : : : ; s) многочлен f делится на (t ci)ki и не делится на (t ci)ki+1, это, в соответствии с определением k-кратного корня многочлена (опр. 4 лекции 9), означает, что показатели k1; : : : ; ks в (10) равны кратностями соответствующих корней многочлена f.

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

Основная теорема алгебры. Поле комплексных чисел алгебраически замкнуто.

Следствие 2. Для любого многочлена f 2 C[t] над полем комплексных чисел существует и единственно каноническое разложение на линейные множители (10).

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

Многочлены с вещественными коэффициентами

Рассмотрим многочлены с вещественными коэффициентами. Как отмечалось выше, поле вещественных чисел не является алгебраически замкнутым. Поэтому многочлен степени n над полем вещественных чисел R может не иметь n корней в поле

R.

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

Утверждение 3. Если комплексное число z является корнем многочлена с вещественными коэффициентами, то комплексно сопряженное число z также является корнем этого многочлена.

6

Доказательство заключается просто в проверке этого факта. Пусть задан многочлен f(t) = a0tn + a1tn 1 + : : : + an, a0; : : : ; an 2 R и пусть z комплексный корень f, т.е.

Свойства операции комплексного сопряжения (лекция 6) позволяют записать следующие равенства:

т.е. комплексно сопряженное число z также является корнем многочлена f с вещественными коэффициентами. /

Утверждение 4. Многочлен f с вещественными коэффициентами, имеющий комплексный корень z с ненулевой мнимой частью, делится на многочлен '(t) = (t z)(t z); многочлен ' имеет вещественные коэффициенты и является неприводимым над полем R.

Доказательство. Пусть f(z) = 0, z = a + bi, b 6= 0; a; b 2 R. По утв. 3 сопряженное число z = a bi также является корнем f, так как по условию многочлен f имеет вещественные коэффициенты. По теореме Безу многочлен f, имющий корни z и z, делится на соответствующие линейные многочлены:

Многочлены (t z) и (t z) взаимно просты: (t z); (t z) = 1. По свойству взаимно простых многочленов (утв. 6 лек. 9) из условий

следует, что f делится на их произведение: f jj (t z)(t z). Рассмотрим многочлен '(t) = (t z)(t z) и покажем, что он имеет вещественные коэффициенты и является неприводимым над полем R.

Дискриминант многочлена ' равен D = b2, т.е. является отрицательным для любого b 2 R, b 6= 0, следовательно, многочлен ' не имеет вещественных корней и не раскладывается в поле R в произведение многочленов меньшей степени, т.е. многочлен ' неприводим над полем R. /

Утверждение 5. Над полем вещественных чисел неприводимыми являются только многочлены первой степени и многочлены второй степени, не имеющие вещественных корней.

Доказательство. Для многочленов с вещественными коэффициентами, степень которых не превышает 2, выполнение утверждения очевидно, так как многочлены первой степени неприводимы над любым полем (св-во 1 неприводимых многочленов), а многочлены второй степени с отрицательным дискриминантом, не имеющие вещественных корней, в произведение многочленов первой степени не раскладываются и являются неприводимыми над полем R.

7

Докажем, что любой многочлен f с вещественными коэффициентами, степень которого больше 2, приводим. Для f есть только две возможности:

1)f имеет вещественный корень c;

2)f не имеет вещественных корней.

В первом случае f jj (t c) и, следовательно, f приводим. Во втором случае многочлен f степени deg f > 2 в поле комплексных чисел C имеет более, чем 2 корня (утв. 2), так как поле C алгебраически замкнуто. Поскольку многочлен f имеет вещественные коэффициенты по утв. 3 его комплексные корни должны входить “парами”, т.е., если z корень f, то z также корень f. По утв.4 f jj ', где многочлен '(t) = (t z)(t z) имеет вещественные коэффициенты и является неприводимым над полем R, т.е. и во втором случае многочлен f является приводимым в поле R. Следовательно, и для многочленов степени больше 2 (с вещественными коэффициентами), утверждение доказано. /

Утверждение 6. Если z комплексный корень k-й кратности многочлена f с вещественными коэффициентами, то z также является корнем k-й кратности многочлена f.

Доказательство построим от противного. Пусть корни z и z многочлена f имеют разные кратности k 6= l:

z корень k-й кратности f, т.е. f(t) = (t z)kh1(t), h1 6jj (t z), z корень l-й кратности f, т.е. f(t) = (t z)lh2(t), h2 6jj (t z).

Пусть, например, k > l. Из взаимной простоты многочленов t z и t z следует взаимная простота многочленов (t z)k и (t z)l (следствие 2 лекции 9). Из условий

следует, что многочлен f делится на произведение многочленов (t z)k и (t z)l (утв. 6 лекц. 9), т.е.

причем многочлен g не делится ни на (t z), ни на (t z) (так как в противном случае корни z и z многочлена f имели бы большую кратность, чем k и l). Перегруппируем множители в разложении f (13) с тем, чтобы выделить многочлен '(t) = (t z)(t z):

Многочлен '(t) = (t z)(t z) имеет вещественные коэффициенты (утв. 4). Из равенства f(t) = '(t)lh(t) следует, что многочлен h также должен иметь вещественные коэффициенты и, следовательно, имея корень z, должен иметь и корень z (утв. 3). Покажем, что z не может быть корнем h. Докажем, что многочлен h взаимно прост с (t z). Действительно, многочлен (t z)k l взаимно прост с (t z) (следствие 1 лекция 9), многочлен g(t) взаимно прост с (t z) (это следует из св-ва 3 неприводимых многочленов, так как g не делится на (t z) ). Таким образом, многочлен h также взаимно прост с (t z) (утв. 7 лекции 9). Из взаимной простоты h и (t z) следует, что h 6jj (t z) и, следовательно, z не является корнем h.

Противоречия не возникает только при k = l, так как в этом случае h = g, а для многочлена g, по его определению, ни z, ни z не являются корнями. /

8

Каноническое разложение многочленов над полем вещественных чисел

Утверждение 7. Каноническое разложение многочлена f из кольца многочленов R[t] над полем R имеет следующий вид:

k1; : : : ; ks; m1; : : : ; mr 2 N [ f0g; k1 + : : : + ks + 2(m1 + : : : + mr) = deg f:

Разложение (15) единственно с точностью до порядка следования множителей.

Доказательство. Разложение (15) следует из утв. 5 о том, что над полем вещественных чисел неприводимыми являются только многочлены первой степени и многочлены второй степени с отрицательным дискриминантом. Единственность (с точностью до порядка следования множителей) разложения (15) следует из утв. 1.

/

Свойства неприводимых многочленов (продолжение)

Утверждение 8. Неприводимый в поле P многочлен ' 2 P [t], входящий в разложение многочлена f 2 P [t] с показателем k (k 1), входит в разложение производной f0 с показателем (k 1).

Доказательство аналогично доказательству утв. 9 (лекц. 9) о том, что k-кратный корень многочлена f является (k 1)-кратным корнем многочлена f0. Пусть f = 'kh, h; ' 2 P [t], h 6jj ', ' многочлен, неприводимый в P . Найдем f0.

Докажем, что многочлен g (g = k'0h + 'h0) не делится на неприводимый многочлен '. Предположим противное: g jj '. Тогда многочлен k'0h = g 'h0 должен делиться на ' (св-во 8 отношения делимости). Покажем, что условие k'0hjj ' приводит к противоречию. Многочлен h взаимно прост с ', так как h 6jj ' и ' неприводимый многочлен (св-во 3 неприводимых многочленов). Если произведение многочленов k'0 и h делится на ' и многочлены h и ' взаимно просты, то многочлен k'0 должен делиться на ' (утв. 5 лекции 9), т.е. из условия k'0hjj ' следует условие: k'0 jj '. Многочлен k'0 является ненулевым, так как k 6= 0 и '0 6= O. Неравенство '0 6= O следует из неприводимости многочлена ':

deg ' 1 ) deg '0 0 ) '0 6= O:

Но ненулевой многочлен k'0 не может делиться на ', так как deg k'0 < deg ' (deg k'0 = deg ' 1). Таким образом, многочлен g не делится на ' и, следовательно, f0 = 'k 1g не делится на 'k; поскольку f0, кроме того, делится на 'k 1, утверждение доказано. /

9

Отделение кратных корней многочлена

Рассмотрим многочлены над полем вещественных или комплексных чисел. Приведенные выше канонические разложения многочленов (10) и (15) можно записать в общем виде следующим образом:

Утверждение 9. Многочлен h = a0k1p01p2 : : : ps + : : : + a0ksp1 : : : ps 1p0s взаимно прост с многочленом p~ = a0p1p2 : : : ps.

Доказательство основано на трех фактах:

1)любой делитель d (deg d > 0) многочлена p~ делится на один из неприводимых многочленов p1; p2; : : : ; ps;

2)если существует отличный от константы общий делитель многочленов h и p~,

то hjj pi, где pi один из неприводимых многочленов p1; p2; : : : ; ps;

3) многочлен h не может делиться ни на один из неприводимых многочленов p1; p2; : : : ; ps.

Если факт 2) доказан, то, предположив существование d отличного от 1 унитарного наибольшего общего делителя многочленов h и p~ приходим к условию hjj pi, где pi один из неприводимых многочленов p1; p2; : : : ; ps:

j j 2) j

d = (h; p~); deg d > 0 ) hj d и p~j d ) hj pi;

где pi один из неприводимых многочленов p1; p2; : : : ; ps. Но условие hjj pi невыполнимо в силу 3), следовательно, не существует отличного от 1 унитарного наибольшего общего делителя h и p~, т.е. многочлены h и p~ взаимно просты:

торый не делится ни на один из неприводимых многочленов p1; p2; : : : ; ps. По св-ву 3 неприводимых многочленов, из этого предположения следует, что d взаимно прост с каждым из p1; p2; : : : ; ps, тогда по утв. 7 лекции 9 многочлен d взаимно прост с произведением p1p2 : : : ps, следовательно, взаимно прост с многочленом p~ = a0p1p2 : : : ps. Из

10