Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
12 Многочлены над полем. Наибольший общий делитель двух многочленов и алгоритм Евклида.
Простое транцендентное расширение кольца
Пусть К и L – коммуникативные кольца.
ОПР1 Кольцо К называется простым расширением кольца L с помощью элемента х, если выполняются следующие условия:1. L К,
2. аК, то а = аnxn + an-1xn-1 + … + a1x + a0 (1), где аn, an-1,…, a1, a0 – элемены L, х- тот элемент, с помощью которого строится расширение, nN.
Обозначается: K = L[x].
ОПР2 Расширение K = L[x] называют простым транцендентным расширением, если выполняется следующие условие: аnxn + an-1xn-1 + … + a1x + a0 = , К. Отсюда следует, что аn=, an-1=,…, a0=. Т.к. L К, то аn = an-1 =…= a0 =.
Если К является простым транцендентным расширением L, то элемент х называется транцендентным относительно кольца L.
ТЕОРЕМА1 Если K = L[x] является простым транцендентным расширением, то представление каждого элемента из кольца К в виде равенства (1) однозначно.
Д-ВО: проводится методом от противного с учетом ОПР2.
ОПР3 Кольцо K = L[x], т. е. простое транцендентное расширение L при помощи х , называют кольцом многочленов от переменной х над кольцом L, а каждый элемент из кольца К представленный в видеравенства (1) называют многочленом от переменного х над кольцом L.
Понятие многочленов. Операции над ними и их свойства.
ОПР4 Многочлены от одного переменного х над областью целостности с единицей (К с 1) назовем выражение вида: аnxn + an-1xn-1 + … + a1x + a0 (2), где аn, an-1,…, a1, a0 кольцу К, х- некоторый символ, называемый переменной, nN.
ЗАМЕЧАНИЕ Понятие многочлен можно было бы определить и над произвольным кольцом К, т.е. не обязательно над областью целостности с единицей. Тогда операция умножения не обладала бы многими «хорошими» свойствами и теория делимости оказалась бы «бедной».
Обозначим множество всех многочленов вида (2) символом K[x] и зададим на этом множестве операции «+» и «*» многочленов.
В равенстве (2) элементы аn, an-1,…, a1, a0 – коэффициенты многочлена. При условии, что аn0 натур. число n называют степенью многочлена, аnxn, an-1xn-1, …,a1x,a0 – одночлены многочлена, аnxn- старший член многочлена при условии, что n0, аn – коэффициент при старшем члене.
ОПР5 Два многочлена из множества K[x] равны, если равны их степени и равны все коэффициенты при соответствующих степенях переменного х. (это алгебраическое определение равенства двух многочленов.
Обозначать многочлены будем используя функциональный подход:
f(x) = аnxn + an-1xn-1 + … + a1x + a0 , аn0, φ(x) = bmxm + bm-1xm-1 + … + b1x + b0 , bm0.
Степень f(x) = n, степень φ(x) = m, nm – для определенности, bm+1 = bm+2 = … = bn = 0. f(x) и φ(x)К.
ОПР6 Суммой двух многочленов f(x) и φ(x) назовем многочлен
f(x) + φ(x) = (аn + bn)xn + (аn-1 + bn-1)xn-1 + … + (а1 + b1)x1 + (a0 + b0) (3)
ОПР7 Произведением многочленов f(x) и φ(x) назовем многочлен
f(x) * φ(x) = (4)
ТЕОРЕМА2 Степень суммы двух многочленов не превосходит наибольшую из степеней слагаемых. Степень произведения двух многочленов равна сумме степеней умножаемых.
Д-ВО: следует из определения 6 и 7.
ТЕОРЕМА3 Если К – область целостности с единицей, то <K[x],+,*> - тоже является областью целостности с единицей.
ОПР8 Область целостности с единицей K[x] называют кольцом многочленов от одного переменного х над областью целостности К.
ТЕОРЕМА4 K[x] – кольцо многочленов от одного переменного является простым транцендентным расширением кольца К.
Д-ВО: 1). Очевидно, что КK[x] (видно из определения 6 и 7).
2). Каждый элемент из кольца K[x] по его определению представим в виде равенства (1).
3). Если f(x) = аnxn + an-1xn-1 + … + a1x + a0 = = 0*xn + 0*xn-1 + … + 0*x + 0 , то определению 5 следует, что аn = 0, an-1 = 0,…, a0 = 0. Все условия транцендентного расширения выполняются. Теорема доказана.
Теорема 4 показывает существование простых транцендентных расширений.
Отметим, что существует функциональный подход к определению многочлена: f(x) = аnxn + an-1xn-1 + … + a1x + a0 , где область определения D( f ) = K и область значения E( f ) = K, а, следовательно, существует и определение равенства двух многочленов как функций.
ОПР 9 Пусть f(x) и φ(x)K[x], где К – это область целостности. Тогда будем считать, что f(x) = φ(x) в функциональном смысле, если аK f(а) = φ(а).
ТЕОРЕМА 5 Если К – бесконечная область целостности, то алгебраическое и функциональное определения равенства двух многочленов над областью К равносильны.
ЗАМЕЧАНИЕ Над конечной областью целостности функциональное и алгебраическое определения неравносильны.
Многочлены над полем. Делимость многочлена.
Пусть F – некоторое поле, F[x] – кольцо многочленов над этим полем, f(x) и g(x) - многочленыF[x].
ОПР 10 Говорят, что многочлен f(x) нацело делится на g(x) (f(x)g(x)), если существует многочлен φ(x)F[x] такой, что f(x) = g(x)*φ(x).
Свойства делимости:
Д-ВО: f(x) = аnxn + an-1xn-1 + … + a1x + a0 = = а* g(x) f(x)а.
Д-ВО: f(x) = [а*f(x)] f(x)а*f(x).
ОПР 11 Говорят, что многочлен f(x) делится с остатком на многочлен g(x), если существуют такие многочлены φ(x) и r(x), что выполняются условия:
ТЕОРЕМА 6 (о делении с остатком) Для любых двух многочленов f(x) и g(x), где g(x)θ существуют многочлены φ(x) и r(x), удовлетворяющие условиям определения 11, причем эти многочлены определены однозначно.
Д-ВО: 1. Существование:
Пусть f(x) = аnxn + an-1xn-1 +…+ a1x + a0 и g(x) = bmxm + bm-1xm-1 +…+ b1x + b0 , причем an0.
Если ст.f(x) < ст.g(x) или если f(x) = θ, то условию опред11 удовлетворяют многочлены: φ(x) = 0, r(x) = f(x). Тогда f(x) = g(x)*0 + f(x) – существование доказано.
Пусть ст.f(x) ст.g(x), тогда домножим многочлен g(x) на одночлен h1(x) так, чтобы старший член f(x) был равен старшему члену многочлена g(x)*h1(x). Очевидно, что h1(x) = .
Рассмотрим разность f(x) - g(x)*h1(x) = f1(x), ст.f1(x) < ст.f(x) или f1(x) = θ. Если f1(x) = θ, то мы нашли многочлен, который нам требовался. Если f1(x)θ и ст.f1(x) ст.g(x), то домножим g(x) на h2(x) так, чтобы старший член многочлена f1(x) был равен старшему члену многочлена g(x)*h2(x) и рассмотрим разность f1(x) - g(x)*h2(x) = f2(x). Получаем, что ст.f2(x) < ст.f1(x) или f2(x) = θ. Если f2(x) = θ, то мы опять нашли нужный многочлен.
Этот процесс продолжим, если f2(x)θ. На каком то шаге получим:
fs-2(x) - g(x)*hs-1(x) = fs-1(x)
fs-1(x) - g(x)*hs(x) = fs(x), ст.fs(x) < ст.fs-1(x) или fs(x) = θ.
Этот процесс конечный, т.к. степень многочленов f1, f2,…,fs убывает и является натуральными числами. Т.е. не более чем через m – шагов, мы получим, что степень ст.fi(x) < ст.g(x).
Сложим почленно все равенства, полученные в этом процессе:
f(x) = g(x)*[ h1(x) + h2(x) + … + hs(x)] + fs(x) или f(x) = g(x)* φ(x) + r(x), т.е. существование доказано.
2. Единственность:
Предположим, что существует две пары таких многочленов: f(x)=g(x)*φ(x)+r(x) и f(x)=g(x)*ψ(x)+r1(x), причем 0ст.r(x) < ст.g(x) и 0ст.r1(x) < ст.g(x). Найдем их разность:
g(x)*[φ(x) - ψ(x)] = r1(x) - r(x) (*) [r1(x) - r(x)]g(x) и ст.[r1(x) - r(x)] < ст.g(x).
Отсюда следует, что это возможно только при условии, что r1(x) = r(x). Из равенства (*) следует, что φ(x) = ψ(x), т.е. единственность доказана.
Наибольший общий делитель многочлена.
ОПР 12 Многочлен d(x) называется общим делителем многочленов f1(x), f2(x),…, fn(x), если fi(x) d(x), где i = 1…n.
ОПР 13 Наибольшим общим делителем (НОД) многочленов f1(x), f2(x),…, fn(x) называется такой многочлен D(x), что выполняется два условия:
ТЕОРЕМА 7 Если D(x) и D׳(x) – это НОД многочленов f1(x), f2(x),…, fn(x), то D(x) = а * D׳(x), где аF.
ОПР 14 НОД D(x) называется нормированным, если его старший коэффициент равен единице.
СЛЕДСТВИЕ из теоремы 1 Нормированный НОД многочленов определен однозначно.
D(x) = ( f1, f2,…, fn ) - нормированный НОД.
ЛЕММА 1 Если многочлен f(x)g(x), где g(x)θ, то НОД f(x) и g(x) равен g(x), т.е. ( f(x), g(x) ) = g(x).
ЛЕММА 2 Если f(x) = g(x)* φ(x) + r(x), где 0 ст.r(x) < ст.g(x), то ( f(x), g(x) ) = ( g(x), r(x) ).
Покажем, что для любых двух многочленов f(x) и g(x), f(x)θ, g(x)θ существует конечная последовательность Евклида.
Разделим f(x) на g(x) с остатком: f(x) = g(x)* φ(x) + r0(x), где ст.r0(x) < ст.g(x).
Разделим g(x) на r0(x) с остатком: g(x) = r0(x)* φ1(x) + r1(x), где ст.r1(х) < ст.r0(x).
Разделим r0(x) на r1(x) с остатком: r0(x) = r1(x)* φ2(x) + r2(x), где ст.r2(х) < ст.r1(x).
и так далее … rк-3(x) = rк-2(x)* φк-1(x) + rк-1(x).
rк-2(x) = rк-1(x)* φк(x) + rк(x), где ст.rк(х) < ст.rк-1(x).
rк-1(x) = rк(x)* φк+1(x).
У нас последовательность конечная, т.к.степень многочленов – числа натуральные, степень остатков убывает, поэтому в результате получится многочлен нулевой степени, на который любой многочлен делится нацело.
Последовательность называется последовательностью Евклида. Она существует для любых двух многочленов f(x) и g(x), отличных от r(x), и конечна.
ТЕОРЕМА ЕВКЛИДА Наибольшим общим делителем многочленов f(x) и g(x) является последний отличный от нуля остаток в последовательности Евклида для этих многочленов.
Д-ВО: следует из леммы 1 и леммы 2.
ТЕОРЕМА 3 Если D(x) = (f1(x), f2(x),…, fn-1(x)), а d(x) = (D(x), fn(x)), то отсюда следует, что d(x) = (f1(x), f2(x),…, fn-1(x), fn(x)).
Д-ВО: проводится методом мат. индукции.
СЛЕДСТВИЕ из теоремы 3 Если d1(x) = (f1(x), f2(x))
d2(x) = (d1(x), f3(x))
d3(x) = (d2(x), f4(x))
…
dn-1(x) = (dn-2(x), fn(x)), то следует, что dn-1(x) = (f1(x), f2(x),…,fn(x)).
ТЕОРЕМА 4 (о линейном представлении НОД двух многочленов). Пусть D(x) = (f(x), g(x)). Тогда существуют многочлены φ(x) и ψ(x) такие, что выполняется два условия:
Д-ВО: Для доказательства существования таких многочленов можно воспользоваться последовательностью Евклида. Выражая из предпоследнего равенства rк(x), затем вместо rк-1(x) поставим его в выражение из третьего равенства снизу и т.д. Поднимаясь вверх по последовательности Евклида выразим D(x) через f(x) и g(x), т.е. получим равенство (5).
Если степень многочленов φ(x) и ψ(x) удовлетворяют условиям теоремы, то теорема доказана.
Пусть ст.φ(x) ст.g(x). Разделим φ(x) на g(x) с остатком: φ(x) = g(x)*h1(x) + r1(x) (6), ст.r1(x) < ст.g(x). Подставим равенство (6) в равенство (5):
D(x) = f(x)*[g(x)*h1(x) + r1(x)] + g(x)*ψ(x) = f(x)r1(x) + g(x)* [f(x)h1(x) + ψ(x)] (7)
Обозначим выражение, стоящее в квадратных скобках, через s(x): s(x) = f(x)h1(x) + ψ(x).
Покажем теперь, что ст.s(x)< ст.f(x). Предположим, что ст.s(x)ст.f(x), тогда ст.f(x)*r1(x) < ст.s(x)*g(x) так как выполняется ст.r1(x) < ст.g(x) ст.D(x) = ст.s(x)*g(x) (8)
С другой стороны g(x)D(x) ст.g(x)ст.D(x), ст.g(x)*s(x) > ст.D(x) (9)
Утверждения (8) и (9) противоречат друг другу. Значит предположение неверно, т.е. ст.s(x)< ст.f(x).
Теорема доказана.