Гашков С.Б. Современная элементарная алгебра в задачах и решениях

Подождите немного. Документ загружается.

§ 3.2. Алгоритм Евклида и теорема Безу 141

§ 3.2. Алгоритм Евклида и теорема Безу

Для простоты далее будем считать, что кольцо коэффициентов K есть

либо Z

––

кольцо целых чисел, либо F

––

поле.

Пусть многочлены f(x) и g(x) принадлежат кольцу K [x].

Определение 73. Многочлен f(x) делится на g(x), если суще

ствует такой многочлен a(x) ∈K [x], что f(x) = g(x) · a(x) (обозначение

g(x) | f(x)).

Другими словами, многочлен f(x) делится на g(x), если остаток

от деления равен нулю.

Справедливы следующие очевидные свойства отношения делимости:

1) если f(x) делится на g(x), а g(x) делится на h(x), то f(x) делится

на h(x);

2) если f(x) и g(x) делятся на h(x), то u(x) f(x) + v(x) g(x) делится

на h(x).

Определение 74. Многочлен d(x) называется наибольшим общим

делителем (НОД) многочленов f(x) и g(x), если каждый из них делится

на d(x) и любой их общий делитель делит d(x), причем будем считать для

определенности старший коэффициент d(x) равным 1.

Для НОД будем использовать обозначение d(x) = (f(x), g(x)).

Используя теорему о делении с остатком, можно для нахождения

НОД двух многочленов над заданным полем коэффициентов применить

алгоритм Евклида аналогично тому, как это делалось для целых чисел:

f(x) = g(x) ·q

(x) + r

(x), где 0 6 deg r

(x) < deg g(x),

(f(x), g(x)) = (g(x), r

(x))

g(x) = r

(x) ·q

(x) + r

(x), где 0 6 deg r

(x) < deg r

(x),

(f(x), g(x)) = (g(x), r

(x)) = (r

(x), r

(x)),

(x) = r

(x) ·q

(x) + r

(x), где 0 6 deg r

(x) < deg r

(x),

(f(x), g(x)) = (r

(x), r

(x)) = (r

(x), r

(x)),

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

n−2

(x) = r

n−1

(x) ·q

n−1

(x) + r

(x), где 0 6 deg r

(x) < deg r

n−1

(x),

(f(x), g(x)) = (r

n−2

(x), r

n−1

(x)) = (r

n−1

(x), r

(x)),

n−1

(x) = r

(x) ·q

(x),

(f(x), g(x)) = (r

n−1

(x), r

(x)) = r

(x).

Осуществимость и однозначность этого процесса последовательного де

ления обосновывается теоремой о делении с остатком.

142 Глава III. Многочлены

Аналогично соответствующей теореме о НОД чисел доказывается

следующая теорема о линейном представлении НОД многочленов.

Теорема 64. Для любых многочленов f(x), g(x) над произвольным

полем F существуют такие многочлены a(x), b(x) ∈ F [x], что

d(x) = a(x) f(x) + h(x) g(x).

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

(x) = u

(x) f(x) + v

(x) g(x).

Подобно числовому случаю, алгоритм Евклида для многочленов можно

расширить так, чтобы он вычислял не только последовательность r

(x),

но и последовательности u

(x), v

(x), а значит, и линейное представле

ние НОД.

Определение 75. Каждому многочлену f(x) ∈K[x] можно сопоста

вить реализуемую им полиномиальную функцию

f : K →K , определя

емую равенством

f (x) = a

+ a

n−1

+ ... + a

x + a

где a

, a

n−1

, ..., a

, a

––

его коэффициенты.

Легко проверить, что сумме многочленов соответствует сумма реали

зуемых ими полиномиальных функций, а произведению

––

произведение

этих же функций.

Определение 76. Корнем многочлена f(x) ∈K[x] называется любой

такой элемент α ∈K , что f(α) = 0.

Теорема 65 (Безу). Для любого f(x) ∈ K[x], deg f(x) > 1, и для лю-

бого корня α ∈K данного многочлена f(x) справедливо равенство

f(x) = (x −α) g(x).

Д о к а з а т е л ь с т в о. Выполняя деление с остатком, получаем, что

для любого f(x) ∈K[x], deg f(x) > 1, и для любого α ∈K справедливо ра

венство f(x) = (x −α) g(x) + r, где r ∈K . Подставляя в него x = α, имеем

r = 0.

Теорема 66 (о числе корней). Любой многочлен f(x) степени n

над областью целостности K имеет не более n корней.

