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

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

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

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

Пример 40 Найти НОД многочленови
.

Решение. Разложим оба многочлена на множители:

Из разложения видно, что искомым НОДом будет многочлен (х – 1).

Пример 41 Найти НОД многочленов
и
.

Решение. Разложим оба многочлена на множители.

Для многочлена
х х – 1) по схеме Горнера.

Для многочлена
возможными рациональными корнями будут числа1,2,3 и6. С помощью подстановки убеждаемся, чтох = 1 является корнем. Разделим многочлен на (х – 1) по схеме Горнера.

Следовательно, , где разложение квадратного трехчлена
было произведено по теореме Виета.

Сравнив разложение многочленов на множители, находим, что искомым НОДом будет многочлен (х – 1)(х – 2).

Аналогично можно находить и НОД для нескольких многочленов.

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

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

Рассмотрим многочлены, использовавшиеся в двух предыдущих примерах.

Пример 42 Найти НОД многочленов
и
.

Решение. Разделим
на
«уголком»:

x

Теперь разделим делитель
на остатокх – 1:

x + 1

Так как последнее деление произошло без остатка, то НОДом будет х – 1, т. е. многочлен, использовавшийся в качестве делителя при этом делении.

Пример 43 Найти НОД многочленов
и
.

Решение . Для нахождения НОД воспользуемся алгоритмом Евклида. Разделим
на
«уголком»:

1

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

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

и будет искомым НОДом.

1. Дробно-рациональные функции

Определения и утверждения к 2.5 можно найти в .

Дробно-рациональной функцией с действительными коэффициентами называется выражение вида , где
и
‑ многочлены.

Дробно-рациональная функция (в дальнейшем будем называть ее «дробь») называется правильной , если степень многочлена, стоящего в числителе, строго меньше степени многочлена, стоящего в знаменателе. В противном случае она называетсянеправильной .

Алгоритм приведения неправильной дроби к правильной называется «выделением целой части».

Пример 44 Выделить целую часть дроби:
.

Решение. Для того, чтобы выделить целую часть дроби необходимо разделить числитель дроби на ее знаменатель. Разделим числитель данной дроби на ее знаменатель «уголком»:

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

=
. Получившаяся в результате дробь
является правильной.

Дробь вида
называется простейшей, если φ(x ) – неприводимый многочлен, а степень
меньше степени φ(x ).

Замечание. Обратите внимание, что сравниваются степени числителя и неприводимого многочлена в знаменателе (без учета степени α).

Для дробей с действительными коэффициентами существует 4 вида простейших дробей:

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

Алгоритм разложения дроби на простейшие:

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

Раскладываем знаменатель правильной дроби на множители.

Записываем правильную дробь в виде суммы простейших дробей с неопределенными коэффициентами.

Приводим к общему знаменателю сумму дробей в правой части.

Находим неопределенные коэффициенты:

Либо приравнивая коэффициенты при одинаковых степенях у левого и правого приведенных числителей;

Либо подставляя конкретные (как правило корни общего их знаменателя) значения x .

Записываем ответ с учетом целой части дроби.

Пример 45 Разложить на простейшие
.

Решение. Так как данная дробно-рациональная функция является неправильной, выделим целую часть:

1

= 1 +
.

Разложим получившуюся дробь
на простейшие. Вначале разложим на множители знаменатель. Для этого найдем его корни по стандартной формуле:

Запишем разложение дробно-рациональной функции на простейшие, используя неопределенные коэффициенты:

Приведем правую часть равенства к общему знаменателю:

Составляем систему, приравнивая коэффициенты при одинаковых степенях в числителях левой и правой дробей:

Ответ:
.

Пример 46 Разложить на простейшие
.

Решение. Так как данная дробь является правильной (т. е. степень числителя меньше степени знаменателя), выделять целую часть не надо. Разложим знаменатель дроби на множители:.

Запишем разложение данной дроби на простейшие, используя неопределенные коэффициенты:

По утверждению, знаменатели простейших дробей должны бытьвсевозможными делителями знаменателя дроби:

. (2.2) Можно было бы составить систему уравнений, приравняв числители левой и правой дробей, но в данном примере вычисления будут слишком громоздки. Упростить их поможет следующий прием: подставим в числители по очереди корни знаменателя.

При х = 1:

Прих = ‑1:

Теперь для определения оставшихся коэффициентов А иС достаточно будет приравнять коэффициенты при старшей степени и свободные члены. Их можно найти, не раскрывая скобок:

