CONTIN1 (1016707), страница 3
Текст из файла (страница 3)
(mod f(x)). Определим на этих классах сложение и умножение: [a(x)]+[b(x)]=[a(x)+b(x)] и [a(x)].[b(x)]=[a(x).b(x)]
следовательно множество с введенными операциями – кольцо.
Доказательство:
-
Введенные операции определены корректно, т.е. результат не зависит от выбора элемента из класса:
a1(x), a2(x) [a(x)] значит [a(x)]=[a1(x)]=[a2(x)],
аналогично для b1(x), b2(x) [b(x)]. По теореме о конгруэнции [a1(x)+b1(x)]=[a2(x)+b2(x)], а [a1(x)+b1(x)]=[a1(x)]+[b1(x)] следовательно [a1(x)]+[b1(x)]=[a2(x)]+[b2(x)].
Аналогично для умножения. ч.т.д.
-
Выполнение аксиом кольца для многочлена (
,+,) вытекает из их справедливости в кольце многочленов P[x].
Из [a(x)] выберем представителя и будем работать с ним, отождествляя результат со всем классом.
Опр.: Множество многочленов a1(x), a2(x),…,at(x) – полная система представителей классов эквивалентностити относительно отношения (mod f(x)) если:
-
для любого jk aj(x) не сравним с ak(x)(mod f(x))
Утв.: Пусть f(x)=xn+ jxj, т.е. унитарный многочлен степени n. Множество многочленов вида {
jxj, cj
P, j=
} – ПСПf(x) – полная система представителей для данного отношения эквивалентности.
Доказательство: каждый класс однозначно определяется своими представителями вида jxj, а т.к. cj
P, то каждый класс сможем выбрать q способами, следовательно всего классов qn.
Теорема: Многочлен a(x) – обратим в кольце
(a(x),f(x))=1 (Под обратимостью многочлена a(x) понимаем, что существует
[b(x)] : [a(x)].[b(x)]=[e])
Доказательство:
" " Существуют u(х), v(х) : a(x)u(x)+f(x)v(x)=1
Разделим на f(x) и возьмем остатки от деления:
resf(x)(a(x).u(x))=1, следовательно a(x).u(x) 1 (mod f(x)), таким образом a(x) – обратим;
a(x)= jxj. ] (a(x),f(x))=d(x), deg
<deg f(x);
и a(x) неэквивалентны 0 (mod f(x)), значит a(x) – делитель нуля, следовательно он необратимый элемент кольца (по теореме) – противоречие. ч.т.д.
Следствие: Множество - поле
когда многочлен f(x) – неприводим.
Доказательство: переходим к представлению
jxj, deg f(x)=n
" " Если f(x) – неприводим, то многочлен f(x) взаимопрост с любым ненулевым многочленом меньшей степени, следовательно по доказанной теореме c(x) – обратим:
(c(x),f(x))=1 и jxj
0, т.е. любой ненулевой элемент обратим,
" " Если f(x) – приводим, т.е. f(x)=f1(x).f2(x), где 0<deg f1(x)<deg f2(x)<deg f(x) значит f1(x).f2(x)=0 (mod f(x)) , т.е. f1(x) – делитель нуля, следовательно
- не поле – противоречие. ч.т.д.
Корни многочленов над конечным полем и их свойства
Опр.: - значение многочлена a(x) на элементе α из поля.
Опр.: Если для некоторого многочлена a(x) над полем Р и элемента ? из Р выполнено условие a(α)=0, то α – κорень многочлена a(x)
Теорема (Безу): Пусть a(x) 0 многочлен над полем Р. α – κорень a(x)
(x-α)|a(x).
Доказательство:
" " a(x)=q(x)(x-α)+r(x), deg r(x)<1 значит r(x)=c
P
(если deg=0, то const; если deg=- , то 0).
a(α)=q(α)(α-α)+c, где a(α)=0 по условию, значит с=0 и a(x)=q(x)(x-α), следовательно (x-α)|a(x)
" " a(x)=q(x)(x-α); a(α)=q(α)(α-α); a(α)=0 значит α – корень. ч.т.д.
Опр.: Кратность корня α – наибольшее значение r : r= α
Замечание: Если многочлен имеет корень в поле, то он приводим (обратное неверно)
Утв.: Многочлен a(x), deg a(x) 3 – неприводим над полем
не имеет в этом поле корней.
Доказательство:
-
Многочлен первой степени неприводим (очевидно)
-
Пусть deg a(x)=3 (для второй аналогично). Докажем: приводим
есть корни.
" " - по теореме Безу (см. замечание)
" " a(x) – приводим, значит a(x)=b(x)c(x), где 0<deg b(x)<3, 0<deg c(x)<3,
причем deg b(x)+deg c(x)=3, следовательно один из них многочлен первой степени.
Пусть deg b(x)=1, тогда b(x)=sx+t, s 0 и x=-
- корень b(x), а a(x)=b(x)c(x) , следовательно x=-
- корень a(x). ч.т.д.
Пример: GF(2)[x]. (x2+x+1)2 – приводим, но корней не имеет в поле GF(2); deg(x2+x+1)2=4
Опр.: Пусть a(x) 0 над полем Р. Тогда многочлен вида
a'(x)= - производная многочлена a(x).
Свойства производной многочлена:
-
(a(x)+b(x))'=a'(x)+b'(x)
-
(a(x)b(x))'=a(x)b'(x)+a'(x)b(x)
Опр.: Если кратность корня многочлена равна 1, то корень – простой.
Теорема: Пусть a(x) 0 над полем Р, значит множество его кратных (т.е. не простых) корней совпадает с множеством корней NOD(a(x),a'(x))
Доказательство: Пусть α – кратный корень. Тогда
a'(x)=r(x-α)r-1g(x)+(x-α)rg'(x)=(x-α)r-1[rg(x)+(x-α)g'(x)]
значит α – корень a'(x), следовательно (x-α)|a(x), (x-α)|a'(x), тогда (x-α)|(a(x),a'(x)).
" " от противного: если корень простой, то пусть α – простой корень. Тогда a(x)=(x-α)g(x), g(α)
0, т.к. простой.
a'(x)=g(x)+(x-α)g'(x);
a'(α)=g(α)+(α-α)g'(α), где g(α) 0, (α-α)=0 значит α – не корень a'(x). Следовательно (x-α)†a'(x) и не делит NOD, т.е. не является его корнем. ч.т.д.
Теорема: Над любым полем существует бесконечное число неприводимых многочленов
Доказательство: пусть существует конечное число N неприводимых многочленов над P.
Пусть f1(x), f2(x),…,fN(x) – все неприводимые многочлены над Р.
F(x)=f1(x).f2(x). ….fN(x)+1, тогда существует многочлен fj(x)|F(x), т.е. F(x) – либо приводим, либо совпадает с fj(x). Тогда F(x)=0 (mod fj(x)) значит 1=0 (mod fj(x)) и fj(x)|1 – противоречие, т.к. degfj(x) 1 следовательно существует бесконечное число неприводимых многочленов. ч.т.д.
Неприводимые многочлены над числовым полем С, полем действительных чисел R и полем рациональных чисел Z
Теорема (Гаусса): Любой многочлен над полем С имеет в этом поле корень.
Следствие: Над полем С неприводимы многочлены только первой степени.
Доказательство: Если deg 2, то имеется корень α, тогда (x-α)|a(x), следовательно многочлен приводим.
Теорема: Над полем R неприводимы многочлены первой степени и второй степени с D<0 и только они.
Доказательство:
1) α=a+ib, =a-ib, где
,
, т.к. α=a+ib, β=c+id
α.β=(ac-bd)+i(ad+bc)
=(ac-bd)-i(ad+bc);
=(a-ib)(c-id)=(ac-bd)-i(ad+bc)
] a(x) R(x), deg a(x)>1; a(x)=
; ] α=a+ib – его корень
=0=
= =
=
, т.к. ak
R
- тоже корень а(х); т.о. если а(х) – имеет корень α
C, то (x-α)(x-
)|a(x)
x2-(α+
)x+α
=x2-
x+
- многочлен с действительными коэффициентами.
2) ] a(x) – неприводим над полем R и не имеет действительных корней. По теореме Гаусса у него комплексный корень
(x-α)(x-
)|a(x)
действительный полином [x2-2Reαx+|a|]|a(x)
если deg a(x)
3, то он автоматически приводим.
3) Для deg a(x)=2 – неприводим над R, т.е. не имеет действительных корней D<0, т.к. отсутствие действительных корней над полем R эквивалентно неприводимости.
Утв.: ] f(x) – неприводимый многочлен над полем R: x2+1, deg f(x)=2 C
- кольцо, а т.к. f(x) – неприводим
поле.
Доказательство: ] f(x)=x2+1, i – его корень
={a+ib|a; b
R}
(для любого f(x) – неприводимого многочлена, вместо i – его корень)
Опр.: Многочлен a(x) над кольцом Z (с целыми коэффициентами) – примитивный, если множество его коэффициентов взаимно просто в совокупности.
Опр.: Два числа взаимно просты, если для любого простого числа одно из них на него не делится.
Опр.: Множество (a0,…,an) – взаимно просто в совокупности, если для p – простого
k, 0
k
n : p†ak
Пример: (6,10,15)=1, т.е. NOD совокупности равен 1.
Опр.: Многочлены a(x), b(x) над полем Q – ассоциированные, если : a(x)=c.b(x).
Утв.: Для многочлена над полем Q
! ассоциированный с ним примитивный многочлен с целыми коэффициентами.
Доказательство:
1. a(x)= , ak=
, pk,qk
. (pk,qk)=1.
NOK(qk; k= )=u
]b(x)=ua(x) – с целыми коэффициентами, т.е.
Z[x].
NOD =v
]c(x)=
b(x)=
a(x)
a(x), c(x) – ассоциированные.
=1
c(x) – примитивный, т.е.
a(x)
ассоциативный с ним примитивный с(х).
2. Докажем единственность: ] два таких многочлена: a(x)=
=
; c(x), c'(x) – примитивные многочлены с целыми коэффициентами
c'(x)=
c'(x)= ; c(x)=
ck'=wck, w
Q. w=
, (α,β)=1; βck'=αck,
k.
¦ ¦
α=β, (α,β)=1
(α,β)=1=α=β
w=
=1
c'(x)=c(x) ч.т.д.
Лемма: ]a(x), b(x) – примитивные многочлены с целыми коэффициентами (старший коэффициент >0) их произведение – примитивный многочлен, т.е. a(x), b(x) – примитивные многочлены
a(x)b(x) – примитивный многочлен.
Доказательство: a(x)b(x)= . Покажем, сто для произвольного р – простого найдется ск : р†ск.