Mnogochlen

Замечание 4.4. Поскольку степени остатков убывают

deg r0 = deg g > deg r0 > deg r1 > ¢ ¢ ¢ >;

должен появится остаток нулевой степени, который либо равен нулю, либо неулевому многочлену нулевой степени, который должен делить любой многочлен. Поэтому алгоритм Евклида обязательно заканчивается через конечное число шагов.

Теорема 4.1 Пусть f; g 2 K[x]; g =6 0 и пусть

f = gq1 + r1; f; g; q1; r1 2 K[x]; deg r1 < deg g;

g = r1q2 + r2;	q2; r2 2 K[x];	deg r2 < deg r1;
r1 = r2q3 + r3;	q3; r3 2 K[x];	deg r3 < deg r2;
	¢ ¢ ¢
ri¡1 = riqi+1 + ri+1;	qi+1; ri+1 2 K[x]; deg ri+1 < deg ri;
	¢ ¢ ¢

rn¡1 = rnqn+1

- соответсивующий алгоритм Евклида. Положим r¡1 = a; r0 = b Тогда

rn = (f; g):

Доказательство. Доказательство проведем индукцией по числу шагов в алгоритме Евклида. Для алгоритма в один шаг:

r¡1 = f = gq1 + 0 = r0q1	Предложение 3.3	g = r0 = (f; g)
	)

Предположим, что утверждение Теоремы истинно для всех пар многочленов, для которых алгоритме Евклида имеет не более n-шагов. Заметим, что для пары g; r1 алгоритме Евклида имеет как раз n-шагов. Поэтому, ввиду предположения индукции rn = (g; r1). Так как f = gq1 + r1, то ввиду Предложения 3.4, rn = (f; g).

¤

Замечание 4.5. Ввиду Теоремы 4.1, для любой пары f; g 2 K[x]; g =6 0 существует наибольший общий делитель f; g, а именно, им является последний ненулевой остаток в алгоритме Евклида.

Некоторые свойства наибольшего общего делителя пары многочленов.

21

Теорема 4.2 Для любой пары многочленов f; g 2 K[x]; g 6= 0 существует единственный нормализованный наибольший общий делитель d = (f; g). Кроме того, многочлен d0 является наибольшим общим делителем многочленов f; g тогда и только тогда, когда d0 = ®d для некоторого ® 2 K¤.

Доказательство. Пусть d1 = (f; g); d2 = (f; g). Тoгда

d1 j d2; d2 j d1 ) d1 = d2e; d2 = d1f для некоторых e; f 2 K[x] )

) d1	(1 ¡ ef) = 0; d2	Следствие 2.11	ef = 1	Следствие 2.11
		(1 ¡ ef) = 0 )		)
|{z}	|{z}
6=0	6=0

) e; f 2 K¤ = K n f0g; f = e¡1:

Таким образом, любые два наибольших общих делителей f; g различаются на ненулевой множитель из поля K. Далее, пусть d = (f; g) -какой -либо наибольший общий делитель f; g и ® 2 K¤. Тогда ®d -также наибольший общий делитель f; g.

Таким образом, существует единственный нормализованный наибольший общий делитель многочленов f; g и любой наибольшим общим делителем многочленов f; g отличается от нормализованного на множитель из K¤.

¤

Теорема 4.3. Теорема о линейном выражении НОД. Пусть f; g 2 K[x]; g 6= 0. Тогда сушествуют такие многочлены Á; Ã 2 K[x], что

(f; g) = Áf + Ãg:

Доказательство проведем индукцией по числу шагов в алгоритме Евклида (4.2) для многочленов f; g. Для алгоритма в один шаг: f = gq1 . Имеем g = 1g + 0f. Предположим, что утверждение Теоремы истинно для всех пар многочленов, для которых алгоритме Евклида имеет не более n-шагов. Тогда

(f; g) = Á0g + Ã0r1:

Следовательно,

(f; g) = Á0g + Ã0(f ¡ gq1) = Ã0	f + (Á0			¡ q1) g:
|{z}	|			{z		}
:=Á			:=Ã
¤