В левой части первого уравнения стоит 0, так как в числителе левой дроби в (2.2) нет слагаемого с, а в правой дроби у слагаемого скоэффициентA + C . В левой части второго уравнения стоит 0, так как в числителе левой дроби в (2.2) свободный член равен нулю, а у числителя правой дроби в (2.2) свободный член равен (‑A + B + C + D ). Имеем:

Ответ:
.

Алгоритм Евклида для многочленов. Алгоритм Евклида позволяет найти наибольший общий делитель двух многочленов, т.е. многочлен наибольшей степени, на который делятся без остатка оба данных многочлена.
Алгоритм основан на том факте, что для любых двух многочленов от одного переменного, f (x ) и g (x ), существуют такие многочлены q (x ) и r (x ) , называемые соответственно частное и остаток, что

f (x ) = g (x )∙q (x ) + r (x ), (*)

при этом степень остатка меньше степени делителя, многочлена g (x ), и, кроме того, по данным многочленам f (x ) и g (x ) частное и остаток находятся однозначно. Если в равенстве (*) остаток r (x ) равен нулевому многочлену (нулю), то говорят, что многочлен f (x ) делится на g (x ) без остатка.
Алгоритм состоит из последовательного деления с остатком сначала первого данного многочлена, f (x ), на второй, g (x ):

f (x ) = g (x )∙q 1 (x ) + r 1 (x ), (1)

затем, если r 1 (x ) ≠ 0, – второго данного многочлена, g (x ), на первый остаток – на многочлен r 1 (x ):

g (x ) = r 1 (x )∙q 2 (x ) + r 2 (x ), (2)

r 1 (x ) = r 2 (x )∙q 3 (x ) + r 3 (x ), (3)

затем, если r 3 (x ) ≠ 0, – второго остатка на третий:

r 2 (x ) = r 3 (x )∙q 4 (x ) + r 4 (x ), (4)

и т.д. Поскольку на каждом этапе степень очередного остатка уменьшается, процесс не может продолжаться бесконечно, так что на некотором этапе мы обязательно придем к ситуации, когда очередной, n + 1-й остаток r n + 1 равен нулю:

r n –2 (x ) = r n –1 (x )∙ q n (x ) + r n (x ),	(n )
r n –1 (x ) = r n (x )∙ q n +1 (x ) + r n +1 (x ),	(n +1)
r n +1 (x ) = 0.	(n +2)

Тогда последний не равный нулю остаток r n и будет наибольшим общим делителем исходной пары многочленов f (x ) и g (x ).
Действительно, если в силу равенства (n + 2) подставить 0 вместо r n + 1 (x ) в равенство (n + 1), затем – полученное равенство r n – 1 (x ) = r n (x )∙q n + 1 (x ) вместо r n – 1 (x ) – в равенство (n ), получится, что r n – 2 (x ) = r n (x )∙q n + 1 (x ) q n (x ) + r n (x ), т.е. r n – 2 (x ) = r n (x )(q n + 1 (x ) q n (x ) + 1), и т.д. В равенстве (2) после подстановки получим, что g (x ) = r n (x )∙Q (x ), и, наконец, из равенства (1) – что f (x ) = r n (x )∙S (x ), где Q и S – некоторые многочлены. Таким образом, r n (x ) – общий делитель двух исходных многочленов, а то, что он наибольший (т.е. наибольшей возможной степени), следует из процедуры алгоритма.
Если наибольший общий делитель двух многочленов не содержит переменную (т.е. является числом), исходные многочлены f (x ) и g (x ) называются взаимно-простыми .

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

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

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

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

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

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

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

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

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

Пример №1

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

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

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

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

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

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

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

Следствие

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

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

Пример №2

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

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

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

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

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

ОСНОВНЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ

Определение 4.1.

Многочлен j(x) из P[x] называется общим делителем многочленов g(x) и f(x) из P[x], если f(x) и g(x) делятся без остатка на j(x).

Пример 4.1. Даны два многочлена: (x) g(x) = x 4 − 3x 3 − 4x 2 + 2х + 2 Î R[x]. Общие делители этих многочленов: j 1 (x) = x 3 − 4x 2 + 2 = Î R[x], j 2 (x) = (x 2 − 2x − 2) Î R[x], j 3 (x) = (x − 1) Î R[x], j 4 (x) = 1 Î R[x]. (Проверьте!)

Определение 4.2.

Наибольшим общим делителем отличных от нуля многочленов f(x) и g(x) из P[x] называется такой многочлен d(x) из P[x], который является их общим делителем и сам делится на любой другой общий делитель этих многочленов.

