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

UptoLike

ВУЗ: 

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

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

Рубрика: 

70
4
0
4-14
21
0 0
00
4-
14
21
4
0 0 8
-
14
2 -7
Таким образом, Q(x)=7x
2
+4, R(x)=-14x
2
+2x-7.
5.4 Наибольшие общие делители полиномов над полем
Определение. Евклидова область есть область целостности
I с функцией
степени
S: I
→
N такой, что выполняются условия:
1
;pp),p(S)pp(S 0
21121
≠
≥
2 Для любых 0
221
≠
∈ p,Ipp , в I существуют элементы q, r, обладаю-
щие свойством евклидовости, то есть
0 или
221
=
<
+
=
r)p(S)r(S,rqpp
.
Примеры
1
)
p
(
)
p
(
S
,
Z
I
== - евклидова область, так как для 0
221
≠
∈ p,Zp,p ,
сущеествуют
q, r такие, что
221
0 pr,rqpp
<
≤
+
=
. Кроме того, если I – по-
ле, то
)
)
x
(
p
(
^
)
)
x
(
p
(
S
x
[
I
= c - евклидова область, потому что для любых
0
221
≠∈ )x(p],x[I)x(p),x(p в I(x) существуют единственные полиномы q(x),
r(x)
такие, что
)x(p^)x(r^),x(r)x(q)x(p)x(p
221
<
+
=
.
2
I=Q (поле рациональных чисел), S(p) = (p) не является евклидовой об-
ластью, потому что
S(5⋅(1/5)) = S(1) < S(5), и первое условие определения евк-
лидовой области не выполняется. Кольцо
Z[x], S(p(x)) = ^p(x) также не является
евклидовой областью, так как если, например, разделить
25на 1247
335
++++
x
x
x
x
, то частное не принадлежит кольцу Z[x].
Определение Говорят, полином p
1
(x) делится на полином p
2
(x) если
∃q(x): p
1
(x)=p
2
(x)q(x). Запись: p
2
(x)|p
1
(x). Если p1(x)?0, то
∧
p
2
(x)≤
∧
p
1
(x).
Определение Пусть 0
221
≠
∈
)x(p],x[I)x(p),x(p , I – область целост-
ности. Тогда наибольшим общим делителем полиномов
р
1
(х), р
2
(х) называется
полином
p
h
(x)
∈
I[x], удовлетворяющий условиям:
а)
p
h
(x) / р
1
(х) и p
h
(x) / р
2
(х);
б) если
q(x) / р
1
(х) и q(x) / р
2
(х), то ^ q(x) <^ p
h
(x) и q(x) < p
h
(x).
Обозначение : НОД
[р
1
(х), р
2
(х)] = p
h
(x). 
                                  70
                          4
                  0
        4-14 21
                  0 0
        00
                  4-
        14 21
                  4
        0 08
                      -
        14 2 -7

       Таким образом, Q(x)=7x2+4, R(x)=-14x2+2x-7.

       5.4 Наибольшие общие делители полиномов над полем

         Определение. Евклидова область есть область целостности I с функцией
степени S: I→N такой, что выполняются условия:
         1 S ( p1 p2 ) ≥ S ( p1 ), p1 p2 ≠ 0;
         2 Для любых p1 p2 ∈ I , p2 ≠ 0 , в I существуют элементы q, r, обладаю-
щие свойством евклидовости, то есть p1 = p2 q + r , S ( r ) < S ( p2 ) или r = 0 .
         Примеры
         1 I = Z , S ( p ) = ( p ) - евклидова область, так как для p1 , p2 ∈ Z , p2 ≠ 0 ,
сущеествуют q, r такие, что p1 = p2 q + r , 0 ≤ r < p2 . Кроме того, если I – по-
ле, то I [ x ] c S ( p( x )) =^ ( p( x )) - евклидова область, потому что для любых
 p1( x ), p2 ( x ) ∈ I [ x ], p2 ( x ) ≠ 0 в I(x) существуют единственные полиномы q(x),
r(x) такие, что p1( x ) = p2 ( x )q( x ) + r( x ), ^ r( x ) <^ p2 ( x ) .
         2 I=Q (поле рациональных чисел), S(p) = (p) не является евклидовой об-
ластью, потому что S(5⋅(1/5)) = S(1) < S(5), и первое условие определения евк-
лидовой области не выполняется. Кольцо Z[x], S(p(x)) = ^p(x) также не является
евклидовой            областью,           так      как   если,       например,  разделить
7 x 5 + 4 x 3 + 2 x + 1 на 5 x 3 + 2 , то частное не принадлежит кольцу Z[x].
         Определение Говорят, полином p1(x) делится на полином p2(x) если
∃ q(x): p1(x)=p2(x)q(x). Запись: p2(x)|p1(x). Если p1(x)?0, то ∧ p2(x) ≤ ∧ p1(x).
         Определение Пусть p1( x ), p2 ( x ) ∈ I [ x ], p2 ( x ) ≠ 0 , I – область целост-
ности. Тогда наибольшим общим делителем полиномов р1(х), р2(х) называется
полином ph(x) ∈ I[x], удовлетворяющий условиям:
         а) ph(x) / р1(х) и ph(x) / р2(х);
         б) если q(x) / р1(х) и q(x) / р2(х), то ^ q(x) <^ ph(x) и q(x) < ph(x).
         Обозначение : НОД[р1(х), р2(х)] = ph(x).

Страницы