Находим наибольший общий делитель заданных полиномов

PolynomialGCD[f[x],g[x],h[x]]

-1+x

Если - наибольший общий делитель многочленов и , то всегда можно подобрать два таких новых многочлена и , что

. (2.1)

Равенство (2.1) называют линейным представлением наибольшего общего делителя.

Многочлены и можно подобрать таким образом, что степень многочлена будет не больше степени многочлена , а степень многочлена - не больше степени многочлена . Сделать это можно, например, методом неопределённых коэффициентов.

Пример 3.3. Найти линейное представление наибольшего общего делителя следующих многочленов

Решение.

Находим наибольший общий делитель заданных полиномов

d[x_]=PolynomialGCD[f[x],g[x]]

1+x

Так как g[x]- многочлен третьей степени, то u[x] будем искать в виде многочлена второй степени; так как f[x] многочлен четвёртой степени, то многочлен v[x] будем искать в виде многочлена третьей степени.

A=Table[a[n-1],{n,1,7}];

d1[x_]=f[x]*u[x]+g[x]*v[x];

T1=Table[Coefficient[d1[x],x,n-1],{n,1,7}];

T2=Table[Coefficient[d[x],x,n-1],{n,1,7}];

T=Table[T1[[n]]ŠT2[[n]],{n,1,7}];

R=Solve[T,A]

a[6]=0;

u[x_]=u[x]/.R[[1]]

v[x_]=v[x]/.R[[1]]

Expand[f[x]*u[x]+g[x]*v[x]]

X

Та же задача может быть решена другим способом. Положим

В левом столбце- последовательность делений, которая разрешена относительно остатков. В правом столбце каждый остаток выражен в виде Мы хотим вычислить и . Очевидно, что , . Сравнивая обе части на м шаге, имеем

Отсюда получается следующая индуктивная процедура вычисления и :

Находим как частное от деления на , затем вычисляем

Покажем, как описанный алгоритм нахождения линейного представления наибольшего общего делителя можно реализовать в системе Mathematica .

Вводим заданные полиномы

Задаём начальные значения параметров цикла

a0[x_]=f[x];a1[x_]=g[x];u0[x_]=1;v0[x_]=0;u1[x_]=0;v1[x_]=1;

q[x_]=PolynomialQuotient[a0[x],a1[x],x];

a2[x_]=a0[x]-a1[x]*q[x];u2[x_]=u0[x]-u1[x]*q[x];v2[x_]=v0[x]-v1[x]*q[x];

Находим коэффициенты линейного представления наибольшего общего делителя u1[x]и v1[x] заданных многочленов и сам наибольший общий делитель a1[x]

While[Length[CoefficientList[a2[x],x]]>0,a0[x_]=a1[x];

a1[x_]=a2[x];q[x_]=PolynomialQuotient[a0[x],a1[x],x];

u0[x_]=u1[x];u1[x_]=u2[x];v0[x_]=v1[x];v1[x_]=v2[x];

a2[x_]=Expand[a0[x]-a1[x]*q[x]];

u2[x_]=Expand[u0[x]-u1[x]*q[x]];

v2[x_]=Expand[v0[x]-v1[x]*q[x]]]

u1[x]

X

v1[x]

a1[x]

Проверяем правильность решения задачи

Simplify[f[x]*u1[x]+g[x]*v1[x]]

Неприводимые многочлены.

Многочлен , отличный от постоянной, называется приводимым над числовым полем , если разлагается на произведение двух многочленов и с коэффициентами из поля , отличных от постоянных.

Если же не может быть разложено на такое произведение, то многочлен называется неприводимым над полем

Произвольный многочлен с коэффициентами из поля может быть записан в следующем виде

, (3.3.1)

где различные многочлены, неприводимые над полем

, -натуральные числа.

Может случиться, что в разложении на неприводимые множители все равны единице. В этом случае говорят, что разлагается на однократные множители.

Говорят, что многочлен входит в с кратностью , если делится на , но не делится на .

Можно доказать, что если неприводимый многочлен входит в с кратностью , то в производную он войдёт с кратностью .

Пусть . Обозначим через произведение всех однократных неприводимых множителей; через -произведение всех двукратных неприводимых множителей , взятых по одному разу, через -произведение всех трёхкратных неприводимых множителей, взятых по одному разу и т.д. Может случиться, что не имеет однократных множителей. Тогда будем считать, что . Вообще, будем считать, что , если не имеет кратных множителей. Если наивысшая кратность множителей многочлена то имеет место соотношение

. (3.3.2)

Процесс построения разложения (3.3.2) называется отделением кратных множителей. Он реализуется по следующему алгоритму.

Находим наибольший общий делитель многочлена и его производной . Можно доказать, что

Наибольший общий делитель многочленов и будет равен

.

Наибольший общий делитель многочленов и будет равен

.

Наконец получим

Далее составляем

Отсюда находим

.

Описанный алгоритм реализуется в системе Mathematica следующим образом.

Пример 3.3.1. Выделить кратные неприводимые множители для многочлена

Решение.

Вводим заданный многочлен

f[x_]=x^8+2*x^7+5*x^6+6*x^5+

8*x^4+6*x^3+5*x^2+2*x+1;

Полагаем g[x] равным заданному многочлену

g[x_]=f[x];

g[x_]=PolynomialGCD[g[x],D[g[x],x]];

d=Append[d,g[x]];

While[Length[CoefficientList[g[x],x]]>1,g[x_]=

PolynomialGCD[g[x],D[g[x],x]];

d=Append[d,g[x]]];