Многочлены. 1. Многочлены. Многочлены от одной переменной о пределен и е. Многочленом
 Скачать 309.13 Kb.
|
|
f (x) и g(x) имеют наибольший общий делитель. Рассмотрим множество D, состоящее из ненулевых многочленов s(x), представимых в виде u(x)f (x) + для некоторых u(x), v(x). Множество D, очевидно, непусто; ясно, что среди его элементов есть многочлен d(x) наименьшей степени. Этот многочлен делит любой многочлен s(x) из D. В самом деле, по теореме о делении с остатком имеем) = w(x)d(x) + r(x), deg r < deg Рассуждая от противного, предположим, что r(x) — ненулевой многочлен. Поскольку s(x) и d(x) содержатся в множестве D, имеем d(x) = u(x)f (x) + v(x)g(x), s(x) = u 1 (x)f (x) + v 1 (x)g(x) для некоторых многочленов. Используя равенство (15), получаем) = s(x) − Поэтому) = (u 1 (x) − w(x)u(x))f (x) + (v 1 (x) − Следовательно, многочлен r(x) принадлежит множеству D. Поскольку deg r < deg d, мы получили противоречие с выбором многочлена Это противоречие показывает, что r(x) — нулевой многочлен, и потому) | s(x). Заметим теперь, что f (x) = 1 · f (x) + 0 · g(x), g(x) = 0 · f (x) + 1 · g(x); отсюда следует, f (x), g(x) принадлежат множеству D. Значит, является общим делителем многочленов f (x) и Из свойства (D5) следует, что если c(x) | f (x) и c(x) | g(x), то делит Следовательно, справедливо следующее утверждение. Теорема 1.2. Пусть f (x) и g(x) — ненулевые многочлены. Среди многочленов вида f (x)u(x) + g(x)v(x), (u(x), v(x) ∈ F [x]) выберем ненулевой многочлен d(x) наименьшей возможной степени. Тогда d(x) наибольший общий делитель многочленов f (x) и g(x). 10 Наибольший общий делитель двух многочленов не является однозначно определенным. Легко убедиться в том, что если d(x) — наибольший общий делитель двух данных многочленов, то любой наибольший общий делитель этих многочленов равен αd(x), где α ∈ F, α 6= 0. В самом деле, пусть d 1 — произвольный наибольший общий делитель данных многочленов. Тогда d(x) | d 1 (x) и d 1 (x) | d(x). Из свойства (D2) вытекает, что d 1 (x) = αd(x). Таким образом, два наибольших общих делителя данных многочленов получаются один из другого умножением на отличное от нуля число. Отсюда немедленно вытекает, что для произвольных ненулевых многочленов f (x) и g(x) однозначно определен их наибольший общий делитель со старшим коэффициентом, равным единице. Этот наибольший общий делитель будет обозначаться через (f (x), Из теоремы 1.2 вытекает следующее утверждение. С лед ст в и е 1. Пусть f (x) и g(x) — ненулевые многочлены, d(x) — их наибольший общий делитель. Тогда) = u(x)f (x) + где u(x), v(x) — некоторые многочлены из F При изучении кольца Z всех целых чисел мы убедились в важности понятия взаимно простых целых чисел. Введем аналогичное понятие для многочленов. О пределен и е. Многочлены f (x) и g(x) называются взаимно простыми, если (f (x), g(x)) = Иными словами, многочлены взаимно просты, если все их общие делители имеют нулевую степень, те. являются отличными от нуля чис- лами. Из теоремы 1.2 легко выводится признак взаимной простоты много- членов. Теорема 1.3. Многочлены f (x) и g(x) взаимно просты тогда и только тогда, когда f (x)u(x) + g(x)v(x) = 1 для некоторых многочленов и Доказательство. Если многочлены f (x) и g(x) взаимно просты, то существование таких многочленов u(x) и v(x), что (x)u(x) + g(x)v(x) = сразу вытекает из следствия 1. 11 Обратно, пусть выполнено равенство (17) и d(x) = (f (x), g(x)). Тогда) делит левую часть равенства (17), а потому d(x) | 1. Следовательно) = 1, те. многочлены f (x) и g(x) взаимно просты. Отметим следующие полезные свойства взаимно простых многочленов) если (f (x), g(x)) = 1 и (f (x), h(x)) = 1, то (f (x), g(x)h(x)) = 1; (2) если f (x) | h(x), g(x) | h(x) и (f (x), g(x)) = 1, то f (x)g(x) | h(x); (3) если f (x) | g(x)h(x) и (f (x), g(x)) = 1, то f (x) | Доказательство свойств (1) - (Пусть (f (x), g(x)) = 1 и (f (x), h(x)) = 1. Тогда (x)u(x) + g(x)v(x) = 1 f (x)t(x) + h(x)s(x) = Перемножив эти равенства, получим (x)(f (x)u(x)t(x)+g(x)t(x)v(x)+h(x)u(x)s(x))+(g(x)h(x))(v(x)s(x)) = 1. Примение теоремы 1.3 показывает, что многочлены f (x) и g(x)h(x) взаимно просты. Свойство (1) доказано. Проверим свойство (2). Пусть f (x) | h(x), g(x) | h(x) и (f (x), g(x)) = Поскольку f (x) и g(x) взаимно просты, найдутся такие многочлены u(x), v(x), что f (x)u(x) + g(x)v(x) = 1, откуда (x)h(x)u(x) + g(x)h(x)v(x) = Поскольку f (x) | h(x), имеем f (x)g(x) | g(x)h(x). Аналогично, из g(x) | следует f (x)g(x) | f (x)h(x). Таким образом, f (x)g(x) делит левую часть равенства (18), а потому делит его правую часть, равную Перейдем к доказательству свойства (3). Пусть f (x) | g(x)h(x) и (x), g(x)) = 1. Как и раньше, взаимная простота многочленов f (x) и) влечет выполнение равенства (18). Поскольку f (x) | g(x)h(x), многочлен, очевидно, делит левую часть равенства (18). Следовательно, правая часть этого равенства делится на f Следует отметить, что свойства отношения делимости в кольце Z аналогичны свойствам отношения делимости в кольце F [x]. 1.5. Алгоритм Евклида В этом разделе мы изложим алгоритм Евклида, предназначенный для нахождения наибольшего общего делителя двух многочленов из кольца Пусть f (x) и g(x) — произвольные ненулевые многочлены из F Поделив первый многочлен на второй с остатком, получим (x) = u 1 (x)g(x) + r 1 (x), deg r 1 (x) < deg g(x). 12 Если deg r 1 (x) > 0 (выпонение этого неравенства означает, что r 1 (x) 6= то поделим g(x) на r 1 (x): g(x) = u 2 (x)r 1 (x) + r 2 (x), deg r 2 (x) < deg Снова, если deg r 2 (x) > 0, поделим r 1 (x) на r 2 (x): r 1 (x) = u 3 (x)r 2 (x) + r 3 (x), deg r 3 (x) < deg Продолжая этот процесс, мы получим последовательность остатков, r 2 (x), r 3 (x), . . . , r i (x), . . такую, что deg r 1 (x) > deg r 2 (x) > deg r 3 (x) > . . . deg r i (x) > . . . Нетрудно понять, что найдется номер k, для которого r k (x) 6= 0 и r k+1 (x) = 0. В самом деле, если бы указанный процесс можно было продолжать до бесконечности, тов силу неравенств (19) получилась бы бесконечная убывающая последовательность целых неотрицательных чисел. Как мы знаем, существование такой последовательности невозможно, ибо любое непустое множество целых неотрицательных чисел имеет наименьший элемент. Итак, нами получена следующая цепочка равенств (x) = u 1 (x)g(x) + r 1 (x) g(x) = u 2 (x)r 1 (x) + r 2 (x) r 1 (x) = u 3 (x)r 2 (x) + r 3 (x) . . . . . . . . . . . . . . . . . r k−2 (x) = u k (x)r k−1 (x) + r k (x) r k−1 (x) = Справедливо следующее утверждение. Теорема 1.4. Последний отличный от нуля остаток r k (x) является наибольшим общим делителем многочленов f (x) и Доказательство. Проверим сначала, что r k (x) делит многочлены (x) и g(x). Для этого достаточно пройти по равенствам (20) снизу вверх. В самом деле, из последнего равенства имеем r k (x) | r k−1 (x). Поднимаясь по цепочке равенств, последовательно получаем r k (x) | r k−2 (x), . . . , r k (x) | r 1 (x), r k (x) | g(x), r k (x) | Пусть многочлен c(x) является общим делителем многочленов f и g(x), те) и c(x) | g(x). Убедимся, что c(x) | r k (x). Для этого пройдем по равенствам (20) сверху вниз. Из первого равенства получаем. Последовательно опускаясь вниз до предпоследнего равенства, получим c(x) | r 2 (x), c(x) | r 3 (x), c(x) | r k−2 (x), c(x) | r k−1 (x), и наконец, c(x) | Следовательно, r k (x) — наибольший общий делитель f (x) и В качестве примера применим алгоритм Евклида для отыскания наибольшего общего делителя многочленов f (x) = x 5 + x 4 + 1 и g(x) = = x 4 + x 2 + 1. Последовательно имеем+ x 4 + 1 = (x + 1)(x 4 + x 2 + 1) + (−x 3 − x 2 − x) x 4 + x 2 + 1 = (−x + 1)(−x 3 − x 2 − x) + (x 2 + x + 1) −x 3 − x 2 − x = (−x)(x 2 + x + Последний отличный от нуля остаток равен x 2 + x + 1. Следовательно (x), g(x)) = x 2 + x + Напомним, что в силу теоремы 1.2 существуют такие многочлены) и v(x), что+ x + 1 = u(x)(x 5 + x 4 + 1) + v(x)(x 4 + x 2 + Эти многочлены легко находятся из равенств (21). В самом деле, выражая из второго равенства остаток отделения, получаем+ x + 1 = x 4 + x 2 + 1 − (−x + 1)(−x 3 − x 2 − В силу первого равенства имеем x 2 − x = x 5 + x 4 + 1 − (x + 1)(x 4 + x 2 + Поэтому+ x + 1 = x 4 + x 2 + 1 − (−x + 1)(x 5 + x 4 + 1 − (x + 1)(x 4 + x 2 + 1)) = = x 4 + x 2 + 1 + (x − 1)(x 5 + x 4 + 1) + (1 − x 2 )(x 4 + x 2 + 1) = = (x − 1)(x 5 + x 4 + 1) + (2 − x 2 )(x 4 + x 2 + 1). 1.6. Освобождение от иррациональности в знаменателе дроби Напомним, что в некоторых простых случаях мы умеем освобождаться от иррациональности в знаменателе. Например, если даны две дроби = 1 √ 3 − 1 , B = 1 3 √ 4 + 3 √ 2 + 1 , 14 то, умножив числитель и знаменатель первой дробина, а числитель и знаменатель второй дробина, мы получим, что = √ 3 + 1 2 , B = 3 √ 2 + Здесь для преобразований были использованы формулы для разности квадратов и разности кубов. Сейчас на примерах мы рассмотрим более общую ситуацию. Пусть дана дробь = 1 3 √ 4 + 3 √ 2 + Видно, что применение формул сокращенного умножения здесь к целине приведет. Поэтому поступим следующим образом. Рассмотрим два многочлена x 3 − 2 и x 2 + x + 3. Ниже при помощи алгоритма Евклида мы убедимся, что эти многочлены взаимно просты. Поэтому найдутся такие многочлены u(x) и v(x), что 2) + v(x)(x 2 + x + 3) = Подставив в равенство (22) вместо x число, получим + 3 √ 2 + 3) = Следовательно, умножение числителя и знаменателя дробина число) позволяет освободиться от иррациональности в знаменателе дроби C. Реализуем намеченный план решения задачи. Применяя алгоритм Евклида к многочленами, получим 2 = (x − 1)(x 2 + x + 3) + (−2x + 1), x 2 + x + 3 = µ − 1 2 x − 3 4 ¶ (−2x + 1) + 15 Отсюда находим 2 x − 3 4 ¶ (x 3 − 2) + µ − 1 2 x 2 − 1 4 x + 7 4 ¶ (x 2 + x + 3) = 15 Если теперь в равенство (23) вместо x подставить, а затем обе части умножить на 4, то получится числовое равенство 3 √ 4 − 3 √ 2 + 7)( 3 √ 4 + 3 √ 2 + 3) = 15. 15 Отсюда вытекает, что в результате умножения числителя и знаменателя дробина, получим = − 2 3 √ 4 + 3 √ 2 − 7 В качестве второго примера освободимся от иррациональности в знаменателе дроби = 1 4 √ 9 + 4 √ 3 + Для этого алгоритм Евклида нужно применить к многочленами. Последовательно имеем 3 = (x 2 − x)(x 2 + x + 1) + (x − 3), x 2 + x + 1 = (x + 4)(x − 3) + Из этих равенств получаем + 4)(x 4 − 3) + (x 3 + 3x 2 − 4x + 1)(x 2 + x + 1) = Подставив в равенство (24) число вместо x получаем числовое равенство Следовательно, после освобождения от иррациональности в знаменателе дроби D получим = 4 √ 27 + 3 4 √ 9 − 4 4 √ 3 + 1 13 . 1.7. Корни многочлена Пусть f (x) = a 0 x n + a 1 x n−1 + a 2 x n−2 + . . . + a n−1 x + a n — произвольный многочлен над полем F . Для произвольного c ∈ F выражение (c) = a 0 c n + a 1 c n−1 + a 2 c n−2 + . . . + a n−1 c + является элементом поля F и называется значением многочлена f (x) при = Теорема 1.5. Значение многочлена f (x) при x = c совпадает с остатком отделения) на x − Доказательство. По теореме о делении с остатком имеем f (x) = (x − c)u(x) + r. Подставив в это равенство вместо x элемент c, получим (c) = Если f (c) = 0, то c называют корнем многочлена f Из теоремы 1.5 легко получить следующее утверждение Следствие. Элемент c ∈ F является корнем многочлена f тогда и только тогда, когда x − c делит f В самом деле, x − c делит f (x) тогда и только тогда, когда остаток отделения) на x − c равен нулю. Это утверждение часто называют теоремой Безу. Заметим, что если c — корень многочлена |