Пример 4.2. Для многочленов из примера 4.1. f(x) = x 4 − 4x 3 + 3x 2 + 2x − 6 Î R[x], g(x) = x 4 − 3x 3 − 4x 2 + 2х + 2 Î R[x] наибольшим общим делителем будет многочлен d(x) = j 1 (x) = x 3 − 4x 2 + 2 Î R[x], т. к. этот о многочлен d(x) делится на все другие их общие делители j 2 (x), j 3 (x) , j 4 (x) .

Наибольший общий делитель (НОД) обозначается символом:

d(x) = (f(x) , g(x) ).

Наибольший общий делитель существует для любых двух многочленов f(x),g(x) Î P[x] (g(x) ¹ 0). Его существование определяет алгоритм Евклида , который заключается в следующем.

Делим f(x) на g(x) . Остаток и частное, полученные при делении, обозначим r 1 (x) и q 1 (x). Затем, если r 1 (x) ¹ 0, делим g(x) на r 1 (x), получаем остаток r 2 (x) и частное q 2 (x) и т.д. Степени получающихся остатков r 1 (x), r 2 (x), … будут убывать. Но последовательность целых неотрицательных чисел ограничена снизу числом 0. Следовательно, процесс деления будет конечным, и мы придем к остатку r k (x), на который нацело разделится предыдущий остаток r k – 1 (x). Весь процесс деления можно записать следующим образом:

f(x) = g(x) × q 1 (x) + r 1 (x), deg r 1 (x) < deg g(x);

g(x) = r 1 (x) × q 2 (x) + r 2 (x), deg r 2 (x) < deg r 1 (x);

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

r k – 2 (x) = r k – 1 (x) × q k (x) + r k (x), deg r k (x) < deg r k – 1 (x);

r k – 1 (x) = r k (x) × q k +1 (x). (*)

Докажем, что r k (x) будет наибольшим общим делителем многочленов f(x) и g(x).

1) Покажем, что r k (x) является общим делителем данных многочленов.

Обратимся к предпоследнему равенству:

r k –-2 (x) = r k –-1 (x) × q k (x) + r k (x), или r k –-2 (x) = r k (x) × q k +1 (x) × q k (x) + r k (x).

Его правая часть делится на r k (x). Следовательно, левая часть также делится на r k (x), т.е. r k –-2 (x) делится на r k (x).

r k –- 3 (x) = r k –- 2 (x) × q k – 1 (x) + r k –- 1 (x).

Здесь r k –- 1 (x) и r k –- 2 (x) делятся на r k (x), отсюда следует, что и сумма в правой части равенства делится на r k (x). Значит и левая часть равенства делится на r k (x), т.е. r k –- 3 (x) делится на r k (x). Продвигаясь таким образом последовательно вверх, мы получим, что многочлены f(x) и g(x) делятся на r k (x). Тем самым мы показали, что r k (x) является общим делителем данных многочленов (определение 4.1.) .

2) Покажем, что r k (x) делится на любой другой общий делитель j(x) многочленов f(x) и g(x), то есть является наибольшим общим делителем этих многочленов.

Обратимся к первому равенству: f(x) = g(x) × q 1 (x) + r 1 (x).

Пусть d(x) – некоторый общий делитель f(x) и g(x) . Тогда по свойствам делимости разность f(x) – g(x) × q 1 (x) также делится на d (x), то есть левая часть равенства f(x) – g(x) × q 1 (x) = r 1 (x) делится на d (x). Тогда и r 1 (x) будет делиться на d (x). Продолжая рассуждения аналогичным образом, последовательно опускаясь по равенствам вниз, получим, что r k (x) делится на d (x). Тогда, согласно определению 4.2. r k (x) будет являться наибольшим общим делителем многочленов f(x) и g(x) : d(x) = (f(x) , g(x) ) = r k (x).

Наибольший общий делитель многочленов f(x) и g(x) является единственным с точностью до множителя - многочлена нулевой степени, или, можно сказать, с точностью до ассоциированности (определение 2.2.).

Таким образом, нами доказана теорема:

Теорема 4.1. /Алгоритм Эвклида/.

Если для многочленов f(x),g(x) Î P[x] (g(x) ¹ 0) верна система равенств и неравенств (*), то последний, не равный нулю остаток будет наибольшим общим делителем этих многочленов.

Пример 4.3. Найти наибольший общий делитель многочленов

f(x) = x 4 + x 3 +2x 2 + x + 1 и g(x) = x 3 –2x 2 + x –2.

Решение.