Д о к а з а т е л ь с т в о. База индукции (n = 1) очевидна. Выполним

шаг индукции.

Пусть теорема верна для многочленов степени n −1. Если многочлен

f(x) степени n не имеет корней в K , то утверждение очевидно верно.

§ 3.2. Алгоритм Евклида и теорема Безу 143

Если α

––

корень f(x), то f(x) = (x − α

)h(x) согласно теореме

Безу. Пусть α

––

корень многочлена f(x) и α

6= α

, тогда f(α

) =

= (α

−α

)h(α

) = 0 и α

−α

6= 0, но в области целостности нет дели

телей нуля, следовательно, h(α

) = 0, а h(x) имеет не более n −1 корней

по предположению индукции, значит, многочлен f(x) имеет не более n

корней.

Следствие из теоремы 66. Если многочлен f(x) степени n с ко-

эффициентами из области целостности K имеет в ней n корней,

то его можно представить в виде произведения элемента из K

на n линейных множителей с коэффициентами из K.

З а м е ч а н и е.



Утверждение теоремы неверно в том случае, если кольцо K не яв

ляется областью целостности.

Упражнение 59. Квадратный двучлен x

−1 имеет в кольце Z

че

тыре корня (

7).

Теорема 67 (о полиномиальных функциях). Пусть область це-

лостности K бесконечна и два многочлена f

(x) и f

(x) над K прини-

мают одинаковые значения при всех c ∈K , т. е. равны как функции.

Тогда эти многочлены совпадают друг с другом.

Д о к а з а т е л ь с т в о. Рассуждаем от противного. Пусть степень

многочлена F(x) = f

(x) − f

(x) равна n. Из условия теоремы следует, что

можно выбрать n + 1 элементов из K , которые являются корнями этого

многочлена. Тем самым получено противоречие с теоремой 66.

Из доказанной теоремы вытекает, что по известным значениям мно

гочлена степени n в n + 1 различных точках многочлен определяется

однозначно.

Однако не сразу ясно, как его выразить в явном виде. Если область

целостности является полем, то для этого можно использовать интер

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

параграфе.

Задачи и упражнения к § 3.2

1. Многочлен x

∈Z

[x] имеет в Z

четыре корня и четыре разныx

разложения на неприводимые (т. е. неразложимые далее) множители

в Z

[x].

2. Если f(x) и g(x) ∈ F[x], где F

––

поле, и степень f(x) не меньше сте

пени g(x), то f(x) однозначно представим в виде f = f

+ f

g + . .. + f

где степени f

меньше степени g.

144 Глава III. Многочлены

3. Число корней многочлена f(x) ∈F[x] в поле F не превосходит его

степени, даже если каждый корень считать столько раз, какова его крат

ность.

4. Разложите на множители x

+ x

+ x + 1 над полем Z

5. Найдите (x

+ x

+ 1, x

+ x

+ 1) над полем Z

6. Найдите (x

+ x

+ 1, x

+ x

+ 1) над полем Q.

Далее все многочлены рассматриваются над полем Q.

7. Применяя алгоритм Евклида, найдите такие многочлены M

и M

что (x

−4x

+ 1)M

(x) + (x

−3x

+ 1)M

(x) = 1.

8*. Применяя алгоритм Евклида, найдите (x

+ a

, x

+ a

9. Применяя алгоритм Евклида, докажите, что

−1, x

−1) = x

(n,m)

−1.

10. Применяя алгоритм Евклида, докажите, что при k | (n, m)



−1



(n,m)

−1

11. (Гаусс.) Докажите, что все рациональные корни многочлена

f(x) = a

+ ... + a

с целыми коэффициентами имеют вид ±p

q, где

p |a

, q | a

, (p − mq) | f(m).

§ 3.3. Интерполяция

Пусть дана таблица значений многочлена степени n над полем F

x x

... x

n−1

f(x) y

... y

n−1

где x

, ..., x

––

различные, а y

, ..., y

––

необязательно различные эле

менты поля F .

Определение 77. Многочлены

(x) =

(x − x

) (x − x

) ... (x − x

k−1

) (x − x

k+1

) ... (x − x

n−1

) (x − x

)

−x

) (x

−x

) ... (x

−x

k−1

) (x

−x

k+1

) ... (x

−x

n−1

) (x

−x

)

где k = 0, ..., n, называются фундаментальными многочленами

Лагранжа.

§ 3.3. Интерполяция 145

Справедлива следующая лемма.

Лемма 19. Для x = x

, ..., x

(x) =

