RUDN-I

9.1. Условия равенства многочленов										161
Доказательство леммы 2. Коэффициенты многочлена P вида (8), удо-
влетворяющего условиям (9), определяются из системы уравнений
p0 + p1zm+1			+ p2zm2 +1	+ . . . + pmzmm+1 =ruym+1
	p0 + p1z1		2				m		= y1
		+ p1z2	+ p2z2	+ . . . + pmz2					= y2
p0								.		(11)
		.	.	.			.		.
.					.
.		.	.			.	.		.
.		.	.				.		.
			matematem

Это система из (m + 1)-го линейного уравнения с (m + 1) неизвестными p0, p1, . . . , pm+1, причем ее определитель равен

				2			m
∆ =		1	z1	z12	. . .		z1m	.
		1	z2	z2	. . . z2
			.	2	.		m
	.			.		..	.
	..		..	..			..
		1	zm+1
				zm+1 . . . zm+1

Он совпадает с определителем Вандермонда порядка (m+1) (см. п. 4.5) и отличен от нуля, поскольку все числа z1, z2, . . . , zm+1 различны. Значит, система (11) имеет единственное решение (см. п. 5.5). Таким образом, многочлен P , удовлетворяющий условиям (8) — (9), существует, причем единственный.

В случае, когда y1	= y2 = . . . = ym+1 = 0, единственное решение одно-
	.	= p1 = . . . = pm = 0. Этим
родной системы (11) является нулевым: p0
www
доказано следствие 1.

Доказательство следствия 2. Из равенств (10) следует, что

(P − Q)(zk) = P (zk) − Q(zk) = 0, k = 0, 1, . . . , m + 1.

Тогда (по следствию 1) все коэффициенты многочлена P − Q нулевые, т.е.

p0 − q0 = p1 − q1 = . . . = pm − qm = 0 P = Q.

162 Тема 9. Многочлены над полем комплексных чисел

9.2. Кольцо многочленов

§ 1. Как и в п. 9.1 используем обозначения					ru
	∑l
	m
P (z) =	plzl,	pm ̸= 0,		.		(1)
	=0
	∑j
	n
Q(z) =	qjzj,	qn ̸= 0.				(2)
причем коэффициентыmatematemмногочлена
	=0
Определение 1. Сумма P + Q и произведение P · Q многочленов вида
(1), (2) определяются по правилам действия с функциями
(P + Q)(z) = P (z) + Q(z),			z C,			(3)
(P · Q)(z) = P (z) · Q(z),			z C.			(4)

Лемма 1. Сумма P + Q и произведение P · Q многочленов являются многочленами.

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

deg(P + Q) ≤ max{deg P, deg Q}.

Так, для многочленов вида (1), (2) при m < n

(P +Q)(z) = (p0 +q0)+(p1 +q1)z +. . .+(pm +qm)zm +qm+1zm+1 +. . .+qnzn.

б) При умножении многочленов их степени складываются:

		.			(5)
	www	deg(P · Q) = deg P + deg Q = m + n,
			∑k
			m+n
		R(z) = (P · Q)(z) =	=0	rkzk	(6)
вычисляются по формулам
	∑			0 ≤ j ≤ n; l + j = k}.	(7)
rk =	plqj, Ak = {(l, j) : 0 ≤ l ≤ m,

(l, j) Ak

Замечание 1. Если P, Q — многочлены с вещественные коэффициентами, то P + Q, P · Q также имеют вещественные коэффициенты.

9.2. Кольцо многочленов					163
Замечание 2. Формула (7), в частности, дает
(так что		A0 = {(0, 0)}, r0 = p0q0;
	deg (P · Q) = m + n = deg P + degruQ).
A1 =	{(0, 1), (1, 0)}, r1 = p0q1			+ p1q0;
A2 = {(0, 2), (1, 1), (2, 0)}, r2 = p0q1 + p1q1 + p2q0;
		. . .		.
Am+n = {(m, n)}, rm+n = pmqn ̸= 0
	matematemk=0 k=0
В другой форме равенство (7) можно записать, используя символ Кро-
некера:
δl+j, k = 1, если l + j = k,			δl+j, k = 0,	если l + j ̸= k.
Тогда		∑
∑l
m		n
rk =		δl+j, kplqj,	k = 0, 1, . . . m + n.		(8)

=0 j=0

Доказательство леммы 1. Часть а) леммы 1 очевидна. Докажем равенства (6) — (7). Умножая равенства (1) и (2), получим

∑l	∑	∑ ∑
m	n	m n
(P · Q)(z) =	plzl · qjzj =	plqjzl+j.
=0	j=0	l=0 j=0

