Поделба на полиноми. Евклидовиот алгоритам.

5x5 +10x2 5x2 + 1

X3 + 7x2 + 14x + 8 1

– x2 – 3x – 2

X3 + 3x2 + 2x – x – 4

3x2 + 9x + 6

3x2 + 9x + 6

12у4 ± 18ху3 30x2y2 6y2 – 2xy – 9x2 =

– 4x3 – 12x2y2 – 11x3y + 3x4

± 4ху3 6х2у2 ± 10х3у

– 18x2y2 – x3y + 3x4

± 18х2у2 27х3у ± 45х4

– 28х3у + 48х4 = големина на фонт:14.0pt;висина на линија:150%">Оттука, ;

Одговор: , .

Забележете дека ако се најде најголемиот заеднички делител на овие полиноми, тогаш со множење со кој било број што не е еднаков на нула, ќе го добиеме и најголемиот делител на овие полиноми. Оваа околност овозможува поедноставување на пресметките во Евклидовиот алгоритам. Имено, пред следното делење, дивидендата или делителот може да се помножат со броеви избрани на посебен начин така што коефициентот на првиот член во количникот е цел број. Како што е прикажано погоре, множењето на дивидендата и делителот ќе доведе до соодветна промена во делумниот остаток, но таква што, како резултат на тоа, GCD на овие полиноми ќе се помножи со некој број еднаков на нула, што е прифатливо.

Пример бр. 3

Намали дропка .

Решение

Применувајќи го Евклидов алгоритам, добиваме

X4 x3 ± 3x2 големина на фонт: 14,0 pt; line-height:150%"> 4 1

2x3 + 6x2 + 3x – 2

големина на фонт: 14,0 pt; линија-висина:150%">2) 2(x4 + x3 - 3x2 + 4) = 2x4 + 2x3 - 6x2 + 8 2x3 + 6x2 + 3x - 2

2x4 6x3 3x2 ± 2x x – 2

– 4x3 – 9x2 + 2x + 8

± 4х3 ± 12х2 ± 6х големина на фонт: 14,0 pt; линија-висина:150%">4

3x2 + 8x + 4

6x3 големина на фонт:14.0pt">16x2 големина на фонт:14.0pt">8x 2x +

Евклидов алгоритам за полиноми.Евклидов алгоритам ви овозможува да го пронајдете најголемиот заеднички делител на два полиноми, т.е. полином од највисок степен со кој двата дадени полиноми се делат без остаток.
Алгоритмот се заснова на фактот дека за кои било два полиноми во иста променлива, ѓ(x) И е(x), има такви полиноми q(x) И р(x), се нарекува количник и остаток, соодветно, кои

ѓ(x) = е(x)∙q(x) + р(x), (*)

во овој случај степенот на остатокот е помал од степенот на делителот, полином е(x), и, дополнително, според овие полиноми ѓ(x) И е(x) количникот и остатокот се единствено пронајдени. Ако еднаквоста (*) има остаток р(x) е еднаква на нултиот полином (нула), тогаш велат дека полиномот ѓ(x) се дели со е(x) без остаток.
Алгоритмот се состои од секвенцијална поделба со остаток прв од првиот даден полином, ѓ(x), на вториот, е(x):

ѓ(x) = е(x)∙q 1 (x) + р 1 (x), (1)

тогаш ако р 1 (x) ≠ 0, – вториот даден полином, е(x), на првиот остаток – до полином р 1 (x):

е(x) = р 1 (x)∙q 2 (x) + р 2 (x), (2)

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

тогаш ако р 3 (x) ≠ 0, – вториот остаток до третиот:

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

итн. Бидејќи во секоја фаза степенот на следниот остаток се намалува, процесот не може да продолжи бесконечно, така што во некоја фаза дефинитивно ќе дојдеме до ситуација следната, n+ 1-ви остаток р n+ 1 е еднакво на нула:

Потоа последниот не-нула остаток р n и ќе биде најголемиот заеднички делител на првобитниот пар полиноми ѓ(x) И е(x).
Навистина, ако врз основа на еднаквоста ( n+ 2) наместо тоа, замени 0 р n + 1 (x) во еднаквост ( n+ 1), потоа – добиената еднаквост р n – 1 (x) = р n (x)∙q n + 1 (x) наместо р n – 1 (x) – во еднаквост ( n), излегува дека р n – 2 (x) = р n (x)∙q n + 1 (x) q n (x) + р n (x), т.е. р n – 2 (x) = р n (x)(q n + 1 (x) q n (x) + 1), итн. Во еднаквоста (2) по замената го добиваме тоа е(x) = р n (x)∙П(x), и, конечно, од еднаквост (1) – тоа ѓ(x) = р n (x)∙С(x), Каде ПИ С– некои полиноми. Така, р n (x) е заеднички делител на двата оригинални полиноми, а фактот дека тој е најголемиот (т.е., најголемиот можен степен) произлегува од постапката на алгоритмот.
Ако најголемиот заеднички делител на два полиноми не содржи променлива (т.е. е број), оригиналните полиноми ѓ(x) И е(x) се нарекуваат меѓусебно премиер.

Дефиниција. Ако секој од двата полиноми е делив со трет полином, тогаш тој се нарекува заеднички делител на првите два.

Најголем заеднички делител (GCD) два полиноми се нарекува нивен заеднички делител од највисок степен.

GCD може да се најде со користење на нередуцирана факторизација или со користење на Евклидов алгоритам.

Пример 40Најдете го gcd на полиномите
.

Решение.Ајде да ги факторизираме двата полиноми:

Од проширувањето е јасно дека бараниот GCD ќе биде полиномот ( X– 1).

Пример 41Најдете gcd од полиноми
И
.

Решение.Да ги факторизираме двата полиноми.

За полином
XX– 1) според шемата на Хорнер.

За полином
можни рационални корени се броевите 1, 2, 3 и 6. XСо помош на замена го потврдуваме тоа X– 1) според шемата на Хорнер.

= 1 е коренот. Поделете го полиномот со (
Затоа, , каде што проширувањето на квадратниот трином

беше произведен користејќи ја теоремата на Виета. X– 1)(X– 2).

Споредувајќи ја факторизацијата на полиномите, откриваме дека бараниот GCD ќе биде полиномот (

Слично на тоа, можете да најдете GCD за неколку полиноми.

Сепак, методот за пронаоѓање на GCD со факторизација не е секогаш достапен. Методот што овозможува да се најде GCD за сите случаи се нарекува Евклидов алгоритам.

Шемата на Евклидовиот алгоритам е следна. Еден од двата полиноми е поделен со друг, чиј степен не е повисок од степенот на првиот. Понатаму, дивидендата секој пат се зема за полиномот што служел како делител во претходната операција, а остатокот добиен во истата операција се зема како делител. Овој процес престанува штом остатокот е нула. Ајде да го демонстрираме овој алгоритам со примери.

Да ги погледнеме полиномите употребени во двата претходни примери.Најдете gcd од полиноми
И
.

Решение.Пример 42
Ајде да се поделиме
на

x

"агол":
Сега да го поделиме делителот X– 1:

x+ 1

за остатокот XБидејќи последната поделба се случи без остаток, GCD ќе биде

– 1, т.е. полиномот што се користи како делител во оваа поделба.Најдете gcd од полиноми
И
.

РешениеПример 43
Ајде да се поделиме
на

1

. За да го најдеме GCD ќе го користиме Евклидов алгоритам.
Сега да го поделиме делителот
Ајде да се поделиме
=
Ајде да направиме втора поделба. За да го направите ова, ќе треба да го поделиме претходниот делител
, но бидејќи
, за погодност ќе го поделиме полиномот
не на

, и натаму

.

1. Таквата замена нема да го промени решението на проблемот, бидејќи gcd на пар полиноми се одредува до константен фактор. Имаме:

Остатокот се покажа дека е еднаков на нула, што значи последниот делител, т.е. полином

и ќе биде посакуваниот GCD. Дробни рационални функции
И
Дефинициите и изјавите за 2.5 може да се најдат во.

Дробната рационална функција со реални коефициенти се нарекува израз на формата , Каде- полиноми. Се нарекува фракционо-рационална функција (во натамошниот текст ќе ја нарекуваме „дропка“)..

точно

, ако степенот на полиномот во броителот е строго помал од степенот на полиномот во именителот. Инаку се викапогрешно
.

Решение.За да го изолирате целиот дел од дропката, треба да го поделите броителот на дропката со неговиот именител. Поделете го броителот на оваа дропка со неговиот именител користејќи „агол“:

Бидејќи степенот на добиениот полином е помал од степенот на делителот, процесот на делење е завршен. Како резултат:

=
.
Добиената фракција

е точно.
Дропка од формата x ) се нарекува наједноставно ако φ(
е нередуциран полином, а степенот x ).

помал од степенот φ(Коментар.

Забележете дека моќите на броителот и несведливиот полином во именителот се споредуваат (игнорирајќи ја моќноста на α).

За дропки со реални коефициенти, постојат 4 типа на едноставни дропки: Секоја соодветна дропка
.

може да се претстави како збир од едноставни дропки, чиишто именители се сите можни делители

Алгоритам за разложување на дропка во наједноставна форма:

Ако дропката е неправилна, тогаш го избираме целиот дел, а добиената правилна дропка ја разложуваме на едноставни.

Именителот на соодветната дропка го факторизираме во множители.

Правилната дропка запишуваме како збир на едноставни дропки со неодредени коефициенти.

Збирот на дропките од десната страна го доведуваме до заеднички именител.

Наоѓање на неодредени коефициенти:

Или со изедначување на коефициентите за истите моќи на левиот и десниот намален броител; x.

Или со замена на специфични (обично корените на нивниот заеднички именител) вредности

Одговорот го пишуваме земајќи го предвид целиот дел од дропката.Пример 45
.

Решение.Разложете го на наједноставно

1

= 1 +
.

Бидејќи оваа фракционо-рационална функција е неточна, го избираме целиот дел:
Ајде да ја прошириме добиената фракција

до наједноставните. Прво, да го факторизираме именителот. За да го направите ова, ги наоѓаме неговите корени користејќи ја стандардната формула:

Дозволете ни да го запишеме распаѓањето на фракционата рационална функција во нејзините наједноставни форми, користејќи неодредени коефициенти:

Да ја доведеме десната страна на еднаквоста до заеднички именител:

Ние создаваме систем со изедначување на коефициентите за истите моќи во броителите на левата и десната дропка:
.

Одговор:Пример 45
.

Решение.Пример 46

Бидејќи оваа дропка е соодветна (односно, степенот на броителот е помал од степенот на именителот), нема потреба да се истакнува целиот дел. Ајде да го факторизираме именителот на дропката:

Дозволете ни да го запишеме распаѓањето на оваа дропка во нејзините наједноставни форми, користејќи неодредени коефициенти: Според изјавата, именители на наједноставните дропки мора да бидатсите видови на

.

(2.2) Би било можно да се создаде систем на равенки со изедначување на броителите на левата и десната дропка, но во овој пример пресметките би биле премногу незгодни. Следната техника ќе помогне да се поедностават: ги заменуваме корените на именителот во броителите еден по еден. 1:

На X= ‑1:

x = НаИ Сега да ги одредиме преостанатите коефициентиА

СО Ќе биде доволно да се изедначат коефициентите од највисок степен и слободните членови. Може да се најдат без да се отворат заградите: Левата страна на првата равенка содржи 0, бидејќи броителот на левата дропка во (2.2) не го содржи членот со , а во десната дропка членот со + коефициентА , а во десната дропка членот со + В + коефициент + .На левата страна од втората равенка има 0, бидејќи во броителот на левата дропка во (2.2) слободниот член е еднаков на нула, а во броителот на десната дропка во (2.2) слободниот член е еднаков на (-

Б
.

Д

). Имаме:

Одговор:

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

Ако секој од двата полиноми е делив со трет полином, тогаш овој трет полином се нарекува заеднички делител на првите два.

Најголемиот заеднички делител (GCD) на два полиноми е нивниот заеднички делител со најголем степен.

Забележете дека секој број што не е еднаков на нула е заеднички делител на кои било два полиноми. Затоа, секој број што не е еднаков на нула се нарекува тривијален заеднички делител на овие полиноми.

Евклидовиот алгоритам предлага низа од дејства што или доведува до пронаоѓање на gcd на два дадени полиноми, или покажува дека таков делител во форма на полином од прв или повисок степен не постои.

Евклидов алгоритам е имплементиран како низа од поделби. Во првата поделба, полиномот од поголем степен се третира како дивиденда, а помалиот - како делител. Ако полиномите за кои е пронајден GCD имаат исти степени, тогаш дивидендата и делителот се избираат произволно.

Ако при следното делење полиномот во остатокот има степен поголем или еднаков на 1, тогаш делителот станува дивиденда, а остатокот станува делител.

Ако следното делење на полиномите резултира со остаток еднаков на нула, тогаш gcd на овие полиноми е пронајден. Тоа е делител на последната поделба.

Ако, при следното делење на полиномите, остатокот се покаже дека е број кој не е еднаков на нула, тогаш за овие полиноми нема gcds освен тривијални.

Пример бр. 1

Намали дропка.

2. Можности за поедноставување на GCD пресметките во Евклидов алгоритам

При множење на дивидендата со број кој не е еднаков на нула, количникот и остатокот се множат со ист број.

каде што полиномот P може да се смета како дивиденда, а полиномите Q и R како количник и остаток добиени со делење на полиномот P со полиномот F. Така, при множење на дивидендата со бројот 0, количникот и остатокот се исто така помножено со, h.t

Последица

Множењето на делителот со бројот 0 може да се смета како множење на дивидендата со бројот.

Според тоа, кога делител се множи со број, 0 е количник, а остатокот се множи со.

Пример бр. 2

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

делење полином алгоритам Евклидов

За да отидеме до целобројните коефициенти во дивидендата и делителот, ја множиме дивидендата со 6, што ќе доведе до множење на саканиот количник Q, а остатокот R со 6. После тоа, делителот го множиме со 5, што ќе доведе до множењето на количникот 6Q и остатокот 6R со. Како резултат на тоа, количникот и остатокот добиени со делење полиноми со целобројни коефициенти ќе се разликуваат со фактор неколку пати од саканите вредности на количникот Q и остатокот R добиен со делење на овие полиноми.

Оттука, ;

Забележете дека ако се најде најголемиот заеднички делител на овие полиноми, тогаш со множење со кој било број што не е еднаков на нула, ќе го добиеме и најголемиот делител на овие полиноми. Оваа околност овозможува поедноставување на пресметките во Евклидовиот алгоритам. Имено, пред следното делење, дивидендата или делителот може да се помножат со броеви избрани на посебен начин така што коефициентот на првиот член во количникот е цел број. Како што е прикажано погоре, множењето на дивидендата и делителот ќе доведе до соодветна промена во делумниот остаток, но таква што, како резултат на тоа, GCD на овие полиноми ќе се помножи со некој број еднаков на нула, што е прифатливо.

ОСНОВНИ ИНФОРМАЦИИ ОД ТЕОРИЈАТА

Дефиниција 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 + 2x + 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 + 2x + 2 О R[x] најголемиот заеднички делител е полиномот d(x) = j 1 (x) = x 3 − 4x 2 + 2 О R[x], бидејќи ова е полином d(x) се дели со сите други нивни заеднички делители j 2 (x), j 3 (x),j4 (x).

Најголемиот заеднички делител (GCD) е означен со симболот:

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),го добиваме остатокот r2 (x)и приватни q2 (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),степен r 1 (x)< deg g(x);