(

1, если x = x

0, если x 6= x

Д о к а з а т е л ь с т в о. Непосредственно проверяется, что при x 6= x

числитель дроби, определяющей многочлен, обращается в нуль, а при

x = x

этот числитель не равен нулю и совпадает со знаменателем.

Определение 78. Многочлен степени n

f(x) = y

(x) + y

(x) + .. . + y

(x)

называется интерполяционным многочленом Лагранжа *, соответ

ствующим данной таблице значений.

Теорема 68 (интерполяционная формула). Интерполяционный

многочлен Лагранжа f(x) принимает значения, указанные в дан-

ной таблице, т. е. решает задачу интерполяции.

Д о к а з а т е л ь с т в о. Из леммы следует, что при x = x

(x) = y

а все остальные слагаемые определяющей многочлен суммы обращаются

в нуль. Поэтому вся сумма тогда равна y

, т. е. f(x

) = y

Упражнение 60. Проверьте, что вычисление коэффициентов ин

терполяционного многочлена по формуле Лагранжа

––

Варинга требует n

сложений, 2n

+ 2n вычитаний, 2n

+ n −1 умножений и n + 1 делений.



Для многочленов над конечными полями последняя теорема пре

дыдущего параграфа неверна.

Пусть Z

––

поле вычетов по модулю p, где p

––

простое число, а мно

гочлен f(x) ∈Z

[x].

Тогда справедлива (предлагавшаяся в § 2.8 в виде задачи)

Теорема 69. Уравнение f(x) = 0, f(x) ∈Z

[x], равносильно урав-

нению степени не выше p −1, другими словами, для любого мно-

гочлена f(x) ∈Z

[x] найдется многочлен степени не выше p − 1,

значения которого для любого x ∈Z

совпадают со значениями

многочлена f(x).

Д о к а з а т е л ь с т в о. Согласно теореме о делении с остатком мож

но записать, что

f(x) = (x

−x) g(x) + r(x), где deg r(x) 6 p − 1.

* Этот многочлен был открыт также английским математиком XVIII в. Э. Варингом

(Eduard Waring, 1734

–

1798).

10 Гашков

146 Глава III. Многочлены

Но x

−x = 0 для любого x ∈ Z

согласно малой теореме Ферма. Зна

чит, уравнение f(x) = 0 равносильно уравнению r(x) = 0, и справедливо

тождество f(x) = r(x).

Поэтому над полем Z

задача интерполяции осмыслена только для

многочленов степени, меньшей p. Но для таких многочленов она реша

ется точно так же, как и для бесконечных полей. В частности, из теоремы

Лагранжа вытекает следующая теорема.

Теорема 70. Для любого отображения g : Z

→Z

найдется

многочлен f(x) степени не выше p −1, реализующий эту функ-

цию, т. е. такой, что для любого x ∈Z

справедливо равенство

f(x) = g(x), причем этот многочлен определен однозначно среди

многочленов степени не выше p −1.

Д о к а з а т е л ь с т в о. Существование этого многочлена вытека

ет из теоремы Лагранжа, а единственность фактически была доказана

в последней теореме предыдущего параграфа.

Предыдущую теорему можно обобщить и на функции нескольких пе

ременных.

В частности, справедлива следующая теорема.

Теорема 71. Для любой функции g(x

, . . ., x

), переменные и зна-

чения которой принадлежат полю Z

, найдется многочлен f(x

, ...

... , x

) от n переменных степени не выше p − 1, по каждой перемен-

ной реализующий эту функцию, т. е. такой, что для любого набо-

ра (x

, ..., x

) ∈Z

справедливо равенство f(x

, ..., x

) = g(x

, ..., x

причем этот многочлен определен однозначно среди многочленов

указанного вида.

Д о к а з а т е л ь с т в о. Сначала реализуем указанными многочле

нами функции, которые всюду равны нулю, кроме одной точки. Пусть,

например, функция δ

, ..., k

, ..., x

) равна единице при (x

, ..., x

) =

= (k

, . . ., k

), а в остальных случаях равна нулю. Для каждого i = 1, ..., n

возьмем многочлен f

) степени p −1 от переменной x

, который ра

вен единице при x

= k

и нулю в остальных случаях, существование

которого доказано в предыдущей теореме. Тогда многочлен, равный их

произведению

, ..., k

, ..., x

) = f

) ... f

будет равен единице при (x

, ..., x

) = (k

, ..., k

) и нулю в остальных

случаях, т. е.

, ..., k

, ..., x

) = δ

, ..., k

, ..., x

