Розподіл багаточленів. Алгоритм Евкліда. Знаходження найбільшого спільного дільника багаточленів За допомогою алгоритму евкліда знайти нод багаточленів

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

Щоб спростити багаточлен, наведіть такі доданки. приклад. Спростіть вираз \ Знайдіть одночлени з однаковою літерною частиною. Складіть їх. Запишіть отриманий вираз: Ви спростили багаточлен.

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

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

Де можна вирішити рівняння багаточлену онлайн?

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

Визначення. Якщо кожен із двох многочленів ділиться без залишку на третій, він називається загальним дільником перших двох.

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

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

Приклад 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). Маємо:

Відповідь:
.

ОСНОВНІ ВІДОМОСТІ З ТЕОРІЇ

Визначення 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крок.

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

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)) = 7x2 + 7.

Оскільки подільність у кільці багаточленів визначена з точністю до асоційованості ( Властивість 2.11.) , то як НОД можна взяти не 7x 2 + 7, а ( 7x2+7) = x2+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 многочленів потрібно довести наступну теорему.

Алгоритм Евкліда для багаточленів.Алгоритм Евкліда дозволяє знайти загальний дільник двох многочленов, тобто. багаточлен най більшою мірою, на який діляться без залишку обидва дані багаточлена.
Алгоритм заснований на тому факті, що для будь-яких двох багаточленів від одного змінного, 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 і буде найбільшим спільним дільником вихідної пари багаточленів 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, отриманих при розподілі даних многочленів.

Отже, ;

Зауважимо, що й найбільший загальний дільник даних многочленів знайдено, то, помножуючи його за будь-яке число, не дорівнює нулю, ми отримаємо найбільший дільник цих многочленов. Ця обставина дозволяє спрощувати обчислення в алгоритмі Евкліда. А саме, перед черговим розподілом ділене або дільник можна множити на числа, підібрані спеціальним чином так, щоб коефіцієнт першого доданка в приватному був цілим числом. Як показано вище, множення ділимого та дільника призведе до відповідної зміни приватного залишку, але такої, що в результаті НОД даних багаточленів помножиться на деяке нуль число, що допустимо.