В правой части приведем подобные члены, собирая слагаемые, у которых сумма (l + j) одинакова (и равна k {0, 1, . . . , m + n}), т.е. слагаемые с (l, j) Ak. В результате

	m+n	m+n
(P · Q)(z) =	(l, j) Ak	plqjzl+j =	zk	plqj,
.		∑		(l, j) Ak
	∑ ∑			∑
что и дает равенства (6) — (7). Равенство (5) следует из (6) — (7) (см.
замечание 2).
Упражнение. Получить равенства (8) (см. упражнение 9.1).

§ 2. Кольцоwwwмногочленов

Пусть P обозначает множество всех многочленов (любых степеней), дополненное функцией Θ(z) = 0, которую будем понимать как многочлен с нулевыми коэффициентами (его степень не определяется). На P мы ввели две алгебраических операции: сложение и умножение многочленов.

Частное многочленов

9.3. Деление

164 Тема 9. Многочлены над полем комплексных чисел

Теорема 1. Множество P образует коммутативное кольцо с единицей относительно операций сложения и умножения. В нем нет делителей нуля. Множество обратимых элементов кольца P совпадает с множеством многочленов нулевой степени (т.е. ненулевых постоянных).

Доказательство. 1) Выполнение всех аксиом кольца и коммутативность умножения проверяются как для любых функций. Отметим лишь, что

роль нуля играет "нулевой многочлен" Θ(z), и роль единицы — много-
член нулевой степени E(z) = 1.	.	ru
2) Покажем, что в P нет делителей нуля. Если P, Q ̸= Θ — многочлены
вида (1) — (2), то их старшие коэффициенты pm,	qn ̸= 0. Но тогда для

R = P · Q старший коэффициент равен rm+n = pm · qn ≠ 0 (см. лемму 1), т.е. R ≠ Θ.

3) Если P P — обратимыйmatematemмногочлен, то существует P −1 P, такой что P · P −1 = E. Но тогда deg P + deg P −1 = deg E = 0 (см. лемму 1), т.е.

1 deg P = deg P −1 = 0. Значит, P (z) = p0 ≠ 0; P −1(z) = p0 .

Замечание 3. Из теоремы 1 следует, в частности, что кольцо многочленов P не является полем. Все многочлены степени больше или равной единице необратимы.

многочленов

				∑l			∑
				m			n
	P (z) =				plzl, Q(z) = qjzj			(1)
www	.			=0			j=0
				P
определяется (как в п. 9.2) по правилам действия с функциями, т.е. как
функция, значения которой определяются формулой
		P		опр. P (z)				(2)
		Q		(z)	=	Q(z)	, z C.

Формула (2) имеет смысл во всех точках z C, где Q(z) ≠ 0.

Частное двух многочленов (в отличие от суммы и произведения) может уже не быть многочленом.

Приведем примеры деления многочленов.

Пример 1. Найти частное Q , где P (z) = z2 − 3z + 2, Q(z) = z − 1.

9.3. Деление многочленов

165

Квадратный трехчлен P (z) можно разложить на множители (по формулам, известным их школьного курса математики)

	Q			z 1		−		ru	(3)
P (z) = z2			− 3z + 2 = (z − 1)(z −				2)
и тогда при z ̸= 1							.
	P	(z) =		(z − 1)(z − 2)	= z	2.
	matematem
				−

Правая часть (3) имеет смысл и при z = 1, она равна (−1); так что мы

можем считать, что	P		(z) = z − 2 — многочлен 1-ой степени.
	Q
Пример 2. Найти частное				P		(z) =	3z4 + 5z3 − z2 + 2z − 5	.
				Q
							z2 + 1

Для нахождения частного используем известный из школы алгоритм деления углом, отраженный в следующей записи:

3z4 +5z3 − z2 +2z −5					z2 + 1
3z4		+3z2			3z2 + 5z − 4
	5z3 −4z2 +2z −5
	5z3		+5z
		−4z2	−3z −5
		−4z2		−4
			−3z −1

www

Итак,

3z

4

.

3

− z

2

+ 2z − 5

3z + 1

+ 5z

= 3z2 + 5z

−

4

.

(4)

z2 + 1

− z2 + 1

Упражнение 1. Сделать проверку равенства (4), т.е. показать, что

3z4 + 5z3 − z2 + 2z − 5 = (3z2 + 5z − 4)(z2 + 1) − (3z + 1).

(5)

Замечание 1. В примере 2 приведена конкретная реализация общего алгоритма деления многочленов с остатком, описанного в следующей теореме.

166 Тема 9. Многочлены над полем комплексных чисел

Теорема 1. (о делении многочленов с остатком)

1) Пусть P, Q — многочлены вида (1). Существуют многочлены H и R, такие что R = 0 или deg R < deg Q и

P = HQ + R.

(6)

2) Представление (6) единственно.
Замечание 2. В представлении (6) P называют делимым, H — част-
		ru
ным, R — остатком от деления P на Q. Если R =.0, то говорят, что
P делится на Q (как в примере 1), при этом Q называют делителем
многочлена P .
Замечание 3. Многочлен нулевой степени Q является, очевидно, дели-
телем любого многочлена P .
R1 = 0, либо	matematem

Доказательство теоремы 1. 1) Если m = deg R < n = deg Q, то положив H = 0, R = P , мы получим равенство (6), причем deg R = deg P < deg Q.

2) Пусть m ≥ n. Введем многочлены

					∑j
		pm	(1)	pm	n
H1	(z) =	qn	zm−n, Q1(z) = H1(z)Q(z) =	qn	qjzm−n+j.
					=0

Тогда, Q1 есть многочлен степени m со старшим коэффициентом (при zm), равным pm. Положим

R1 = P − Q1 = P − H1Q.

(7)

3) При условии, что n1 ≥ n, продолжим наше построение, применив к

Это многочлен степени не выше m (вместе с P и Q1), более того, либо
	.	n1 = deg R1	≤ m − 1,
поскольку коэффициент при zm в R1			равен pm − pm = 0. Итак,
		P = H1Q + R1,		(8)
где R1 = 0 или n1 = deg R1 ≤ m − 1. Если R1 = 0 или n1				< n, то (8) и
есть искомое представление (6) (с H = H1, R = R1).
www

R1 = r0 + r1z + . . . + rn1 zn1 , rn1 ≠ 0

e e

0 = (H − H)Q + (R − R),

9.3. Деление многочленов					167
тот же прием деления на Q. Введем				∑j
	rn1		rn1	n
H2(z) =		zn1−n, Q2(z) = H2(z)Q(z) =			qjzn1−n+j.
	qn		qn	=0	ru

Тогда Q2 есть многочлен степени n1	со старшим коэффициентом (при
zn1 ), равным rn1 . Положим	.

Это многочлен степени не выше n1, более того, либо R2 = 0, либо

n2 = deg R2 ≤ n1 − 1,
поскольку коэффициент при zn1 в R2 равен rn1 − rn1	= 0. Итак,
R1 = H2Q + R2,	(9)
где R2 = 0 или n2 = deg R2 ≤ n1 − 1 ≤ m − 2. Подставим (9) в (8):
P = (H1 + H2)Q + R2.	(10)

Если R2 = 0 или n2 = deg R2 < n = deg Q, то (10) и есть искомое представление (6) (с H = H1 + H2, R = R2).

4) Если все еще n2 ≥ n, алгоритм деления на Q можно продолжить. На каждом шаге степень остатка уменьшается (как минимум) на единицу. На k-ом шаге получим представление

где либо Rk = 0, либо nk = deg Rk ≤ nk−1 − 1 ≤ m − k. При достаточ-

matematemR2 = R1 − Q2 = R1 − H2Q.

	.	P = (H1 + H2 . . . + Hk)Q + Rk,	(11)
www

но большом k получим искомое неравенство nk < n. Тогда (11) и есть искомое представление (6) (с H = H1 + H2 + . . . + Hk, R = Rk).

5) Осталось показать единственность представления (6) (в частности, его независимость от конкретного алгоритма, примененного выше). Допустим, что кроме (6) есть еще представление

	P = HQ + R,	deg R < deg Q.	(12)
Вычтем (12) из (6) и	получим	e
	e e

где

168

Тема 9.

Многочлены над полем комплексных чисел

т.е.

R − R = −(H − H)Q.

(13)

Но если

R

=

R

, то deg (

R

R

)

< deg Q

этом

H =

H

, т.е.

e

e ; при

̸

deg (H

̸

−

−

≥ e

e

e

равенствоe(13) возможно только при H = H, R = R. Итак, представле-

ние (12) совпадает с (6).

e

e

Теорема 1 доказана.

. ru

Лемма 1. (Схема Горнера деления многочлена на двучлен)

Пусть

matematem

P (z) = p0 + p1z + . . . + pn−1zn−1 + pnzn, pn ≠ 0;

P (z) = (z − c)Q(z) + R,

Q(z) = q0 + q1z + . . . qn−1zn−1.

Тогда коэффициенты qn−1, qn−2, . . . , q1, q0 и остаток R находятся

(последовательно) из формул

qn−1 = pn, qn−2 = pn−1 + cqn−1, . . . , q0 = p1 + cq1, R = p0 + cq0.

Упражнение 2. Доказать эту лемму (см. упражнение 9.2).

Упражнение 3. Показать, что если многочлены P и Q в теореме 1 имели вещественные коэффициенты, то частное H и остаток R также имеют вещественные коэффициенты (см. упражнение 9.3).

9.4. Наибольший общий делитель двух многочле-

Определениеwww1. 1) Многочлен R называется общим делителем многочленов P и Q, если он является делителем каждого из них.