§ 3.3. Интерполяция 147

Если же функция δ

, ..., k

, . .., x

) в точке (k

, . . ., k

) равна не еди

нице, а некоторому значению a ∈ Z

, а в остальных точках равна нулю,

то многочлен f

, ..., k

, ..., x

) после умножения на a опять будет реа

лизовывать эту функцию.

Произвольная функция g(x

, ..., x

) реализуется многочленом, рав

ным сумме всех многочленов g(k

, ..., k

) f

, ..., k

, ..., x

Действительно, для любого набора (k

, ..., k

) ∈Z

при (x

, ..., x

равном набору (k

, ..., k

), в этой сумме все слагаемые обращают

ся в нуль, и только слагаемое g(k

, ..., k

) f

, ..., k

, ..., x

) равно

g(k

, ..., k

), поэтому и вся сумма при (x

, ..., x

) = (k

, ..., k

) равна

g(k

, ..., k

). Указанная сумма является многочленом от перемен

ных x

, ..., x

степени не выше p −1 по каждой из них. Тем самым

существование реализующего функцию g(x

, ..., x

) многочлена дока

зано.

Для доказательства единственности заметим, что каждый из мно

гочленов от n переменных степени, меньшей p по каждой из них,

однозначно определяется набором коэффициентов при своих одночленах

... x

, 0 6 k

6 p − 1. Этих коэффициентов, как и одночленов, p

штук, каждый из них независимо от других принимает p значений,

поэтому число всех таких многочленов равно p

Число же различных реализуемых функций тоже равно p

, так

как каждая из них однозначно определяется набором своих p

значе

ний при

, ..., x

) = (k

, ..., k

), 0 6 k

6 p − 1.

Поэтому согласно принципу Дирихле каждая из функций реализует

ся ровно одним многочленом, иначе многочленов не хватило бы для

реализации всех функций.

Используя многочлены над полем Z

, можно дать другое доказатель

ство теоремы Вильсона: если p

––

простое число, то число (p − 1)! + 1

делится на p.

Д о к а з а т е л ь с т в о. Для p = 2 эту теорему можно проверить

непосредственно. Пусть p > 2. Согласно малой теореме Ферма много

член x

p−1

−

1 над полем Z

имеет ровно p −1 корень

2, ...,

p −1,

поэтому этот многочлен можно разложить на линейные множители

p−1

−

1 = (x −

1) (x −

2) ... (x − (p − 1)).

Подставим в полученное тождество

0 и получим, что −

1= (−1)

p−1

(

p −1)!,

а так как (p −1)

––

число четное, то (p − 1)! + 1 делится на p.

В некоторых случаях более удобной является интерполяционная

формула Ньютона.

10*

148 Глава III. Многочлены

Теорема 72. Для произвольного многочлена f(x) ∈K[x] степени n

и произвольных c

, ..., c

∈K справедлива формула

f(x) = a

+ a

(x −c

) + a

(x −c

)(x − c

) + ... + a

(x −c

) .. . (x − c

n−1

где a

= F

), i = 0, . . ., n, а последовательность функций

: {c

, ..., c

i−2

, c

, ..., c

} →K

определяется формулами F

) = f(c

), i = 0, . . ., n,

(x) =

i−1

(x) −F

i−1

)

x − c

i−1

, x ∈{c

, ..., c

i−2

, c

, ..., c

Д о к а з а т е л ь с т в о. Существование формулы указанного вида

можно доказать по индукции, при этом в качестве a

берется старший

коэффициент многочлена f(x).

Единственность коэффициентов a

также с помощью индукции выво

дится из формул

f(c

) = a

;

f(c

) = a

+ a

−c

);

f(c

) = a

+ a

−c

) + a

−c

)(c

−c

);

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

f(c

) = a

+ a

−c

) + ... + a