22

Следствие 2.11

)

Замечание 4.5. Доказательство Теоремы 4.3 содержит алгоритм вычиcления многочленов Á; Ã. А именно, начнем с предпоследнего равенства :

rn¡2	= rn¡1qn + rn ) (f; g) = 1 rn¡2 + (¡qn) rn¡1:
		|{z}	¡
	| {z }		|		{z		}
	=rn Án¡2		Ãn 2

Предположим вычислили разложение

(f; g) = Áiri + Ãiri+1:

Тогда

ri¡1 = riqi+1 + ri+1 ) (f; g) = Áiri + Ãi(ri¡1 ¡ riqi+1) = Ái¡1 ri¡1 +

|{z}

=Ãi

Ãi¡1 ri

|{z}

=(Ái¡qi+1)

и далее,
= ¢ ¢ ¢ = Á f + Ã g :
|{z}|{z}	|{z} |{z}
=Á¡1 =r¡1	=á1 =r0
Теорема 4.4. Пусть f; g 2 K[x]; g 6= 0 и ¢ = fh 2 K[x]			j h j f; h j gg-множество
общих делителей f; g. Пусть, далее, d 2 ¢. Тогда
d = (f; g) , deg d = maxfdeg h j h 2 Mg:
Доказательство. Пусть d = (f; g).
d = (f; g) ) d : h для любого h 2 ¢		Следствие 2.11
			)

) deg h · deg d для любого h 2 ¢:

Пусть deg d = maxfdeg h j h 2 Mg

deg d = maxfdeg h j h 2 Mg; d j (f; g)

) d = (f; g)

¤

Замечание 4.6. Теорема 4.4 позволяет определить наибольший общий делитель двух многочленов, как общий делитель максимальной степени.

Взаимно простые многочлены.

Определение. 4.3. Многочлены f; g 2 K[x] называются взамно простыми, если

1 = (f; g)

Теорема 4.5. Пусть f; g 2 K[x]; f; g =6 0. Тогда

f = (f; g)f1; g = (f; g)g1

23

где f1; g1 2 K[x]; (f1; g1) = 1.

Доказательство. Так как (f; g)-общий делитель f; g, то f = (f; g)f1; g = (f; g)g1 для некоторых многочленов f1; g1 2 K[x]. Ввиду Теоремы 4.3,

Следствие 2.11	1 = (Áf1 + Ãg1):
(f; g) = Áf + Ãg = (f; g)(Áf1 + Ãg1) )

Но из равенства 1 = (Áf1 + Ãg1) следует, что все общие делители f1; g1-это только многочлены нулевой степени, а значит 1 = (f1; g1)

¤

УПРАЖНЕНИЯ.

Докажите следующие простейшие своства взаимно простыех многочленов (Указание : воспользйтесь следующим свойством : многочлены f; g -взамно просты тогда и только тогда когда 1 = Áf + Ãg для некоторых Á; Ã 2 K[x]).

1) Пусть многочлены последовательности f1; : : : ; fn 2 K[x] взаимно простыми с многочленом g 2 K[x]. Тогда мнгочлен Qni=1 f1 взаимно прост с многочленом g.

2) Пусть многочлены последовательности f1; : : : ; fn 2 K[x] попарно взаимно про-

стыми с многочленами последовательности g1; : : : ; gm 2 K[x]. Тогда мнгочлен		in=1 f1
	Q	Q
взаимно прост с многочленом	m
	j=1 gj.

3)Пусть многочлены f; g -взаимно просты и пусть fh : g для некоторого h 2 K[x]. Тогда h : g.

4)Пусть многочлены последовательности f1; : : : ; fn 2 K[x] попарно взаимно просты и пусть f : fi для любого i = 1; : : : ; n. Тогда f : Qni=1 f1.

Вычисление наименьшего общего кратного двух многочленов.

Теорема 4.5. Пусть f; g 2 K[x]; f; g 6= 0. Тогда (f; g) j fg и

	fg		= [f; g]:
	(f; g)

(здесь дробь обозначает частное от деления).

Доказательство. Пусть d = (f; g); f = df1; g = dg1. Далее,