1шаг.2шаг.

x 4 + x 3 +2x 2 + x + 1	x 3 –2x 2 + x –2		x 3 –2x 2 + x –2	7x 2 + 7
– (x 4 –2x 3 + x 2 – 2x)	x+3 = q 1 (x)	– (x 3 + x)	1/7x.–2/7 = q 2 (x)
3x 3 + x 2 + 3x + 1 – (3x 3 –6x 2 + 3x –6)		–2x 2 –2 –(–2x 2 –2)
7x 2 + 7 = r 1 (x)		0 = r 2 (x)

Запишем шаги деления в виде системы равенств и неравенств, как в (*) :

f(x) = g(x) × q 1 (x) + r 1 (x), deg r 1 (x) < deg g(x);

g(x) = r 1 (x) × q 2 (x).

Согласно Теореме 4.1. /Алгоритм Эвклида/ последний, не равный нулю остаток r 1 (x) = 7x 2 + 7 будет наибольшим общим делителем d(x) этих многочленов:

(f(x) , g(x) ) = 7x 2 + 7.

Поскольку делимость в кольце многочленов определена с точностью до ассоциированности (Свойство 2.11 .) , то в качестве НОД можно взять не 7x 2 + 7, а (7x 2 + 7) = x 2 + 1.

Определение 4.3.

Наибольший общий делитель со старшим коэффициентом 1 будем называть нормированным наибольшим общим делителем .

Пример 4.4. В примере 4.2. был найден наибольший общий делитель d(x) = (f(x) , g(x) ) = 7x 2 + 7 многочленов f(x) = x 4 + x 3 +2x 2 + x + 1 и g(x) = x 3 –2x 2 + x –2. Заменив его на ассоциированный с ним многочлен d 1 (x) = x 2 + 1, получим нормированный наибольший общий делитель этих многочленов(f(x) , g(x) ) = x 2 + 1.

Замечание. Применяя алгоритм Евклида при поиске наибольшего общего делителя двух многочленов, можно сделать следующее заключение. Наибольший общий делитель многочленов f(x) и g(x) не зависит от того, будем ли мы рассматривать f(x) и g(x) над полем P или над его расширением P’.

Определение 4.4.

Наибольшим общим делителем многочленов f 1 (x), f 2 (x), f 3 (x),… f n (x) Î P[x] называется такой многочлен d(x) Î P[x], который является их общим делителем и сам делится на любой другой общий делитель этих многочленов.

Поскольку алгоритм Евклида пригоден лишь для поиска наибольшего общего делителя двух многочленов, то для поиска наибольшего общего делителя n многочленов требуется доказать следующую теорему.

Применение уравнений широко распространено в нашей жизни. Они используются во многих расчетах, строительстве сооружений и даже спорте. Уравнения человек использовал еще в древности и с тех пор их применение только возрастает. Многочлен представляет собой алгебраическую сумму произведений чисел, переменных и их степеней. Преобразование многочленов обычно включает два вида задач. Выражение требуется либо упростить, либо разложить на множители, т.е. представить его в виде произведения двух или нескольких многочленов или одночлена и многочлена.

Чтобы упростить многочлен, приведите подобные слагаемые. Пример. Упростите выражение \ Найдите одночлены с одинаковой буквенной частью. Сложите их. Запишите полученное выражение: \ Вы упростили многочлен.

В задачах, которые требуют разложения многочлена на множители, определите общий множитель данного выражения. Для этого сначала вынесите за скобки те переменные, которые входят в состав всех членов выражения. Причем эти переменные должны иметь наименьший показатель. Затем вычислите наибольший общий делитель каждого из коэффициентов многочлена. Модуль полученного числа будет коэффициентом общего множителя.

Пример. Разложите на множители многочлен \ Вынесите за скобки \ т.к. переменная m входит в каждый член данного выражения и ее наименьший показатель равен двум. Вычислите коэффициент общего множителя. Он равен пяти. Таким образом, общий множитель данного выражения равен \ Отсюда: \

Где можно решить уравнение многочлена онлайн?

Решить уравнение вы можете на нашем сайте https://сайт. Бесплатный онлайн решатель позволит решить уравнение онлайн любой сложности за считанные секунды. Все, что вам необходимо сделать - это просто ввести свои данные в решателе. Так же вы можете посмотреть видео инструкцию и узнать, как решить уравнение на нашем сайте. А если у вас остались вопросы, то вы можете задать их в нашей групе Вконтакте http://vk.com/pocketteacher. Вступайте в нашу группу, мы всегда рады помочь вам.