Кольца многочленов, делимость

Множество многочленов над кольцом Я от одной переменной х (обозначаемое Ях) образует кольцо относительно операций сложения и умножения. Нулем кольца Я[х] является нулевой многочлен, у которого все коэффициенты — нули кольца R. Кольцо Ях коммутативное « кольцо R коммутативное. Кольцо R[x] имеет единицу е(х) <=> кольцо R имеет единицу е; у многочлена е(х) свободный член равен е, а остальные коэффициенты равны нулю кольца R.

Заметим, что многочлен f(x) = я0 + ахх + ... + аггхп над кольцом R задает преобразование кольца R. Вместе с тем, не всякое преобразование кольца R можно задать многочленом.

Преобразование g кольца называется полиномиальным, если найдется полином f(x) е R[x], реализующий преобразование g, т.е. g(x) = f(x) для любого х е R.

Любое преобразование g коммутативного кольца R полиномиальное <=> <=> R — поле. Для кольца вычетов данная теорема доказана С. В. Яблонским[1].

Рассмотрим кольцо многочленов Р[х] над полем Р. Пусть f(x), g(x)y h(x) е Р[х]. Говорят, что ненулевой многочлен g(x) делит f(x) (обозначается g(x) |/(х)), если имеется многочлен h(x) такой, что fix) = g(x)h(x)y при этом говорят также, что fix) кратен g(x).

В Р[х выполнены следующие свойства делимости:

  • 1) Я(-г) I f(x) <=> ag(x) I bf(x), где a, b e P, a* 0;
  • 2) если g'(x) | f(x) и f(x) — ненулевой многочлен, то degg(x) < dcg/(x);
  • 3) g(x) I f{pc) и f{x) |g(x) <=> ag(x) =/(x), где a e P;
  • 4) если g(x) |/(x) и g(x) h(x), to g(x) |/(x) ± h(x);
  • 5) если g(x) |/(x), to g(x) I f(x)h(x). >

Далее 0 < degg'(x) < deg/(x). Разделить с остатком /(x) на g(x) — значит найти q(x), r(x) e P[x] такие, что /(x) = g(x)q(x) + r(x) и 0 < degr(x) <

< degg(x). Многочлены q(x) и r(x) называются соответственно неполным частным и остатком от деления f(x) на g(x).

Теория делимости многочленов над полем во многом аналогична теории делимости чисел в силу того, что Z и Р[х образуют коммутативные кольца с единицей. Основное отличие в том, что мерой остатка от деления в Z является модуль числа, а в Р[х] — степень многочленов. Приведем положения теории делимости многочленов (доказательства см. в [2]).

Теорема 2.12. Многочлен Дх) можно разделить с остатком на ненулевой многочлен g(x), при этом неполное частное и остаток от деления определены однозначно. О

Значением многочлена Дх) = а0 + ахх +...+ аггхп в точке b е Р называют элемент поля Р