−c

) ... (c

−c

n−1

которые получаются из формулы для f(x) подстановками констант c

i = 0, . . ., n.

Из определения функций F

, i = 0, . .., n, также по индукции выводятся

формулы

(x) = a

+ F

(x) (x −c

(x) = a

+ a

(x −c

) + F

(x) (x −c

)(x −c

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

(x) = a

+ a

(x −c

) + ... + F

(x) (x −c

) ... (x −c

n−1

Подставляя в них константы c

, . .., c

и пользуясь доказанной един

ственностью коэффициентов a

, i = 0, .. ., n, получаем формулы

= F

), i = 0, . .., n.

Упражнение 61. Проверьте, что вычисление коэффициентов интер

поляционного многочлена по формуле Ньютона требует n

+ n вычитаний,

+ n)

2 делений.

Если коэффициенты a

, i = 0, .. ., n, в формуле Ньютона уже вы

числены и нам нужно найти значение интерполяционного многочлена

§ 3.3. Интерполяция 149

в заданной точке x, то для этого удобно использовать следующую фор

мулу (обобщающую схему Горнера, которая появится у нас дальше)

f(x) =a

(x −c

) +a

(x −c

)(x −c

) +...+a

(x −c

) ... (x −c

n−1

) =

= ((a

(x −c

n−1

) +a

n−1

)(x −c

n−2

) +...) (x −c

) +a

Упражнение 62. Проверьте, что вычисление значения интерполяци

онного многочлена по этой формуле требует n умножений и 2n сложений.

Заметным преимуществом формулы Ньютона при обработке экспе

риментальных данных является то обстоятельство, что если мы решили

добавить еще одну точку в формулу для интерполяции и соответственно

увеличить на 1 степень интерполяционного многочлена, то не надо зано

во пересчитывать все ее коэффициенты, а нужно найти только последний

(старший) коэффициент.

Но формула Ньютона не дает явно коэффициентов интерполяционно

го многочлена, как формула Лагранжа

––

Варинга.

Задачи и упражнения к § 3.3

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

чисел, если не оговорено противное.

1. Построить многочлен наименьшей степени по таблице значений

x 1 2 3 4

y 2 1 4 3

а) над полем Q; б) над полем Z

2. Пусть P(x) =

i=1

(x −a

), l

(x) =

P(x)

x − a

. Докажите, что

i=1

(x)

)

= 1.

3*. Пусть P(x) =

i=1

(x −a

). Докажите, что

i=1

′

)

= 0, при n > 1.

4*. Формуле Лагранжа можно придать следующий более элегант

ный вид

f(x)

(x − x

) ... (x − x

)

k=1

f(x

)

′

) (x − x

)

где стоящая слева дробь

––

правильная.

5. Многочлен P(x) при делении на x − a дает остаток a для всех

a = 1, 2, 3, 4. Найдите остаток от деления его на (x −1) (x −2) (x −3) (x −4).

6. Докажите, что если p(x)

––

многочлен степени n со старшим коэф

фициентом 1, то при некотором целом m ∈ [0, n] его модуль не меньше

150 Глава III. Многочлены

7. Докажите, что если p(x)

––

многочлен степени 2n и при каждом

целом k ∈ [−n, n] справедливо неравенство |p(k)|6 1, то при любом

x ∈ [−n, n] справедливо неравенство |p(x)|6 2

8. Построить многочлен наименьшей степени по таблице значений

а)

x 0 1 2 ... 9

y 1 2 4 ... 512

; б)

x 1 2 3 .. . 99

y 1 1

2 1

3 ... 1

9*. Многочлен p(x) степени n удовлетворяет равенству p(k) =

k + 1

k = 0, ..., n. Найдите p(n + 1).

10*. Многочлен p(x) степени n удовлетворяет равенству p(k) =

n+1

k = 0, ..., n. Найдите p(n + 1).

Многочлен называется целозначным, если он принимает во всех

целых точках только целые значения.

11*. Докажите, что целозначный многочлен имеет вид

+ a

x + ... + a

x(x − 1) .. . (x − n + 1)

где a

∈Z.

У к а з а н и е. Применить формулу Ньютона.

12. Докажите, что операция ∆P(x) = P(x + 1) −P(x) переводит цело

значный многочлен в целозначный.

13*. Докажите, что многочлен степени n, принимающий в n + 1 под

ряд идущих целых точках только целые значения, является целозначным.

14*. Докажите, что многочлен степени n, принимающий в точках

0, 1, 4, .. ., n

только целые значения, принимает целые значения в любой

целой точке вида m

, m ∈Z.

15*. Многочлен степени n со старшим коэффициентом 1 при целых

значениях аргумента принимает целые значения, делящиеся на m. Дока

жите, что m |n!.

16**. Многочлен степени n в любой целой точке равен n

й степени

целого числа. Докажите, что он равен n

й степени линейного многочлена

с целыми коэффициентами.

§ 3.4. Производные и кратные корни

Рассмотрим кольцо многочленов над произвольным полем F.

Определение 79. Производной многочлена

f(x) = a

+ a

n−1

+ ... + a

n−1

x + a

называется многочлен f

′

(x) = na

n−1

+ (n −1)a

n−2

+ ... + a

n−1