нов	.

2) Общий делитель R многочленов P и Q называется наибольшим общим делителем (кратко: НОД), если он делится на любой общий делитель многочленов P и Q.

Опишем алгоритм Евклида нахождения НОД (называемый также алгоритмом последовательного деления). Считаем для определенности, что deg Q ≤ deg P .

9.4. Наибольший общий делитель двух многочленов

169

Если P делится на Q, то Q будет общим делителем для P и Q, причем, очевидно, наибольшим. Если P не делится на Q (без остатка), делаем

первый шаг.			ru
Шаг 1. Делим P на Q с остатком (согласно теореме 1 п. 9.3):
	P = H1Q + R1,	.		(1)
где H1, R1 — многочлены, причем deg R1 < deg Q.
	matematem	делится на R1		, т.е. R1
а) Если Q делится на R1, то в силу (1), также и P
есть общий делитель для P и Q. Если R есть еще один общий делитель
для P и Q, то
	(1)			(2)
	R1 = P − H1Q

делится на R (вместе с P и Q). Значит, R1 — искомый НОД.

б) Если Q не делится на R1 (без остатка), делаем следующий шаг.

Шаг 2. Делим Q на R1 с остатком (согласно теореме 1 п. 9.3):

Q = H2R1 + R2,

(3)

где H2, R2 — многочлены, причем deg R2 < deg R1.

а) Если R1 делится на R2, то в силу (3), также и Q делится на R2, а тогда, в силу (1), и P делится на R2 (вместе с R1 и Q); т.е. R2 есть общий делитель для P и Q. Если R — еще один общий делитель для P и Q, то, в силу (2), R1 также делится на R, а тогда

	(1)	(4)
	R2 = Q − H2R1
также делится на R. Значит, R2 — искомый НОД.
	.
б) Если R1 не делится на R2 (без остатка), делаем следующий шаг.
www	на R2 с остатком (согласно теореме 1 п. 9.3):
Шаг 3. Делим R1
	R1 = H3R2 + R3,	(5)

где H3, R3	— многочлены, причем deg R3 < deg R2.
а) Если R2	делится на R3, то в силу (5), R1 также делится на R3, затем,
в силу (3), и Q делится на R3 (вместе с R1 и R2); далее, в силу (1), P
делится на R3 (вместе с Q и R1). Итак, R3		— общий делитель для P и
Q. Если R — еще один общий делитель для P и Q, то, в силу (2), (4), и
равенства
	(5)	(6)
	R3 = R1 − H3R2

170	Тема 9. Многочлены над полем комплексных чисел
получим, что на R делятся R1, R2, а также R3. Итак, R3 — искомый
НОД.	ru

б) Если R2 не делится на R3 (без остатка), делаем следующий шаг и т.д.

Выводы. 1) На каждом шаге мы или находим искомый НОД, или переходим к остатку меньшей степени: deg R1 > deg R2 > deg R3 > . . .

2) На k-ом шаге получим цепочку равенств (считая, что на предыдущих

matematemR1 = P − H1Q,				.
шагах НОД еще не был найден)
P = H1Q + R1,
		+ R2	,
Q = H2R1
R1 = H3R2 + R3,				(7)
	−	−
. . . . . . . . .
			+ Rk
Rk 2 = HkRk 1

3) Для достаточно большого k заведомо получим, что Rk−1 делится на Rk (в "худшем случае" это произойдет, когда окажется deg Rk = 0, поскольку многочлен нулевой степени является делителем любого многочлена, см. замечание 3 к теореме 1 п. 9.3).

4) Покажем, что в этом случае Rk и есть НОД для P и Q. Проходя цепочку (7) снизу вверх, получаем последовательно, что на Rk делятся Rk−2, . . . , R3, R2, R1, Q, P , т.е. Rk есть общий делитель для P и Q. Если R — еще один общий делитель для P и Q, то, проходя сверху вниз соответствующую (7) цепочку равенств:

.	R2 = Q	−	H2R1,
				H3R2,		(8)
	R3 = R1
		−
	. . . . . . . . .
				HkRk 1,
	Rk = Rk 2
		−		−	−

получимwwwпоследовательно, что на R делятся R1, R2, R3, . . . , Rk. Таким образом, Rk есть НОД для P и Q.

Упражнение 1. Показать, что НОД многочленов P и Q является единственным с точностью до постоянного множителя (см. упражнение 9.4).