Если d(x) – наибольший общий делитель многочленов f(x) и g(x) из P[x], то в том же кольце P[x] найдутся многочлены U(x) и V(x) такие, что f(x) × U(x) + g(x) × V(x) = d(x).

Заметим, что Теорема 4.3.(о линейном представлении НОД двух многочленов) распространяется на n – ое количество многочленов, т.е.

Теорема 4.4. (о линейном представлении НОД многочленов)

Пример 4.4. Для многочленов f(x) = 2x − 1 Î R[x], g(x) = х + 2 Î R[x] их НОД d(x) = (f(x), g(x)) = 1, т.е. многочлены f(x) и g(x) являются взаимно простыми.

Свойства взаимно простых многочленов из кольца многочленов P[x].

Свойство 4.2.Если (f₁(x), f₂(x), f₃(x),…f_n(x)) = d(x), то .

Свойство 4.3.Если (f(x) × j(x)) h(x) и (f(x), h(х)) =1, то j(x) h(x).

Пример 4.5. Найдём наибольший общий делитель многочленов

Задача1. Найти наибольший общий делитель многочленов f(x) = x 4 + 3x 3 –x 2 –4x –3 и g(x) = 3x 3 + 10x 2 + 2x –3.

Применяя алгоритм Евклида в данном примере, мы будем вынуждены проводить вычисления с дробными коэффициентами многочленов, что, естественно, затрудняет и замедляет процесс поиска наибольшего общего делителя данных многочленов. Но так как НОД определяется с точностью до множителя нулевой степени, в некоторых случаях можно избежать дробных коэффициентов. Будем умножать делимое, делитель, остаток на любое не равное нулю число, т.е. заменять многочлены на ассоциированные с ними, но так, чтобы равенство f(x) = g(x) × q(x) + r(x) (Теорема 3.1.) не нарушалось.

Делим f(x) на g(x) согласно алгоритму Евклида, предварительно умножив f(x) на 3.

Наибольший общий делитель многочленов f(x) = x 4 + 3x 3 –x 2 –4x –3 и g(x) = 3x 3 + 10x 2 + 2x –3 – это последний, не равный нулю остаток r₂(x) = 9x + 27, или ассоциированный с ним, более простой многочлен r₂(x) = x + 3.

Задача2. Для многочленов из задачи 1 над полем рациональных чисел найти многочлены U(x) и V(x) над тем же полем, чтобы имело место равенство f(x) × U(x) + g(x) × V(x) = d(x), где d(x) = ( f(x), g(x) ).

g(x) = (– )r₁(x)) × q₂(x) + r₂(x);

– r₁(x) = r₂(x) × q₃(x).

d(x) = (f(x), g(x)) = x + 3 = r₂(x), выражаем r₂(x) из равенства, которое содержит последний, не равный нулю остаток: r₂(x) = g(x)- (– )r₁(x)) × q₂(x), и подставляем в полученное нами равенство, т.е.

d(x) = (f(x), g(x)) = x + 3 = r₂(x) = × (g(x) – (– )r₁(x) × q₂(x)) = g(x) + r₁(x) × q₂(x), теперь выражаем r₁(x) из предыдущего равенства: r₁(x) = 3f(x) – g(x) × q₁(x) и подставляем в полученное нами равенство, т.е.

d(x) = (f(x), g(x)) = x + 3 = r₂(x) = × (g(x) – (– )r₁(x)) × q₂(x)) = g(x) + r₁(x) × q₂(x) = g(x) + (3f(x) – g(x) × q₁(x)) × q₂(x) = g(x) + f(x) × q₂(x) – g(x) × q₁(x) × q₂(x) = f(x) × q₂(x) + ( g(x) – g(x) × q₁(x) × q₂(x)) = q₂(x) × f(x) + g(x) ( – q₁(x) × q₂(x)) =f(x) × [ q₂(x)] + g(x) × [ – q₁(x) q₂(x)].

Итак: f(x) × [ q₂(x)] + g(x) × [ – q₁(x) q₂(x)] = d(x) = x + 3.

Т. е. функции U(x) и V(x) найдены: U(x) = q₂(x) = (3x –5) = х– 1, V(x) = – q₁(x) q₂(x) = – (x – ) (3x –5) = – ( х 2 –2х) = – х 2 + х.

Тогда d(x) = x + 3 = f(x) × ( х– 1) + g(x) × (– х 2 + х).

f(x) × ( х– 1) + g(x) × (– х 2 + х) = (x 4 + 3x 3 –x 2 –4x –3) × ( х– 1) + (3x 3 + 10x 2 + 2x –3) × (– х 2 + х) = x + 3. (Сделайте проверку самостоятельно!).

1)Составьте 3 – 4 многочлена, являющихся делителями многочлена f(x) ;

2)Составьте 3 – 4 многочлена, являющихся делителями многочлена g(x) ;

3)Составьте 2 – 3 многочлена, являющихся общими делителями многочленов f(x) и g(x);

4)Составьте многочлен,являющийся наибольшим общим делителем многочленов f(x) и g(x)

и убедитесь в том, он удовлетворяет всем требованиям, содержащимся в определении наибольшего общего делителя многочленов.

85.С помощью алгоритма Евклида найдите нормированный наибольшийобщийделитель d(x) многочленов :

86.С помощью алгоритма Евклида найдите наибольшийобщийделитель d(x) многочленов f(x) и g(x), применяя при этом два варианта вычислений: I– обычное деление многочленов « уголком »; II –используя для удобства деления предварительное умножение делимого на некоторое постоянное число и сокращение остатков на постоянное число. Сравните результаты.

В примерах 87 – 97с помощью алгоритма Евклида найдите нормированный наибольшийобщийделитель d(x) многочленов f(x) и g(x) .