g(x)= r 1 (x)× q 2 (x) + r 2 (x),степен r2 (x) < deg r1(x);

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

r k – 2 (x)= r k – 1 (x)× qk(x) + r k (x),степен 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)× qk(x) + r k (x),или r k –-2 (x)= r k (x) × q k +1 (x) × qk(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 чекор.

Да ги напишеме чекорите на поделба во форма на систем на еднаквости и нееднаквости, како во (*) :

f(x)= g(x) × q 1 (x) + r 1 (x), степен r 1 (x)< deg g(x);

g(x)= r 1 (x)× q2 (x).

Според Теорема 4.1./Евклидов алгоритам/ последниот ненула остаток r 1 (x) = 7x 2 + 7 ќе биде најголемиот заеднички делител d(x)овие полиноми :

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

Бидејќи деливоста во полиномниот прстен е дефинирана до асоцијација ( Имотот 2.11.), тогаш како GCD можеме да земеме не 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. Заменувајќи го со неговиот поврзан полином d1 (x)= x 2 + 1, го добиваме нормализираниот најголем заеднички делител на овие полиноми( f(x), g(x)) = x 2 + 1.

помал од степенот φ(Користејќи го Евклидов алгоритам за наоѓање на најголемиот заеднички делител на два полиноми, можеме да го извлечеме следниот заклучок. Најголем заеднички делител на полиноми f(x)И g(x)не зависи од тоа дали сметаме f(x)И g(x)над теренот Пили над неговото проширување П'.

Дефиниција 4.4.

Најголем заеднички делителполиноми f 1 (x), f 2 (x), f 3 (x),… f n (x) Î P[x] се нарекува таков полином d(x)Î P[x], кој е нивен заеднички делител и самиот е делив со кој било друг заеднички делител на овие полиноми.

Бидејќи Евклидовиот алгоритам е погоден само за наоѓање на најголемиот заеднички делител на два полиноми, за да го најдеме најголемиот заеднички делител на n полиноми, треба да ја докажеме следната теорема.