Неприводимые многочлены. Алгоритм Евклида для многочленов

Неприводимый многочлен — многочлен, неразложимый на нетривиальные (неконстантные) многочлены. Неприводимые многочлены являются неприводимыми элементами кольца многочленов.

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

Многочлен называется абсолютно неприводимым, если он неприводим над алгебраическим замыканием поля коэффициентов. Абсолютно неприводимые многочлены одной переменной ― это многочлены 1-й степени и только они. В случае нескольких переменных существуют абсолютно неприводимые многочлены сколь угодно высокой степени — например, любой многочлен вида абсолютно неприводим.

Корни неприводимого многочлена называются сопряженными.

Алгоритм Евклида для многочленов. Алгоритм Евклида позволяет найти наибольший общий делитель двух многочленов, т.е. многочлен наибольшей степени, на который делятся без остатка оба данных многочлена.
Алгоритм основан на том факте, что для любых двух многочленов от одного переменного, f(x) и g(x), существуют такие многочлены q(x) и r(x), называемые соответственно частное и остаток, что
f(x) = g(x)∙q(x) + r(x), (*)
при этом степень остатка меньше степени делителя, многочлена g(x), и, кроме того, по данным многочленам f(x) и g(x) частное и остаток находятся однозначно. Если в равенстве (*) остаток r(x) равен нулевому многочлену (нулю), то говорят, что многочлен f(x) делится на g(x) без остатка.
Алгоритм состоит из последовательного деления с остатком сначала первого данного многочлена, f(x), на второй, g(x):

f(x) = g(x)∙q1(x) + r1(x), (1)
затем, если r1(x) ≠ 0, – второго данного многочлена, g(x), на первый остаток – на многочлен r1(x):
g(x) = r1(x)∙q2(x) + r2(x), (2)
далее, если r2(x) ≠ 0, – первого остатка, r1(x), на второй остаток, r2(x):
r1(x) = r2(x)∙q3(x) + r3(x), (3)
затем, если r3(x) ≠ 0, – второго остатка на третий:
r2(x) = r3(x)∙q4(x) + r4(x), (4)
и т.д. Поскольку на каждом этапе степень очередного остатка уменьшается, процесс не может продолжаться бесконечно, так что на некотором этапе мы обязательно придем к ситуации, когда очередной, n + 1-й остаток rn + 1 равен нулю:

rn–2(x) = rn–1(x)∙ qn(x) + rn(x), (n)
rn–1(x) = rn(x)∙ qn+1(x) + rn+1(x), (n+1)
rn+1(x) = 0. (n+2)
Тогда последний не равный нулю остаток rn и будет наибольшим общим делителем исходной пары многочленов f(x) и g(x).
Действительно, если в силу равенства (n + 2) подставить 0 вместо rn + 1(x) в равенство (n + 1), затем – полученное равенство rn – 1(x) = rn(x)∙qn + 1(x) вместо rn – 1(x) – в равенство (n), получится, что rn – 2(x) = rn(x)∙qn + 1(x) qn(x) + rn(x), т.е. rn – 2(x) = rn(x)(qn + 1(x) qn(x) + 1), и т.д. В равенстве (2) после подстановки получим, что g(x) = rn(x)∙Q(x), и, наконец, из равенства (1) – что f(x) = rn(x)∙S(x), где Q и S – некоторые многочлены. Таким образом, rn(x) – общий делитель двух исходных многочленов, а то, что он наибольший (т.е. наибольшей возможной степени), следует из процедуры алгоритма.
Если наибольший общий делитель двух многочленов не содержит переменную (т.е. является числом), исходные многочлены f(x) и g(x) называются взаимно-простыми.