fg

[f; g] = (f; g) = f1g1d = fg1 = gf1 : f; g:

24

Пусть e 2 K[x],

e : f; e : g ) e = df1q = dg1p для некоторых p; q 2 K[x] )

Упр.3)

) f1q = g1p ) q : g1 ) q = g1l для некоторого l 2 K[x] )

fg ) e = df1q1l : df1g1 = (f; g):

¤

Замечание 4.6. Таким образом, наименьшее общее кратное двух многочленов f; g 2 K[x]; f; g =6 0 существует. Кроме того, имеет место аналог Теорем 4.2 и 4.4, т.е. существует единственное нормализоанное наименшее общее кратное и все остальные наименшие общие кратные отличаются от него на множитель из K¤ и, кроме того, общее кратное двух многочленов f; g 2 K[x]; f; g =6 0 является наименшим общим кратным тогда и только тогда , когда оно имеет минимально возможную степень (докажите эти аналоги !).

x 5: Значения и корни

многочленов над полем.

В данном параграфе A- кольцо ,K-поле, а A[x]; K[x]-кольца многочленов от одной буквы над A; K соответственно.

Значения многочленов.

Пусть f 2 A[x] . В x 1: обсуждался вопрос об определении многочлена как функци f : A ! A. Было показано, что разным многочленам может соответствовать одна и та же функция. В данном параграфе мы подробнее изучим функции соответствующие мнгочленам, в особенности многочленам над полями.

Пусть f = [F ] 2 A[x] и пусть
F = a1xn1 + a2xn2 + ¢ ¢ ¢ + amxnm :
Для любого ® 2 A положим
F (®) = a1®n1 + a2®n2 + ¢ ¢ ¢ + am®nm :	(5:1)

Таким образом, имеем функцию A ! A, которую будем обозначать

^

F : A ! A;

^

определенную формулой F (®) = F (®).

25

Пусть теперь G Ã F . Тогда для любого ® 2 A имеем

F (®) = G(®):

(Действительно, достаточно рассмотреть случаи, когда G Ã F являются элементарными тождественными преобразованиями формальных сумм одночленов. В этих случаях равенство F (®) = G(®) вытекает непосредственно из свойств операций в кольце.) Теперь мы можем определить функцию

f^ : A ! A;

^ ^

полагая f(®) = F (®). В частности, в качестве F можно рассматривать нормальную форму (что и происходило в x 1:)

Соглашение. В далнейшим мы будем опускать^над f, рассматривая многочлен f как функцию (имея ввиду однако , что равентво таких функций не есть в общем случае равенство соответствующих многочленов). Если требуется подчеркнуть, что многочлен рассматривается как функция или выделить аргумент этой функции будем записывать многчлен в виде: f(x).

Определение 5.1. Элемент f(®) называется значением многочлена f 2 A[x] при x = ® (или в "точке ®").

Пусть f; g 2 A[x]. Тогда

(f + g)(®) = f(®) + g(®):

(5:2)

(Действительно, поскольку значение функции, соответствующей многочлену не зависит от выбора формы, в качестве формы f + g можно взять форму, соответствующую приписыванию формы g со знаком + к форме f. Тогда (5.1) просто следует из определения (5.1).)

Пусть f; g 2 A[x] и A-коммутативное кольцо. Тогда

(fg)(®) = f(®)g(®):

(5:3)

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

Замечание 5.1 Если кольцо A-некоммутативно, то равенство (5.3) в общем случае неверно. Например, пусть ®; ¯ 2 A и пусть ¯®¯® =6 ¯2®2. Далее, пусть f = g = bx. Тогда (fg)(®) = ¯2®2 ==6 ¯®¯® = f(®)g(®).

Пусть f 2 A[x]. Тогда для любого ® 2 A возможно деление с остатком:

f = (x ¡ ®)g + r; 0 = deg r < deg g

(5:4)

26

(см. Замечание 4.) Предположим, A-коммутативное кольцо. Тогда, ввиду (5.3), (5,4)

f(®) = (® ¡ ®)g(®) + r(®) = r:

(5:5)

Таким образом, значение многочлена над коммутативным кольцом равно остатку от деления на двучлен x ¡ ®.

Схема (алгоритм) Горнера вычисления значения многочлена.

Формула (5.5) позволяет сократить число опрераци при вычислении значения многочлена f 2 A[x] в точке ® 2 A.

Пусть

f = f(x) = a0xn + a1xn¡1 + ¢ ¢ ¢ + an; q = f(x) = b0xn¡1 + b1xn¡2 + ¢ ¢ ¢ + bn¡1:

Из равенства (5.5) получаем

a0 = b0; a1 = b1 ¡ ®b0; : : : ; an¡1 = bn¡1 ¡ ®bn¡2; an = r ¡ ®bn¡1:

Следоательно,

b0 = a0; b1 = a1 + ®b0; : : : ; bn¡1 = an¡1 + ®bn¡2; r = an + ®bn¡1:

Таким образом, значение многочлена в точке ® можно вычислить за n + 1 шаг. При этом, каждый шаг (за исключением последнего)- это вычисление i-того коэффициента многочлена q:

bi = ai + ®bi¡1:

Алгоритм Горнера может быть записан в виде следующей таблицы.

	a0	a1	¢ ¢ ¢ ¢ ¢ ¢	an¡1	an
®	b0 = a0	b1 = a1 + ®b0	¢ ¢ ¢ ¢ ¢ ¢	bn¡1 = an¡1 + ®bn¡2	r = an + ®bn¡1

Корни многочленов.

Определение 5.2. Пусть f 2 A[x]. Элемент ® 2 A называется корнем многочлена f, если f(®) = 0.

Из формулы (5.5) вытекает следующее утверждение:

® ¡ корень многочлена f , f : (x ¡ ®):

(5; 6)

(Это утверждение иногда называют Теоремой Безу.)

Теорема 5.1. Пусть f 2 K[x]; f =6 0. Тогда число корней многчлена f, содержащихся в поле K не превосходит его степени.

27

Доказательство. Пусть ®1; : : : ; ®m 2 K -различные корни f в K. Многочлены (x¡®1); : : : ; (x¡®m -попарно взамно просты (Следствие 2.11). Следовательно ((5.6),x4

Упражнение 4)):

Ym

f : (x ¡ i) ) m · deg f:

i=1

¤

Замечание 5.2 Над кольцом это утверждение Теоремы 5.1 - неверно. Например, пусть A = Z=nmZ, где n; m 2 N; n; m =6 1 и пусть f = nx¹ . Тогда m;¹ 2m; : : : ; (n ¡ 1)m- корни f.

Cледствие 5.2. Пусть f; g 2 K[x]. Предположим, что поле K-бесконечно. Тогда, если многочлены f; g совпадают как функции на K, то f = g.

Доказательство. Пусть f(x) = g(x). Положим h = f ¡ g. Тогда h(®) = 0 для любого ® 2 K. Ввиду Теоремы 5.1., h = 0.

¤

Замечание 5.3 Таким образом, над бесконечным полем многочлены можно определять как функции.

Кратные корни.

Определение 5.2. Пусть f 2 A[x]. Элемент ® 2 A называется корнем многочлена f кратности k 2 N, если (x ¡®)k j f и (x ¡®)k+1 - f Корни кратности k = 1 называются простыми корнями.

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

Дифференцирование многочленов.

Пуст A-коммутативное кольцо с единицей. Элемент кольца A равный

1 + 1 + ¢ ¢ ¢ + 1

| {z }

n раз

будем также обозначать n.

Определим операцию дифференцирования D формальной суммы

F = a1xn1 + a2xn2 + ¢ ¢ ¢ + amxnm ;

28

одночленов над A следeющим образом:

	def	¡1 + n2a2xn2	¡1 + ¢ ¢ ¢ + nmamxnm¡1
D(F ) = n1a1xn1
(если ni = 0, то nixni¡1	def
	= 0).

Пусть G Ã F . Тогда

D(G) Ã D(F )

