Деление многочленов. Алгоритм евклида деление многочленов

Вид материала

Подобный материал:

ДЕЛЕНИЕ МНОГОЧЛЕНОВ. АЛГОРИТМ ЕВКЛИДА

§1. Деление многочленов

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

Результатом деления является единственная пара многочленов – частное и остаток, которые должны удовлетворять равенству:

< делимое > = < делитель >  < частное > + < остаток >.

Если многочлен степени n P_n(x) является делимым,

многочлен степени m R_k(x)является делителем (n  m),

многочлен Q_n_–_m(x) – частное. Степень этого многочлена равна раз-ности степеней делимого и делителя,

а многочлен степени k R_k(x) является остатком (k < m).

То равенство

P_n(x) = F_m(x) Q_{n – m}(x) + R_k(x) (1.1)

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

Ещё раз отметим, что степень остатка k должна быть меньше степени делителя m. Назначение остатка – дополнить произведение многочленов F_m(x) и Q_n_–_m(x) до многочлена, равного делимому.

Если произведение многочленов F_m(x) Q_n_–_m(x) дает многочлен, равный делимому, то остаток R = 0. В этом случае говорят, что деление производится без остатка.

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

Пусть требуется разделить многочлен (5х⁵ + х³ + 1) на многочлен (х³ + 2).

1. Разделим старший член делимого 5х⁵ на старший член делителя х³:

.

Ниже будет показано, что так находится первый член частного.

2. На очередное (поначалу первое) слагаемое частного умножается делитель и это произведение вычитается из делимого:

5х⁵ + х³ + 1 – 5х²(х³ + 2) = х³ – 10х² + 1.

3. Делимое можно представить в виде

5х⁵ + х³ + 1 = 5х²(х³ + 2) + (х³ – 10х² + 1). (1.2)

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

Старший член разности х³ делится на старший член делителя х³:

.

Ниже будет показано, что таким образом находится второе слагаемое в частном.

2. На очередное (теперь уже, второе) слагаемое частного умножается делитель и это произведение вычитается из последней разности

х³ – 10х² + 1 – 1(х³ + 2) = – 10х² – 1.

3. Тогда, последнюю разность можно представить в виде

х³ – 10х² + 1 = 1(х³ + 2) + (–10х² + 1). (1.3)

Если степень очередной разности окажется меньше степени делителя (как при повторе в действии (2)), то деление завершено с остатком, равным последней разности.

Для подтверждения того, что частное является суммой (5х² + 1), подставим в равенство (1.2) результат преобразования многочлена х³ – 10х² + 1 (см.(1.3)): 5х⁵ + х³ + 1 = 5х²(х³ + 2) + 1(х³ + 2) + (– 10х² – 1). Тогда, после вынесения общего множителя (х³ + 2) за скобки, получим окончательно

5х⁵ + х³ + 1 = (х³ + 2)(5х² + 1) + (– 10х² – 1).

Что, в соответствии с равенством (1.1), следует рассматривать как результат деления многочлена (5х⁵ + х³ + 1) на многочлен (х³ + 2) с частным (5х² + 1) и остатком (– 10х² – 1).

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

– –
5х⁵ + 0х⁴ + х³ + 0х² + 0х + 1 х³ + 2

5х⁵ +10х² 5х² + 1

– –
х³ –10х² + 0х + 1

х³ + 2

–10х² + 0х – 1

Мы видим, что деление многочленов сводится к последовательному повторению действий:

в начале алгоритма старший член делимого, в последующем, старший член очередной разности делится на старший член делителя;
результат деления дает очередное слагаемое в частном, на которое умножается делитель. Полученное произведение записывается под делимым или очередной разностью;
из верхнего многочлена вычитается нижний многочлен и, если степень полученной разности больше или равна степени делителя, то с нею повторяются действия 1, 2, 3.

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

Пример №1

6
–

х³ + х² – 3х – 2 2х² – х – 1

6х³  3х²  3х 3х + 2

–
4х² + 0х – 2

4х²  2х  2

2х

Таким образом, 6х³ + х² – 3х – 2 = (2х² – х – 1)( 3х + 2) + 2х.

Пример №2

–
a⁵ + b⁵ a + b

a⁵

a⁴b a⁴ –a³b + a²b² – ab³ + b⁴

– a⁴b + b⁵

 a⁴b  a³b²

–
a³b² + b⁵

a³b²

a²b³

– a²b³ + b⁵

 a²b³  ab⁴

