Математическая логика и теория алгоритмов. Стенюшкина В.А. - 91 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

5.1 Кольцо полиномов от одной переменной
Пусть J-область целостности /8/, x - некоторый символ, тогда выражение
вида
P(x)=a
n
x
n
+a
n-1
x
n-1
+…+a
1
x+a
0
, (5.1)
где
a
i
∈
J, i=0.. n, называется полиномом от x над J. Полином можно за-
дать набором его коэффициентов
(a
n
, … , a
0
). Два полинома называются равны-
ми, если они заданы одинаковыми наборами коэффициентов. Подвыражение
вида
a
i
x
i
называется членом i-той степени. Коэффициент при x
n
называется
старшим коэффициентом полинома, если он отличен от нуля, то n называется
степенью полинома, если равен единице, то полином называется нормирован-
ным. На множестве полиномов над
J введем операцию суммирования и муль-
тисуммирования, по обычным правилам, то есть, если
P(x), Q(x) заданы набо-
рами
(a
n
, … , a
0
), (b
n
, … , b
0
) соответственно, то сумма P(x)+Q(x) зададим на-
бором
(a
l
+b
l
, … , a
0
+b
0
), l=max(m,n), а произведение P(x) ⋅Q(x) набором
(
i
ji
i
nmji
ii
baba
∑∑
=++=+ 0
,...,
). Таким образом, множество полиномов над J становится
нетривиальным коммуникативным кольцом. Предположим, что P(x)
≠
0, Q(x)
≠
0
(не есть полиномы вида 0x
k
+ … + 0 при некотором k), а m, n –их соответству-
ющие степени. Тогда
a
m
≠
0, b
n
≠
0 и в силу их принадлежности области целостно-
сти
J их произведение a
m
b
n
≠
0. Поскольку a
m
b
n
есть старший k коэффициент по-
линома
P(x)Q(x), этот полином не есть 0. Из этого следует что множество поли-
номов от
x над областью целостности J само является областью целостности.
Обозначим её через
J[x]. Эта область содержит, в частности J и x.
Примечание. Если рассматривать полином как отображение
x
∈
J в
P(x)
∈
J[x], то в случае конечной области J не равные между собой полиномы
могут иногда осуществлять одно и тоже отражение. Например, если
J[x]=Z
2
[x],
то различные полиномы
P
1
(x)=x
3
-1 и P
2
(x)=x
5
-1 равны как функции:
P
1
(0)=P
2
(0)=1, P
1
(1)=P
2
(1)=0.
5.2 Делимость
Говорят, что полином P
1
(x) делится на полином P
2
(x), или P
2
(x) есть де-
литель полинома
P
1
(x), если существует полином Q(x) такой, что
P
1
(x)=P
2
(x)
⋅
Q(x). Если P
1
(x)
≠
0 как полином, то степень P
2
(x) не превосходит
степени
P
1
(x).
Основная теорема Пусть
P
1
(x)=
∑
=
m
i
i
i
xa
0
, P
2
(x)=
i
n
i
i
xb
∑
=0
≠
0 – многочлены
степени
m, n соответственно над областью целостности J
1
и пусть коэффициент
b
n
обратим в J. Тогда существуют единственные полиномы Q(x), R(x)
∈
J[x], на-
зываемые частным и остатком соответственно, для которых
P
1
(x)=P
2
(x)Q(x)+R(x), (5.2) 
                   5.1 Кольцо полиномов от одной переменной

                   Пусть J-область целостности /8/, x - некоторый символ, тогда выражение
вида
                   P(x)=anxn+an-1xn-1+…+a1x+a0,                              (5.1)

       где ai ∈ J, i=0.. n, называется полиномом от x над J. Полином можно за-
дать набором его коэффициентов (an, … , a0). Два полинома называются равны-
ми, если они заданы одинаковыми наборами коэффициентов. Подвыражение
вида aixi называется членом i-той степени. Коэффициент при xn называется
старшим коэффициентом полинома, если он отличен от нуля, то n называется
степенью полинома, если равен единице, то полином называется нормирован-
ным. На множестве полиномов над J введем операцию суммирования и муль-
тисуммирования, по обычным правилам, то есть, если P(x), Q(x) заданы набо-
рами (an , … , a0 ), (bn , … , b0 ) соответственно, то сумма P(x)+Q(x) зададим на-
бором (al+bl, … , a0+b0 ), l=max(m,n), а произведение P(x) ⋅Q(x) набором
(     ∑a b ,
    i + j =m+ n
                  i i   ... ,    ∑ a b ).
                                i + j =0
                                           i i   Таким образом, множество полиномов над J становится

нетривиальным коммуникативным кольцом. Предположим, что P(x)≠0, Q(x)≠0
(не есть полиномы вида 0xk + … + 0 при некотором k), а m, n –их соответству-
ющие степени. Тогда am≠0, bn≠0 и в силу их принадлежности области целостно-
сти J их произведение ambn≠0. Поскольку ambn есть старший k коэффициент по-
линома P(x)Q(x), этот полином не есть 0. Из этого следует что множество поли-
номов от x над областью целостности J само является областью целостности.
Обозначим её через J[x]. Эта область содержит, в частности J и x.
       Примечание. Если рассматривать полином как отображение x∈J в
P(x)∈J[x], то в случае конечной области J не равные между собой полиномы
могут иногда осуществлять одно и тоже отражение. Например, если J[x]=Z2[x],
то различные полиномы P1(x)=x3-1 и P2(x)=x5-1 равны как функции:
P1(0)=P2(0)=1, P1(1)=P2(1)=0.

                   5.2 Делимость

       Говорят, что полином P1(x) делится на полином P2(x), или P2(x) есть де-
литель полинома P1(x), если существует полином Q(x) такой, что
P1(x)=P2(x) ⋅ Q(x). Если P1(x) ≠0 как полином, то степень P2(x) не превосходит
степени P1(x).
                                                                  m                n
                   Основная теорема Пусть P1(x)= ∑ ai x i , P2(x)= ∑ bi x i ≠0 – многочлены
                                                                  i =0            i =0

степени m, n соответственно над областью целостности J1 и пусть коэффициент
bn обратим в J. Тогда существуют единственные полиномы Q(x), R(x)∈J[x], на-
зываемые частным и остатком соответственно, для которых

                   P1(x)=P2(x)Q(x)+R(x),                                  (5.2)

Страницы