достаточно рассмотреть случаи, когда G Ã F являются элементарными тождественными преобразованиями формальных сумм одночленов для которых данное утверждение очевидно.) Теперь можно определить отображение дифференцирования

D : A[x] ! A[x]

, а именно,

def

D(f) = [D(F )]:

Предложенеие 5.2. Пуст A-коммутативное кольцо с единицей. Тогда

1)D(f + g) = D(f) + D(g) для любых f; g 2 A[x];

2)D(®) = 0 для любого ® 2 A;

3)D(®f) = ®D(f) для любых f 2 A[x]; ® 2 A;

4)D(fg) = D(f)g + fD(g) для любых f; g 2 A[x].

Доказатенльство. Свойства 1),2),3) непосредственно следуют из определения дифференцирования.

Рассмотрим свойство 4). Пусть f = [F ]; g = [G];

F = a1xn1 + a2xn2 + ¢ ¢ ¢ + arxnr ; G == b1xm1 + b2xm2 + ¢ ¢ ¢ + bsxns :

Тогда	X
	fg = [ aibjxni+mj ];
X	i;j
	X
D(fg) = [	aibjD(xni+mj )] = [ aibj(ni + mj)xni+mj¡1] =
i;j	i;j
X
= [	aibj((D(xni ) xmj + xni D(xmj ))] =
X	i;j
	X
= [ aibjD(xni ) xmj ] + [ aibjxni D(xmj )] = [D(F )G] + [F D(G)] =
i;j	i;j

= D(f)g + fD(g):

¤

Пусть f 2 A[x] Положим:

f0 := D(f); f00 = D ± D(f); f[3] := D ± D ± D(f); : : : ;

29

f[m] := D ± D ± ¢ ¢ ¢ ± D(f); f[0]						:= 0:
|			{z		}
		nраз
Теорема 5.3 Пусть char K = 0;		f 2 K[x]; f 6= 0 и ® 2 K. Тогда

® ¡ корень кратности k , f(®) = 0; f0(®) = 0; : : : ; fk¡1(®) = 0; f[k](®) =6 0:

Доказательство.

1))

® ¡ корень кратности					k для f , f = (x ¡ ®)kg; g(®) 6= 0 )
, f0 = (x ¡ ®)k¡1 ( k		g + (x ¡ ®)g0) ) ® ¡ корень кратности k ¡ 1 для f0:
|{z}		=Á; Á(®)=0
|	6=0		{z			}
				6

Теперь используем индукцию по k.

2) ( Пусть f(®) = 0; f0(®) = 0; : : : ; fk¡1(®) = 0; f[k](®) 6= 0 пусть e-кратность корня ®. Тогда , ввиду 1), f(®) = 0; f0(®) = 0; : : : ; fm¡1(®) = 0; f[m](®) 6= 0. Следоателно, m = k.

¤

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

Определение 5.3. Поле K назыается алгебраически замкнутым, если любой многочлен f 2 K[x]; deg f ¸ 1 имеет корень в поле K.

Теорема 5.4 Пусть K алгебраически замкнутое поле и f 2 K[x]; n = deg f ¸ 1. Тогда

f = a0(x ¡ ®1)m1 (x ¡ ®2)m2 ¢ ¢ ¢ (x ¡ ®k)mk ;

где a0-старший коэффициент многочлена f, ®1; : : : ; ®k 2 K все попарно различные корни многочлена f , содержащиеся в поле K, а m1; : : : ; mk-их кратности.

Доказательство. Индукция по n:

n = 1

)

f = a

x + a

; a

= 0;

)

f = a

(x

¡

(

¡a1

)):

0

1

0 6

0

a0

|

®

deg f = n

Опр.5.3., Т. Безу

={z1 }

)

f = (x ¡ ®1)g; deg g = n ¡ 1 )

Предположение индукции

g = a0

(x ¡ ®1)m1¡1(x ¡ ®2)m2 ¢ ¢ ¢ (x ¡ ®k)mk )

)

) f = a0(x ¡ ®1)m1 (x ¡ ®2)m2 ¢ ¢ ¢ (x ¡ ®k)mk :

¤

30