Материал: Методические указания для организации самостоятельной работы по дисциплине «Алгебра и геометрия». Майорова С.П., Завгородний М.Г

Справедлива теорема о линейном представлении НОД.

Теорема. Если a(x), b(x) P[x] и d (x) НОД (a(x),b(x)) ,

то существуют многочлены u(x), v(x) P[x] такие, что d (x) a(x)u(x) b(x)v(x) .

Нахождение НОД нескольких многочленов сводится к нахождению НОД двух многочленов. Так, для трех много-

членов имеем: НОД(f1, f2 , f3 ) НОД НОД(f1, f2 ), f3 . Аналогично для четырех многочленов: НОД(f1, f2 , f3, f4 )

НОД НОД(f1, f2 ), f3, f4 =НОД НОД НОД(f1, f2 ), f3 , f4 .

Как видно из приведенных формул, при вычислении НОД нескольких многочленов можно заменять любую пару многочленов на их наибольший общий делитель.

Вопросы для самоконтроля

1)Что называют наибольшим общим делителем многочленов?

2)Как найти наибольший общий делитель двух многочленов? Опишите алгоритм Евклида.

3)Как найти наибольший общий делитель трех многочленов?

4)Сформулируйте теорему о линейном представлении наибольшего общего делителя.

5) Какие многочлены называются взаимно простыми? Приведите примеры.

Примеры решения задач

Задача 1. Найти НОД многочленов f (x) x3 x2 2x 2

x 2 r1

9

поэтому НОД ( f , g) 3 , или переходя к унитарному многочлену, имеем НОД ( f , g) 1 .

В кольце 3[x] остаток r2 3 0(mod3) , поэтому последним ненулевым остатком в этом кольце многочленов является r1 , а значит НОД ( f , g) x 2 .

Задача 2. В кольце [x] найти НОД многочленов

f (x) x5 2x4 x3 7x2 x 6 и g(x) x4 4x3 4x2 3x 14 .

Решение. Выполняя цепочку последовательных делений алгоритма Евклида, имеем:

2x4 3x3 4x2 13x 62x4 8x3 8x2 6x 28

5x3 12x2 7x 34( r1)

Для удобства дальнейших вычислений умножим g (x) на 5. Это не повлияет на окончательный ответ, так как 5 - обратимый элемент кольца [x] . Чтобы избежать дробных коэф-

фициентов, один из промежуточных остатков также умножим на 5. Получим:

10

8x3 27x2 19x 70 ( 5)

40x3 135x2 95x 350 40x3 96x2 56x 272

39x2 39x 78( r2 )

В этой схеме знак // разделяет различные частные. Разделим

17x2 17x 34 17x2 17x 34

0

Итак, в кольце [x] последний ненулевой остаток - это r2 , тогда переходя к унитарному многочлену, получим

НОД ( f , g) 391 r2 x2 x 2 .

Отметим, что домножение промежуточного остатка на число возможно лишь в случае, когда не ставится задача об отыскании линейного представления НОД, поскольку при таком домножении изменяется частное.

Задача 3. В кольце 3[x] найти НОД многочленов

f (x) x5 2x4 2x3 x2 x 2 , g(x) x5 x3 x

и получить линейное представление НОД.

Решение. Выполним цепочку последовательных делений, сразу преобразуя коэффициенты (напомним, что кольцо

3 состоит из трех элементов - это 0, 1, 2):

11

x4 2x3

x4 2x3 2x2 1

x2 2( r2 )

Итак, НОД ( f , g) r3(x) x 2 .

Для получения линейного представления НОД найдем многочлены u(x), v(x) 3[x] такие, что НОД ( f , g) u(x) f (x) v(x)g(x) . Запишем алгоритм Евкли-

да в сокращенной форме: f (x) g(x) 1 r1(x) ,

g(x) r1(x) (2x 2) r2 (x) , r1(x) r2 (x) (2x2 x) r3(x) .

Из этих равенств выразим остатки, начиная с последнего: r3(x) r1(x) r2 (x) (2x2 x) ,

r2 (x) g(x) r1(x) (2x 2) , r1(x) f (x) g(x) .

12

Будем последовательно исключать остатки из выражений для r3 и r2 . Для остатка r3 (x) НОД ( f , g) получим:

r3 (x) r1(x) r2 (x) (2x2 x)

r1(x) (g(x) r1(x) (2x 2)) (2x2 x)

g(x) (2x2 x) r1(x) (x3 2x 1)

g(x) (2x2 x) ( f (x) g(x)) (x3 2x 1)

f (x) (x3 2x 1) g(x) (x3 2x2 1)

f (x) (x3 2x 1) g(x) (2x3 x2 2) .

Таким образом, линейное представление НОД найдено, а

3) Выясните, являются ли взаимно простыми многочлены f , g [x] , если: а) f (x) x3 3x2 2x 1, g(x) 2x2 x 1; б) f (x) 2x3 3x2 x 2 , g(x) x4 2x2 3x 4 .

13