+ ab⁴ + b⁵

– ab⁴

b⁵

0

Таким образом, a⁵ + b⁵ = (a + b)(a⁴ –a³b + a²b² – ab³ + b⁴).

Пример №3

–
х⁵ – у⁵ х – у

х⁵

х⁴у х⁴ + х³у + х²у² + ху³ + у⁴

–
х⁴у – у⁵

х⁴у  х³у²

–
х³у² – у⁵

х³у²  х²у³

–
х²у³ – у⁵

х²у³  ху⁴

–
ху⁴ – у⁵

ху⁴ – у⁵

0

Таким образом, х⁵ – у⁵ = (х – у)( х⁴ + х³у + х²у² + ху³ + у⁴).

Обобщением результатов, полученных в примерах 2 и 3, являются две формулы сокращенного умножения:

(х + а)(х²ⁿ – х²ⁿ^–1a + х²ⁿ^–2a² – … + a²ⁿ) = х²ⁿ⁺¹+ a^{2n + 1};

(х – a)(х²ⁿ + х^2n–1a + х^2n–2a² + … + a²ⁿ) = х²ⁿ⁺¹– a^{2n + 1}, где nN.

Упражнения

Выполнить действия

1. (– 2х⁵ + х⁴ + 2х³ – 4х² + 2х + 4) : (х³ + 2).

Ответ: – 2х² + х +2 – частное, 0 – остаток.

2. (х⁴ – 3х² + 3х + 2) : (х – 1).

Ответ: х³ + х² – 2х + 1– частное, 3 – остаток.

3. (х² + х⁵ + х³ + 1) : (1 + х + х²).

Ответ: х³ – х² + х + 1– частное, 2х – остаток.

4. (х⁴ + х²у² + у⁴) : (х² + ху + у²).

Ответ: х² – ху + у²– частное, 0 – остаток.

5. (a³ + b³ + c³ – 3abc) : (a + b + c).

Ответ: a² – (b + c)a + (b² – bc + c²) – частное, 0 – остаток.

§2. Нахождение наибольшего общего делителя двух многочленов

1. Алгоритм Евклида

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

Наибольшим общим делителем (НОД) двух многочленов называется их общий делитель наибольшей степени.

Заметим, что любое число неравное нулю является общим делителем двух любых многочленов. Поэтому, всякое неравное нулю число называется тривиальным общим делителем данных многочленов.

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

Алгоритм Евклида реализуется в виде последовательности делений. В первом делении многочлен большей степени рассматривается как делимое, а меньшей – как делитель. Если многочлены, для которых находится НОД, имеют одинаковые степени, то делимое и делитель выбираются произвольно.

Если при очередном делении многочлен в остатке имеет степень больше или равную 1, то делитель становится делимым, а остаток – делителем.

Если при очередном делении многочленов получен остаток, равный нулю, то НОД данных многочленов найден. Им является делитель при последнем делении.

Если же при очередном делении многочленов остаток оказывается числом неравным нулю, то для данных многочленов не существует НОД помимо тривиальных.

Пример №1

Сократить дробь

.

Решение

Найдем НОД данных многочленов, применяя алгоритм Евклида

1
– – – –

) х³ + 6х² + 11х + 6 х³ + 7х² + 14х + 8

х³ + 7х² + 14х + 8 1

– х² – 3х – 2

2

– – –
) х³ + 7х² + 14х + 8 – х² – 3х – 2

х³ + 3х² + 2х – х – 4

– – –
4х² + 12х + 8

4х² + 12х + 8

0

Следовательно, многочлен (– х² – 3х – 2) является НОД числителя и знамена-теля данной дроби. Результат деления знаменателя на этот многочлен известен. Найдем результат деления числителя.

х³ + 6х² + 11х + 6 – х² – 3х – 2

х³ + 3х² + 2х – х – 3

– – –
3х² + 9х + 6

3х² + 9х + 6

0

Т
– – –
аким образом,

.

Ответ:

.

2. Возможности упрощения вычислений НОД в алгоритме Евклида

Теорема

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

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

Пусть P – делимое, F – делитель, Q – частное, R – остаток. Тогда,

P = FQ + R.

Умножая данное тождество на число   0, получим

P = F(Q) + R,

где многочлен P можно рассматривать как делимое, а многочлены Q и R – как частное и остаток, полученные при делении многочлена P на многочлен F. Таким образом, при умножении делимого на число   0, частное и остаток так же умножаются на , ч.т.д

Следствие