Отсюда если Дх) = g(x) + h(x) и /*(x) = g*(x)A*(x), то f(b) = g(b) + h(b) и f*(b) = g*(b)h*(b).

Корнем многочлена f(x) в поле P называется элемент b поля Р, для которого /(b) = 0.

Теорема 2.13 (Безу). Остаток от деления Дх) на х - b равен f(b), b е Р. В частности, b — корень многочлена Дх) <=> (х - b) | Дх).

Ч Разделим с остатком f(x) на х - b: Дх) = q(x){x - b) + Дх), где deg/^x) < < 1. Тогда r(x) e P и значение Дх) одинаково для всех х е Р. Подставив в равенство х = Ь, получаем f(b) = г(Ь) = г(х). Заметим, b — корень f(x) « « r{b) = r(x) = 0, что равносильно свойству (х - b) f(x). ?

Следствие. Многочлен степени п > 0 имеет в Р не более п различных корней.

Ч Пусть b — корень многочлена/(х), тогда по теореме Безу f(x) = q(x)(x-b), где многочлен q(x) ненулевой. Заметим, что с — корень многочлена /(х), где с ф Ъ <=> с — корень многочлена q(x), где degq(x) = п - 1. Проведя рассуждения для п различных корней, получаем после п-го шага ненулевое частное степени 0, т.е. константу поля Р, которая корней не имеет. ?

Многочлен со старшим коэффициентом, равным единице поля, называется унитарным. Множество унитарных многочленов замкнуто относительно умножения, но не относительно сложения. Остаток от деления унитарных многочленов не обязательно унитарный.

Ассоциированным с многочленом /(х) = а0 + а{х + ... + аГ1хп называют многочлен а/(х), где а — ненулевой элемент поля Р. При а = а~х многочлен af(x) унитарный. Значит, для любого многочлена из Р[х] существует единственный унитарный ассоциированный с ним многочлен.

Многочлен, делящий/(х) и g(x), называют их общим делителем. Наибольший общий делитель многочленов/(х) и g(x) (обозначается (Дх), g(x)) или НОД(/(х), g(x))) — это общий делитель наибольшей степени, где (Дх), 0) = = (Дх)) = Дх). Поскольку степень общих делителей Дх) и g(x) конечна и 1 делит Дх) и g(x), то существует единственный унитарный (Дх), g(x)).

Многочлен, кратный Дх) ng(x), называют их общим кратным. Наименьшее общее кратное многочленов Дх) и g(x) (обозначается [Дх), g(x)] или НОК(Дх), g(x))) — это общее кратное наименьшей степени, где [Дх), 0] =

= 1/001 =/(*)• Поскольку ctegHOK(/(x), g(x)) < deg(f(x)g(x)), то суще- ствует единственный унитарный [Дх), g(x)].

Наибольший общий делитель и наименьшее общее кратное многочленов /Дх), ..., /Дх) обозначают соответственно НОЖ/), ...,/„) и НОК(Д, Л). Если {/„ с ...,gm), то НОД(^, IНОД(/„ НОД(/„.... /„)| НОК(/„ НОКС/,, lHOK(g„

Для любых многочленов /Дх), /Дх) при п > 1 НОД(/), /„) =

= нод (нод „), НОК(/„ = НОК(НОК(/„ >

Многочлен/(х) из Р[х] называется неприводимым над Р, если он не представим в виде произведения двух многочленов ненулевой степени из Р[х]. По теореме Безу многочлен степени 2 или 3 неприводим <=> не имеет корней в Р.

Пример 2.7

Многочлен х2 - 3 неприводим над Q, так как его корпи иррациональны, но приводим над R: х2 - 3 = (х + -s/З )(лг - л/з). О

Если /(х) неприводим над Р, то:

  • 1) любой многочлен g(x) из Р[х либо кратен /(х), либо (Дх), g'(x)) е Р
  • 2) если/(х) |g(x)/z(x) для g(x), /г(х) е Р[х], то/(х) |g(x) или/(х) |/Дх).

В кольце Р[х] множество унитарных неприводимых многочленов бесконечно, в том числе если поле Р конечное.

Теорема 2.14. Унитарный многочлен степени п > 0 или неприводим над Р, или разлагается (единственным образом) в произведение унитарных неприводимых над Р многочленов. >

В силу данной теоремы любой многочлен /(х) степени п > 0 представляется в виде

где ап старший коэффициент /(х); /?Дх),..., ps(x) — унитарные, неприводимые, попарно различные многочлены из Р[х] и kv ..., ks е N — их кратности. Представление (2.4), называемое каноническим разложением многочлена /(х), позволяет легко определить их НОД и НОК.

Для многочленов высокой степени нахождение (/(х), g(x)) и [Дх), g(x)] с помощью канонических разложений является, как правило, трудоемким ввиду большой сложности определения делителей многочленов. Менее сложным является способ на основе алгоритма Евклида. Корректность алгоритма Евклида основана на следующих свойствах: если g(x) I/(х), то (Дх), g(x)) = = g(x); если /(х) = g(x)q(x) + Дх), где 0 < deg^x) < degg'(x), то (Дх), g(x)) = = (g(x), Дх)). Как и для чисел, алгоритм состоит в выполнении цепи делений с остатком до тех пор, пока степень остатка не станет равной нулю. Конечность цепи делений обеспечивается уменьшением степеней остатков.

Из алгоритма Евклида для многочленов следует, что если d{x) = (Дх), g(x)), то существуют такие многочлены и(х) и v(x), что f{x)u{x) +g(x)^(x) = = d(x). Также если НОД^Дх), ..., ап(х)) = d(x) при п > 1, то существуют такие многочлены г/Дх),..., ип(х)} что яДх)г/Дх) + ... + ап(х)ип(х) = d(x).

Кратностью корня b е Р многочлена /(х) е Р[х] называется число k е N такое, что многочлен (х - b)kf(x) и (х - b)k+x нс делит/(х); корень b многочлена /(х) называют кратным, если k > 1, и простым, если k = 1. Кратность корня 6 многочлена /(х) совпадает с кратностью многочлена (х - Ь) в каноническом разложении /(х) над Р.

Аналогично следствию теоремы 2.13 доказывается следующая теорема.

Теорема 2.15. Если Ь ..., bs различные корни в Р многочлена /(х) е Р[х] степени п > 0 и их кратности равны соответственно kv ..., ks, то kx + ... + ks < п.

Производной многочлена а{х) = я0 + аЛх -г ... + а(рсп е Рх] называется многочлен а'(х) = а{ + Ча-рс + ... + narpcn~{. С помощью производной различают простые и кратные корни многочлена. Отметим свойства производных. Для любых многочленов а(х), Ь(х) е Р[х]

  • 1. (л(х) + Ь(х))' = ах) + Ь'(х)
  • 2. (а(х)Ь(х))' = ах)Ь{х) + Ь'(х)а(х);
  • 3. ((a(x))k)' = k(a(x))k~xa'(x). D>

Теорема 2.16. Корень b € Р многочлена/(х) е Р[х] является простым « <=> b не является корнем его производной /'(х).

А Пусть k — кратность корня Ь. Тогда /(х) = (х - b)kg(x), где g(b) * 0. Отсюда /'(х) = k(x - b)k~]g(x) + (х - b)kgx).

Отсюда / '(fc) = g(6) ^ 0, если k = 1. Если & > 1, то /'(6) = 0, т.е. если /'(6) Ф 0, то k - 1. ?

Следствие. Множество кратных корней в Р многочлена /(х) е Р[х] совпадает с множеством всех корней в Р многочлена d(x) = (/(х)/'(х)). О

Поле Р называется нолем разложения многочлена /(х) е Р[х] степени > 0, если /(х) разлагается над Р в произведение линейных множителей. В этом случае каноническое разложение многочлена /(х) имеет вид /(х) =(x-bl)kK..(x-bs)k*.

Пример 2.8

Для действительного многочлена х2 + 1 поле действительных чисел не является нолем разложения, а ноле комплексных чисел — является. С>

Поле называется алгебраически замкнутым, если оно есть поле разложения для любого многочлена ненулевой степени.

Теорема 2.17 (Гаусс). Поле С комплексных чисел алгебраически замкнутое. О

Над полем С неприводимы все полиномы 1-й степени и только они.

Теорема 2.18. Среди действительных многочленов неприводимы все многочлены первой степени и многочлены второй степени с отрицательными дискриминантами. 1>

Теорема 2.19 (Эйзенштейн). Многочлен /(х) = а0 + ахх + ...+ atrxn с целыми коэффициентами неприводим над Q, если для простого числа р выполнено:

  • 1) р не делит ап
  • 2) р | й,-, где г = 0, 1 1;
  • 3) р2 не делит а0. t>

Отсюда над нолем Q имеются неприводимые многочлены любой натуральной степени п.

Определим отношение эквивалентности на R[x], где R — кольцо. Пусть ф(х) е R[x] и deg(p(x) = п, положим /(х) =g(x) <=> совпадают остатки от деления /(х) и g(x) на многочлен ср(х), записывается /(х) =g(x)(mod(p(x)). Следовательно, кольцо Л[х] разбивается на классы эквивалентности. Транс- версал кольца R[x] по эквиваленции =, состоящий из всех унитарных многочленов степени меньше п, образует относительно сложения и умножения кольцо, обозначаемое R[x] / ср(х) и называемое факторкольцом кольца R[x] по модулю ф(х).

В Rx] / ф(х) сложение многочленов определено как в R[x], а умножение многочленов/(х) и g(x) — как остаток от деления на ф(х) многочлена/(x)g(x). Если R — коммутативное кольцо с 1, то и Rx] / ф(х) — коммутативное кольцо с единицей 1. Данная эквиваленция есть конгруэнция кольца /?[х], т.е. если /(х) =g(x)(тобф(х)) и /*(х) = g*(x)(modф(x)), то /(х) ± /*(х) = (g(x) ± ±g*(x))(mod(p(x)>, /(х)/*(х) = g(x)g%r)(modф(х)).

Пусть /(x) = g(x)(modф(x)), тогда для данной эквиваленции выполнено:

  • 1) /(*) = g(x)(modrf(x)), где d(x) I ф(х);
  • 2) если /(х) = g(x)(mod|/(x)), где deg(ф(x), ф(х)) = 0, то /(х) = g'(x) (mod (ф(х) ф (х*))).

Получим условие обратимости элементов кольца Р[х] / ф(х), где Р — поле. Определим для ненулевого многочлена /(х) обратный многочлен g'(x), т.е. решим сравнение

где е - единица кольца Р[х.

Теорема 2.20. Ненулевой многочлен /(х) обратим в Р[х] / ф(х) <=^ «deg^(x),/(x)) = 0.

Ч Пусть (ф(х), /(х)) = d(x). Если degrf(x) > 0, то (2.5) не выполнено для любого многочлена g(x) е Rx / ф(х), иначе из d(x)f(x)g(x) - е и d(x) |/(х) следует, что d(x) е.

Обратно, при degrf(x) = 0 имеются такие многочлены г/(х), v(x), что f(x)u(x) + ф(х)т’(х) = е. Полагая g(x) = и(х), получаем, что ф(х) | е -f(x)u(x), т.е. (/(х))-1 = и(х). ?

Следствие. Каждый ненулевой элемент кольца Р[х / ф(х) обратим (т.е. Р[х] / Ф(х) — поле) <=> многочлен ф(х) неприводим над Р. t>

  • [1] Яблонский С. В. Введение в дискретную математику. М.: Наука, 1979.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >