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

Date: 2015-10-07; view: 603.

Лемма: Пусть f(x), g(x) ÎР[x] — многочлены; f(x) ¹0, g(x) ¹0.

Тогда deg f(x)* g(x)= deg f(x)+deg g(x).

< Пусть f(x)=a0+a1x+…+an x^n , аn¹0,

g(x)=b0+b1x+…+bs x^s , bs¹0

f(x)* g(x)=an*bs x(^n+1)+…

Последнее и означает, что степень многочлена равна n+s.

deg f(x)* g(x)=n+s.>

Определение1.Пусть f(x), g(x)ÎР[х]. Будем говорить, что f(x) делит g(x) (обозначать f(x)ïg(x) ), если существует j(х)ÎР[х] такое,что g(x)=f(x)*j(х).

Простейшие свойства:

1)Если g(x) делит fi(x), i=1..n, то g(x) делит .

2)Если f(x) / g(x)и g(x) / m(x), тогда f(x) / m(x).

3)Если f(x) / g(x)и g(x) / f(x), то f(x)=ag(x),где aÎР.

Докажем первое свойство:

◄g(x) / fi(x) следовательно $ многочлен ji(х), что fi(x) = g(x)ji(х), следовательно

Вынесем общий множитель g(x) за знак суммы. А это и означает, что g(x) делит сумму . >

Второе свойство доказывается аналогично как и для чисел.

Докажем третье свойство:

< f(x) / g(x)®g(x)=f(x)*m(x) (1)

g(x) / f(x)®f(x)=g(x)*q(x) (2)

Подставим (2) в (1):

g(x)=g(x)*q(x)*m(x) Þ g(x)*(q(x)*m(x)-1)=0Þq(x)*m(x)=1.

Из леммы следует, что степень q(x)= степени m(x)=0.

Иначе говоря, что q(x) и m(x) — это элементы поля P. А это и доказывает свойство 3. >

Теорема о делении с остатком:Пусть f(x), g(x)ÎР[х], g(x)¹0. Тогда существует единственная пара многочленов q(x), r(x)ÎР[х], такая, что f(x)=g(x)*q(x)+r(x), где степень r(x)<степени g(x)либо r(x)=0.

Доказательство. 1) случай: f=0,очевидно q=0, r=0; 2) случай: если степень f<степени g(cт.g), то q=0 и r=f; 3)случай: ст. f³ст.g.

Пусть

f=an*x^n+…+a0,

g=bs*x^s+…+b0.

Возьмем многочлен j1=(an/bs)*x(s-n). Рассмотрим f-g*j1=f1. Если f1=0, то в качестве r возьмём 0, в качестве q-j1, т.е. r=0; q=j1. Если ст. f1 < ст.g , то в качестве r возьмем f1, а в качестве q -j1. Если ст. f1³ ст.g, то берем

f – g j1 ₌ f1 ( ст.f1 < ст.f ),

f – g j2 ₌ f2 ( ст.f2 < ст.f2 ). C f2 рассуждаем аналогично как и с f2. На

каком-то шаге мы получим, что многочлен fk=0 либо его степень меньше степени g ( степени многочленов f_k все время уменьшаются ), где f_k-1 – g (j)(k) = fk

f – g j1 ₌ f1 ( ст.f1 < ст.f ) Сложим почленно

f1 – gj2 ₌ f2 ( ст.f2 < ст.f1 ) (1) левые и правые части

…………………………..

равенств:

f_k-1 – g (j)(k) ₌ fk

__________________________

Получим, что

f – g (j1+…+jk ) = fk и очевидно

q = j1+…+jk ; r = fk.

Этим мы доказали существование q и r.

f = g(j1+…+jk ) + fk.

Докажем однозначность q и r. Доказывать будем методом от противного. Пусть наряду с разложением f = gq+r (2) имеет место разложение f = gq1+r1 (3). Вычтем из (2) равенство (3). Получим:

r – r1 = g ( q1 – q ).

Сравним степени многочленов слева и справа. Если r-r1≠0, то степень r – r1 < степени -g (q1 – q ). А такого быть не может для равных многочленов. Мы пришли к противоречию. Однозначность доказана. >

Алгоритм Евклида: Пусть f(x) и g(x) — два многочлена над полем Р.

f(x) , g[x] ÎP[x] ; g(x)¹ 0. Тогда можно разделить с остатком f(x) на g(x).

f(x)=g(x)q(x)+r(x) , если r(x) ¹0, степень r(x)<степени g(x).

Разделим g(x) на r(x) с остатком g(x)=r(x)q1(x)+r1(x), если r1(x) ¹0 степень r₁ < степени r.

Разделим r(x) на r1(x) и т.д.

Так как степени остатков все время убывают, то на каком-то шаге остаток r_k+1(x)=0.

f(x)=g(x)q(x)+r(x) ; r(x) ¹0

g(x)=r(x) q1(x)+r1(x) ; r1(x) ¹0 ; cт. R1< ст. r

(4) r(x)=r1(x)q2(x)+r2(x)

…………………..

(r)(k-1) (x)=rk(x)(q) (k+1)(x)+ (r)(k+1) (x), (r)(k+1) (x)=0.

Процесс последовательного получения равенств (4) называют алгоритмом Евклида для многочленов f(x) и g(x). Последний отличный от нуля остаток — rk.