Умножение делителя на число   0 можно рассматривать как умножение делимого на число

.

Следовательно, при умножении делителя на число   0 частное и остаток умножается на

.

Пример №2

Найти частное Q и остаток R при делении многочленов

Решение

Для перехода в делимом и делителе к целым коэффициентам умножим делимое на 6, что приведет к умножению на 6 искомого частного Q и остатка R. После чего, умножим делитель на 5, что приведет к умножению частного 6Q и остатка 6R на

. В итоге, частное и остаток, полученные при делении многочленов с целыми коэффициентами, в

раз будут отличаться от искомых значений частного Q и остатка R, полученных при делении данных многочленов.

–
12у⁴ – 22ху³ + 18х²у² – 11х³у + 3х⁴ 2у² – 3ху + 5х²

12у⁴  18ху³

30х²у² 6у² – 2ху – 9х² =

– 4ху³ – 12х²у² – 11х³у + 3х⁴

 4ху³

6х²у²  10х³у

– 18х²у² – х³у + 3х⁴

 18х²у²

27х³у  45х⁴

– 28х³у + 48х⁴ =

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

;

.

Ответ:

.

Заметим, что если наибольший общий делитель данных многочленов найден, то, умножая его на любое число, не равное нулю, мы также получим наибольший делитель этих многочленов. Это обстоятельство дает возможность упрощать вычисления в алгоритме Евклида. А именно, перед очередным делением делимое или делитель можно умножать на числа, подобранные специальным образом так, чтобы коэффициент первого слагаемого в частном был числом целым. Как показано выше, умножение делимого и делителя приведет к соответствующему изменению частного остатка, но такому, что в итоге НОД данных многочленов умножится на некоторое равное нулю число, что допустимо.

Пример №3

Сократить дробь

.

Решение

Применяя алгоритм Евклида, получим

1

–
) х⁴ + 3х³ + 3х² + 3х + 2 х⁴ + х³ – 3х² + 4

х⁴

х³  3х²

4 1

2х³ + 6х² + 3х – 2

2

) 2(х⁴ + х³ – 3х² + 4) = 2х⁴ + 2х³ – 6х² + 8 2х³ + 6х² + 3х – 2

2х⁴

6х³

3х²  2х х – 2

– 4х³ – 9х² + 2х + 8

 4х³ 12х²  6х

4

3х² + 8х + 4

3
–

–
) 3(2х³ + 6х² + 3х – 2) = 6х³ + 18х² + 9х – 6 3х² + 8х + 4

6х³

16х²

8х 2х +

–
2х² + х – 6

–
) 3х² + 8х + 4 х + 2

3х²

6х 3х + 2

–
2х + 4

2х + 4

0

Следовательно, многочлен (х + 2) является НОД числителя и знаменателя данной дроби. При этом,

–
х⁴ + 3х³ + 3х² + 3х + 2 х + 2

х⁴

2х³ х³ + х² + х + 1

–
х³ + 3х² + 3х + 2

х³

2х²

х² + 3х + 2

х²

2х

х + 2

2

0

х

–

⁴ + х³ – 3х² + 4 х + 2

х

⁴ +2х³ х³ – х² – х + 2

– х³ – 3х² + 4

 х³  2х²

– х² + 4

 х²  2х

–
2х  4

2х + 4

0

Таким образом,

Ответ:

Упражнения

Сократить дроби

1.

Ответ:

.

2.

Ответ:

§3. Нахождение НОД двух натуральных чисел

Число является частным случаем многочлена. Поэтому, алгоритм нахождения НОД двух натуральных чисел не отличается от рассмотренного алгоритма определения НОД двух многочленов. При этом, большее из заданных чисел становится делимым, а меньшее – делителем. И, подобно тому, как признаком отсутствия НОД двух многочленов является появление остатка в виде числа неравного нулю – тривиального делителя любого многочлена, признаком отсутствия НОД двух натуральных чисел является появление 1 в остатке – тривиального делителя любого натурального числа.

Пример №1

Найти НОД двух чисел 323 и 247

Решение

1

) 323 247 2) 247 76 3) 76 19

247 1 228 3 76 4

76 19 0

Ответ: НОД _{323; 247} = 19.

Пример №2

Найти НОД двух чисел 323 и 107

Решение

1

) 323 107 2) 107 2

321 3 100 53

2 7

6

1 не существует

Ответ: НОД _{323; 107} не существует.

Упражнения

Blog

Деление многочленов. Алгоритм евклида деление многочленов