8. Алгоритм Евклида. Нод и нок многочленов. Линейное представление нод.

Определение 10. Пусть F – поле, f(x), g(x) F[x]. Многочлен d(x) F[x] называется наибольшим общим делителем многочленов f(x) и g(x) (или коротко, НОД f(x) и g(x)) и обозначается d(x)=(f(x),g(x)), если выполняются два условия:

1) d(x) – общий делитель многочленов f(x) и g(x), т.е. и ;

2) d(x) кратен любому общему делителю многочленов f(x) и g(x), т.е. если и , то .

Определение 11. Пусть K – ассоциативно-коммутативное кольцо с единицей. Элементы a и b кольца K называются ассоциированными в K и обозначаются a∼b, если и .

Лемма 1. Пусть F – поле, f(x), g(x) F[x]. Тогда f(x)∼g(x)  F^#: f(x)=⋅g(x).

Лемма 2. Пусть F – поле, f(x), g(x),q(x),r(x) F[x], g≠0, и f=g·q+r (1). Тогда НОД многочленов f и g и НОД многочленов g и r ассоциированы, т.е. (f,g)∼(g,r).

Доказательство. Пусть d₁=(f, g), d₂=(g, r).

Так как и , то из (1)  и d₁ – общий делитель g и r (2)

Так как и , то из (1)  и d₂ – общий делитель f и g (3).

Из (2) и (3) следует, что d₁∼d₂. Лемма доказана.

Лемма 3. НОД двух многочленов определяется однозначно с точностью до ассоциированности.

Алгоритм Евклида для нахождения НОД многочленов f и g.

Пусть F – поле, f(x), g(x) F[x], g(x)≠0.

Делим с остатком f на g; если остаток r₁≠0, то делим с остатком g на r₁, и т.д. (каждый раз делим делитель на остаток):

(4.1)

(4.2)

(4.3) (4)

...

(4.k)

(4.k+1)

Последовательность равенств (4) называется алгоритмом Евклида.

Покажем, что процесс деления в алгоритме Евклида является конечным, то есть через конечное число k шагов очередной остаток r_k+1=0. Рассмотрим последовательность (5).

Так как (5) – убывающая последовательность целых неотрицательных чисел, она является конечной и содержит число членов . Следовательно, процесс деления с остатком в алгоритме Евклида (4) конечен и через конечное число k шагов будет получен очередной остаток r_k+1 такой, что deg r_k+1<0. То есть, r_k+1=0.

Пусть r_k - последний отличный от нуля остаток. Покажем, что (f,g)∼ r_k. Действительно, из равенств (4) по лемме 2 получим

(f,g)∼( g, r₁ )∼( r₁, r₂ )∼…∼ ( r_k-1, r_k )∼ r_k.

Значит, НОД многочленов f и g ассоциирован с последним ненулевым остатком в алгоритме Евклида (4).

Замечание. Так как по лемме 3 НОД двух многочленов определяется однозначно с точностью до ассоциированности, то существует множество ассоциированных между собой НОД, отличающихся, согласно лемме 1, лишь скаляром F^#. Из всех возможных НОД выберем тот, который нормирован, т.е. имеет старший коэффициент 1, и будем обозначать его далее через (f,g) или НОД(f,g).

Т.е. НОД многочленов f и g равен нормированному последнему ненулевому остатку в алгоритме Евклида (4).

Определение 12. Пусть F – поле, f(x), g(x) F[x]\{0(x)}. Многочлен m(x) F[x] называется наименьшим общим кратным многочленов f(x) и g(x) (или коротко, НОК f(x) и g(x)) и обозначается m(x)=[f(x),g(x)], если выполняются два условия:

1) m(x) – общее кратное многочленов f(x) и g(x), т.е. и ;

2) m(x) делит любое общее кратное многочленов f(x) и g(x), т.е. если и , то .

Лемма 4. НОК двух многочленов определяется однозначно с точностью до ассоциированности.

Теорема 9. Пусть F – поле, f(x), g(x) F[x] \{0(x)}. Для нахождения НОК многочленов f и g справедлива следующая формула: [f,g]= .

Теорема 10 (теорема о линейном представлении НОД). Пусть F – поле, f(x), g(x) F[x], g≠0, d=(f,g). Тогда

(6) – линейное представление НОД f(x) и g(x).

Доказательство. Рассмотрим алгоритм Евклида (4). Выражая из последнего равенства (4) и заменяя их значениями из предыдущих равенств (4), через конечное число шагов получим , где .

Теорема доказана.

Аналогично определениям 10 и 11 можно дать определение НОД и НОK произвольного конечного количества многочленов f₁, f₂, …, f_n F[x]. Для их нахождения используется теорема

Теорема 11. Пусть F – поле, f₁, f₂, …, f_n F[x] \{0(x)}. Для нахождения НОД и НОK многочленов f₁, f₂, …, f_n справедливы формулы:

(f₁, f₂, …, f_n)=(…(( f₁, f₂), f₃)…, f_n)

[f₁, f₂, …, f_n]=[…[[ f₁, f₂], f₃]…, f_n].