11. Многочлени над числовим полем. Найбільший спільний дільник двох многочленів. Алгоритм Евкліда.

Нехай К – довільна область цілісності

Многочленом або поліномом від 1 змінної над областю цілісності К називається вираз виду:

f(x)=a_nxⁿ+a_n-1x^n-1+…+a₁x+a₀ (1)

де a_i K (i=0…n), n N{0}.

При цьому a_i називають коефіцієнтами многочлена, a_ixⁱ – ітим членом многочлена, зокрема anxn назив старшим членом, a₀ – вільним членом многочлена, x_i – ітим степенем елемента x.

Якщо a_n≠0, то n назив. степенем многочлена і позначають deg f(x)

Многочленами нульового степеня є константи з кільця К, т.б це многочлени виду f(x)≡a₀, a₀≠0, a₀ є K. Говорять, що многочлен f(x)=0 взагалі немає степеня. Запис многочлена у вигляді (1) назив. канонічним або стандартним. Множину всіх многочленів над областю цілісності К прийнято позначати К[х], а над полем Р - Р[х].

Не нульові многочлени

f(x)=a_nxⁿ+…+a₁x+a₀ та g(x)= b_nxⁿ+…+b₁x+b₀ назив. рівними, якщо вони мають одинакові коефіцієнти при відповідних степенях Сумою многочленів f(x) та g(x) називається многочлен f(x)+g(x)=C_nxⁿ+…+C₁x+C₀, де C_i=a_i+b_i (i=0…n) коефіцієнти якого є сумами коефіцієнтів многочленів що стоять при однакових степенях, а степінь дорівнює n, якщо deg f(x)<deg g(x), і не перевищую n, якщо degf(x)=degg(x)

Добутком многочленів f(x) та g(x) називається многочлен

f(x)*g(x)=C_n+mx^n+m+…+C₁x+C₀ степінь якого дорівнює сумі степенів f(x) та g(x), якщо f(x)≠0 і g(x)≠0, а коефіцієнти С_і є сумами добутків тих елементів многочленів f(x) та g(x) які в сумі дають і. З означення випливає, що якщо хоча б один з многочленів нульовий, то добуток дорівнює нулю.

Говорять, що многочлен f(x) ділиться націло на g(x), g(x)≠0, якщо існує q(x) є Р[х] таке, що f(x)= g(x) q(x)

Спільним дільником многочленів f(x) та g(x) є Р[х] називають многочлен D(x), такий що f(x)÷D(x)та g(x)÷D(x)

Найбільшим спільним дільником многочленів f(x) та g(x) називається такий їх спільний дільник, який ділиться на будь-який інший спільний дільник d(x)=( f(x), g(x)). НСД многочленів визначається однозначно Справді, нехай d(x) та d₁(x) – НСД f(x) та g(x), тоді за означенням d(x) ÷d₁(x), d₁(x)÷d(x), тому d(x)≈d₁(x) або d(x)=Сd₁(x). Таким чином, НСД визначається однозначно з точністю до асоційовності.

Наявність ділення з остачею в кільці Р[х] дає можливість знаходити НСД методом послідовного ділення з остачею, тобто за алгоритмом Евкліда

Нехай f(x) та g(x) є Р[х], g(x)≠0 і degf(x)≥ degg(x). Тоді можливі випадки :

1. f(x)÷ g(x) → (f(x), g(x))≈ g(x).

2. f(x) не ділиться на g(x), Розділимо f(x) на g(x) з остачею, g(x) на r₁(x) і тд

f(x)=g(x)q₁(x)+r₁(x)

g(x)=r₁(x)q₂+r₂(x)

r₁(x)=r₂(x)q₃(x)+r₃(x)

………………………

r_n-1(x)=r_n(x)q_n+1(x)+r_n+1(x)

r_n(x)=r_n+1(x)q_n+2(x)

deg g>deg r₁>…>deg r_n+1)

Процес ділення буде скінченим, бо степені остач строго спадають і обмежені знизу нулем. Покажемо, що член r_n+1(x) є НСД f(x) та g(x). Справді, піднімаючись знизу вгору легко показати, що r_n+1(x)=СД (f(x), g(x)). З іншого боку будь-який СД Д(х) многочленів f(x) та g(x) буде дільником r_n+1(x), справді, з 1-го рівняння випливає, що r₁(x)÷Д(х), з другого – r₂(x)÷Д(х)… , з передостаннього r_n-1(x)÷Д(х), тобто r_n+1(x) є НСД f(x) та g(x).

При переході від одного ділення до іншого в алгоритмі Евкліда, ділені та дільник можна помножати або ділити на деяке число відмінне від нуля при цьому будуть змінюватися частки, а остачі будуть множитись на деякі числа. Тобто в результаті r_n+1(x) буде помножений на деяку константу, яка по суті його не міняє. Тобто процес ділення можна полегшити.

Алгоритм Евкліда дозволяє знайти лінійне представлення 2-х многочленів у кільці Р[х], т.б подати НСД у вигляді

d(x)=f(x)u(x)+g(x)v(x) (2)

де u(x), v(x) є P[x] і залежить лише від часток q_i(х). Покажемо, що таке представлення існує. Для цього з передостанньої рівності алгоритма Евкліда виразимо НСД

d(x)=r_n+1(x)=r_n-1(x)-r_n(x)q_n+1(x)

з двох попередніх рівностей виразимо r_n-1(x) та r_n(x)

r_n(x)=r_n-2(x)-r_n-1(x)q_n(x)

r_n-1(x)=r_n-3(x)-r_n-2(x)q_n-1(x)

та підставимо їх у вираз d(x). Рухаючись угору, та виражаючи остачі одержимо вираз (2) в якому u(x) та v(x) залежать лише від q_i(x).

На відміну від знаходження НСД за алгоритмом Евкліда при знаходженні лінійного представлення НСД помножати ділені та дільники на константи неможна, бо від цього суттєво зміняться частки, а значить u(x) та v(x).

Т-ма(лінійне представлення НСД)

Якщо d(x)=( f(x), g(x)), де f(x) та g(x) є Р[х], то в кільці Р[х] знайдуться многочлени u(x), v(x) такі, що має місце представлення

d(x)=f(x)u(x)+g(x)v(x), якщо при цьому deg f(x) >0 і deg g(x)>0 то можна вважати що deg u(x)<deg g(x) i deg v(x)<deg f(x).

Д-ня Існування представлення (2) доведено вище. Покажемо, що справджується друга частина теореми. Припустимо, що це не так і

deg u(x)≥ deg g(x) тоді, розділивши deg u(x) на deg g(x) з остачею одержимо:

u(x)=g(x)q₁(x)+r₁(x), де degr₁(x)<degg(x) або r₁(x)≡0 Підставимо u(x) у вираз (2) отримаємо

d(x)=f(x)(g(x)g₁(x)+r₁(x))+g(x)v(x)

d(x)=f(x)r₁(x)+g(x)(f(x)q₁(x)+v(x))

Оскільки deg r₁(x)<deg g(x) → degr₁(x)f(x)<deg f(x)g(x),але в такому випадку степінь другого доданка правої частини більший ніж степінь першого доданку і тому степінь правої частини буде не менший ніж deg f(x)g(x)=deg f(x)+deg g(x)>deg f(x) i deg f(x)g(x)>deg g(x). З іншого боку, степінь d(x) збігається з степенем правої частини і тому більший за degf(x) і більший ніж deg g(x) що неможливо, бо d(x) – дільник f(x) і g(x), т.б припущення невірне. Отже deg u(x)<deg g(x) аналогічно переконуємось що deg v(x)<deg f(x).▲