Máximo común divisor polinómico

En álgebra, el MÁXIMO común divisor (frecuentemente abreviado como MCD) de dos polinomios es otro polinomio del grado más alto posible, que es un factor de los dos polinomios originales. Este concepto es análogo al de máximo común divisor de dos enteros.

En el caso importante de polinomios de una sola variable sobre un cuerpo, el polinomio MCD puede ser calculado, como el MCD de dos enteros, mediante el algoritmo de Euclides usando la división polinómica. El polinomio MCD (salvo si se exceptúa la multiplicación por una constante invertible), es único.

La similitud entre el entero MCD y el polinomio MCD permite extender a polinomios de una variable todas las propiedades que se pueden deducir del algoritmo euclidiano y de la división euclídea. Además, el polinomio MCD tiene propiedades específicas que lo convierten en una noción fundamental en diversas áreas del álgebra. Normalmente, las raíces del MCD de dos polinomios son las raíces comunes de los dos polinomios, y esto proporciona información sobre las raíces sin necesidad de calcularlas. Por ejemplo, las raíces múltiples de un polinomio son las raíces del MCD del propio polinomio y de su derivada, y los cálculos adicionales del MCD permiten calcular el polinomio libre de cuadrados del polinomio de partida, lo que proporciona polinomios cuyas raíces son las raíces de un múltiples del polinomio original.

El máximo común divisor puede definirse y existe, de manera más general, para polinomios sobre un cuerpo numérico o sobre el anillo de los números enteros, y también sobre un dominio de factorización única. Existen algoritmos para calcularlos si se dispone de un algoritmo para calcular el MCD en el anillo de coeficientes. Estos algoritmos proceden mediante una recursión sobre el número de variables para reducir el problema a una variante del algoritmo euclidiano. Son una herramienta fundamental en cálculo simbólico, porque los sistemas algebraicos computacionales los usan sistemáticamente para simplificar fracciones. Por el contrario, la mayor parte de la teoría moderna del MCD polinómico se ha desarrollado para satisfacer la necesidad de eficiencia de los sistemas de álgebra por computadora.

Definición general

Sean p y q dos polinomios con coeficientes en un dominio de integridad F, normalmente un cuerpo o el anillo de los números enteros.

Un máximo común divisor de p y q es un polinomio d que divide a p y que divide a q, y tal que cada divisor común de p y de q también divide a d. Cada par de polinomios (ambos no nulos) tiene un MCD si y solo si F es un dominio de factorización única.

Si F es un cuerpo y p y q no son ambos cero, un polinomio d es un máximo común divisor si y solo si divide tanto a p como a q, y tiene el mayor grado entre los polinomios que tienen esta propiedad. Si p = q = 0, el MCD es 0. Sin embargo, algunos autores consideran que en este caso el MCD no está definido.

El máximo común divisor de p y q generalmente se denota como mcd(p, q).

El máximo común divisor no es único: si d es un MCD de p y q, entonces el polinomio f es otro MCD si y solo si hay un elemento invertible u de F tal que

$f=ud$

y

$d=u^{-1}f$.

En otras palabras, el MCD es único excepto si se considera la multiplicación por una constante invertible.

En el caso de los enteros, esta indeterminación se ha resuelto eligiendo como MCD el único que es positivo (hay otro, que es su contrario). Con esta convención, el MCD de dos enteros también es el divisor común más grande (para el orden habitual). Sin embargo, dado que no existe orden total natural entre los polinomios sobre un dominio integral, no se puede proceder de la misma manera aquí. Para polinomios de una sola variable sobre un cuerpo, se puede requerir adicionalmente que el MCD sea un polinomio mónico (es decir, que tenga 1 como su coeficiente del grado más alto), pero en casos más generales no existe una convención general. Por lo tanto, las igualdades como d = mcd(p, q) o mcd(p, q) = mcd(r, s) son abusos comunes de notación que deben leerse como d es un MCD de p y de q; y como que p y q tienen el mismo conjunto de MCD que r y que s. En particular, mcd(p, q) = 1 significa que las constantes invertibles son los únicos divisores comunes. En este caso, por analogía con el caso entero, se dice que p y q son polinomios coprimos.

Propiedades

• Como se indicó anteriormente, el MCD de dos polinomios existe si los coeficientes pertenecen a un cuerpo, el anillo de los números enteros o, de manera más general, a un dominio de factorización única.
• Si c es un divisor común de p y q, c divide al MCD de p y de q.
• ${\text{mcd }}(p,q)={\text{mcd }}(q,p).$
• ${\text{mcd }}(p,q)={\text{mcd }}(q,p+rq)$ para cualquier polinomio r. Esta propiedad está en la base de la prueba del algoritmo de euclides.
• Para cualquier elemento invertible k del anillo de los coeficientes, ${\text{mcd }}(p,q)={\text{mcd }}(p,kq)$.
• Por lo tanto, ${\text{mcd }}(p,q)={\text{mcd }}(a_{1}p+b_{1}q,a_{2}p+b_{2}q)$ para cualquier escalar $a_{1},b_{1},a_{2},b_{2}$ tal que $a_{1}b_{2}-a_{2}b_{1}$ sea invertible.
• Si ${\text{mcd }}(p,r)=1$, entonces ${\text{mcd }}(p,q)={\text{mcd }}(p,qr)$.
• Si ${\text{mcd }}(q,r)=1$, entonces ${\text{mcd }}(p,qr)={\text{mcd }}(p,q)\,{\text{mcd }}(p,r)$.
• Para dos polinomios de una variable p y q sobre un cuerpo, existen polinomios a y b, de modo que ${\text{mcd }}(p,q)=ap+bq$ y ${\text{mcd }}(p,q)$ dividen cada combinación lineal de p y de q (identidad de Bézout).
• El máximo común divisor de tres o más polinomios se puede definir de manera similar al de dos polinomios. Puede calcularse de forma recursiva a partir de los MCD de dos polinomios mediante las identidades:

${\text{mcd }}(p,q,r)={\text{mcd }}(p,{\text{mcd }}(q,r)),$

y

${\text{mcd }}(p_{1},p_{2},\dots ,p_{n})={\text{mcd }}(p_{1},{\text{mcd }}(p_{2},\dots ,p_{n})).$

MCD mediante cálculo manual

Hay varias formas de encontrar el máximo común divisor de dos polinomios. Dos de ellas son:

1. Factorización de polinomios, mediante la que se determinan los factores de cada expresión, luego se selecciona el conjunto de factores comunes incluidos dentro de ambos conjuntos de factores. Este método puede ser útil solo en casos simples, ya que la factorización suele ser más difícil que calcular el máximo común divisor.
2. El algoritmo de Euclides, que se puede usar para encontrar el MCD de dos polinomios de la misma manera que para dos números enteros.

Factorización

Para encontrar el MCD de dos polinomios usando su factorización, basta con factorizar los dos polinomios por completo. A continuación, se selecciona el producto de todos los factores comunes. En esta etapa, no necesariamente se obtiene un polinomio mónico, por lo que finalmente se debe multiplicar por una constante para convertirlo en un polinomio mónico. Este será el MCD de los dos polinomios, ya que incluye todos los divisores comunes, y es mónico.

Ejemplo uno: Encontrar el MCD de x² + 7x + 6 y de x² − 5x − 6.

x² + 7x + 6 = (x + 1)(x + 6)

x² − 5x − 6 = (x + 1)(x - 6)

Por lo tanto, su MCD es x + 1.

Algoritmo de Euclides

Factorizar polinomios puede ser difícil, especialmente si los polinomios tienen un grado grande. El algoritmo de Euclides es un método que funciona para cualquier par de polinomios. Hace un uso repetido de la división euclídea. Cuando se usa este algoritmo con dos números enteros, el tamaño de los números disminuye en cada etapa. Con polinomios, el grado de los polinomios disminuye en cada etapa. El último resto distinto de cero, transformado en mónico si es necesario, es el MCD de los dos polinomios.

Más específicamente, para encontrar el mcd de dos polinomios a(x) y b(x), se puede suponer que b ≠ 0 (de lo contrario, el MCD es a(x)), y

$\deg(b(x))\leq \deg(a(x))\,.$

La división euclídea proporciona dos polinomios q(x), el cociente; y r(x), el resto; tales que

$a(x)=q_{0}(x)b(x)+r_{0}(x)\qquad {\text{y}}\qquad \deg(r_{0}(x))<\deg(b(x))$

Un polinomio g(x) divide a a(x) y a b(x) si y solo si divide a b(x) y r₀(x). Por lo tanto

$\gcd(a(x),b(x))=\gcd(b(x),r_{0}(x)).$

La configuración

$a_{1}(x)=b(x),b_{1}(x)=r_{0}(x),$

permite repetir la división euclidiana para obtener nuevos polinomios q₁(x), r₁(x), a₂(x), b₂(x) y así sucesivamente. En cada etapa se tiene que

$\deg(a_{k+1})+\deg(b_{k+1})<\deg(a_{k})+\deg(b_{k}),$

por lo que la secuencia finalmente llegará a un punto en el que

$b_{N}(x)=0$

y se obtiene el MCD:

$\gcd(a,b)=\gcd(a_{1},b_{1})=\cdots =\gcd(a_{N},0)=a_{N}.$

Ejemplo: encontrar el MCD de x² + 7x + 6 y x² − 5x − 6:

x² + 7x + 6 = 1 ⋅ (x² − 5x − 6) + (12 x + 12)

x² − 5x − 6 = (12 x + 12) (1/12 x − 1/2) + 0

Dado que 12 x + 12 es el último resto distinto de cero, es un MCD de los polinomios originales y el polinomio mónico MCD es x + 1.

En este ejemplo, no es difícil evitar la introducción de denominadores factorizando 12 antes del segundo paso. Esto siempre se puede hacer usando secuencias de pseudo-resto, pero si no se tiene cuidado con las operaciones, se pueden generar números enteros muy grandes durante el cálculo. Por lo tanto, para los cálculos con computadora, se utilizan otros algoritmos, que se describen a continuación.

Este método funciona solo si se puede probar la igualdad a cero de los coeficientes que aparecen durante el cálculo. Entonces, en la práctica, los coeficientes deben ser números enteros, números racionales, elementos de un cuerpo finito, o deben pertenecer a alguna extensión de cuerpos de uno de los cuerpos anteriores. Si los coeficientes son valores con coma flotante que representan números reales que se conocen solo aproximadamente, entonces se debe conocer el grado del MCD para obtener un resultado de cálculo bien definido (es decir, un resultado provisto de estabilidad numérica; en estos casos se pueden utilizar otras técnicas, generalmente basadas en descomposición en valores singulares.

Polinomios de una variable con coeficientes en un cuerpo

El caso de polinomios de una variable sobre un cuerpo es especialmente importante por varias razones. En primer lugar, es el caso más elemental y, por tanto, aparece en la mayoría de los primeros cursos de álgebra. En segundo lugar, es muy similar al caso de los números enteros, y esta analogía es la fuente de la noción de dominio euclídeo. Una tercera razón es que la teoría y los algoritmos para el caso de varias variables y para los coeficientes en un dominio de factorización única están fuertemente basados en este caso particular. Por último, pero no menos importante, los algoritmos de MCD polinómicos y los algoritmos derivados permiten obtener información útil sobre las raíces de un polinomio, sin calcularlas.

División euclídea

La división euclídea de polinomios, que se usa en el Algoritmo de Euclides para calcular el MCD, es muy similar a la división euclídea de números enteros. Su existencia se basa en el siguiente teorema: Dados dos polinomios de una variable a y b ≠ 0 definidos sobre un cuerpo, existen dos polinomios q (el cociente) y r (el resto) que satisfacen

$a=bq+r$

y

$\deg(r)<\deg(b),$

donde deg (...) denota el grado; y el grado del polinomio cero se define como negativo. Además, q y r se definen de forma única por estas relaciones.

La diferencia con la división euclidiana de números enteros es que, para los números enteros, el grado se reemplaza por el valor absoluto, y que para tener unicidad se tiene que suponer que r no es negativo. Los anillos para los que existe tal teorema se denominan dominios euclídeos.

Al igual que para los números enteros, la división euclídea de los polinomios puede calcularse mediante el algoritmo de división polinómica. Este algoritmo generalmente se presenta para el cálculo con lápiz y papel, pero funciona bien en computadoras cuando se formaliza de la siguiente manera (téngase en cuenta que los nombres de las variables corresponden exactamente a las regiones de la hoja de papel en un cálculo con lápiz y papel de división de polinomios). En el siguiente cálculo, deg representa el grado de su argumento (con la convención deg(0) < 0), y lc representa el coeficiente principal, el coeficiente del grado más alto de la variable.

División euclídea

Input: a y b ≠ 0 dos polinomios en la variable x;
Output: q, el cociente, y r, el resto;

Begin
    q := 0
    r := a
    d := deg(b)
    c := lc(b)
    while deg(r) ≥ d do
        s := lc(r)/c xdeg(r)−d
        q := q + s
        r := r − sb
    end do
    return (q, r)
end

La prueba de la validez de este algoritmo se basa en el hecho de que durante todo el ciclo "while", se tiene que a = bq + r y deg(r) es un número entero no negativo que disminuye en cada iteración. Así, la prueba de la validez de este algoritmo también prueba la validez de la división euclídea.

Algoritmo de Euclides

En cuanto a los números enteros, la división euclídea permite definir el algoritmo de Euclides para calcular los MCD.

Partiendo de dos polinomios a y b, el algoritmo de Euclides consiste en reemplazar recursivamente el par (a, b) por (b, rem(a, b)) (donde "rem(a, b)" denota el resto de la división euclídea, calculada por el algoritmo de la sección anterior), hasta obtener b = 0. El MCD es el último resto distinto de cero.

El algoritmo de Euclides se puede formalizar en el estilo de programación recursiva como:

${\text{mcd }}(a,b):{\text{si }}b=0{\text{ entonces =}}a{\text{; o en caso contrario, }}{\text{mcd }}(b,\operatorname {rem} (a,b)).$

En estilo de programación, dando un nombre a cada resto intermedio, el mismo algoritmo se convierte en:

${\begin{aligned}r_{0}:=a\\r_{1}:=b\end{aligned}}$

for ($i:=1$; $r_{i}\neq 0$; $i:=i+1$) do
    ${\begin{aligned}r_{i+1}&:=\operatorname {rem} (r_{i-1},r_{i})\end{aligned}}$
end do

return $(r_{i-1}).$

La secuencia de grados de r_i es estrictamente decreciente. Por lo tanto, después de como máximo deg(b) pasos, se obtiene un resto nulo, denominado r_k. Como (a, b) y (b, rem(a,b)) tienen los mismos divisores, el algoritmo de Euclides no cambia el conjunto de los divisores comunes y, por lo tanto, todos los pares (r_i, r_i+1) tienen el mismo conjunto de divisores comunes. Los divisores comunes de a y b son, por tanto, los divisores comunes de r_k−1 y 0. Por tanto, r_k−1 es un MCD de a y b. Esto no solo prueba que el algoritmo de Euclides calcula los MCD, sino que también prueba que existen los MCD.

Identidad de Bézout y algoritmo MCD extendido

La identidad de Bézout es un teorema relacionado con el MCD, inicialmente probado para los enteros, que es válido en cualquier dominio de ideales principales. En el caso de los polinomios de una variable sobre un cuerpo, se puede enunciar de la siguiente manera:

Si g es el máximo común divisor de dos polinomios a y b (no ambos cero), entonces hay dos polinomios u y v tales que

$au+bv=g\quad$ (Bézout's identity)

y también u = 1, v = 0, o u = 0, v = 1, o

$\deg(u)<\deg(b)-\deg(g),\quad \deg(v)<\deg(a)-\deg(g).$

El interés de este resultado en el caso de los polinomios es que existe un algoritmo eficiente para calcular los polinomios u y v. Este algoritmo se diferencia del algoritmo de Euclides por algunos cálculos más realizados en cada iteración del ciclo. Por lo tanto, se denomina algoritmo MCD extendido. Otra diferencia con el algoritmo de Euclides es que también usa el cociente, denotado quo, de la división euclídea en lugar de solo el resto. Este algoritmo funciona de la siguiente manera:

Algoritmo MCD extendido

Input: a, b, polinomios de una variable

Output:
    g, el MCD de a y b
    u, v, como en la línea anterior
    a1, b1, tales que
        ${\begin{aligned}a=ga_{1}\\b=gb_{1}\end{aligned}}$
Begin
    ${\begin{array}{ll}r_{0}=a&r_{1}=b\\s_{0}=1&s_{1}=0\\t_{0}=0&t_{1}=1\end{array}}$
  
    for (i = 1; ri ≠ 0; i = i+1) do
        $q=\operatorname {quo} (r_{i-1},r_{i})$
        ${\begin{aligned}r_{i+1}&=r_{i-1}-qr_{i}\\s_{i+1}&=s_{i-1}-qs_{i}\\t_{i+1}&=t_{i-1}-qt_{i}\end{aligned}}$
    end do
    ${\begin{aligned}g&=r_{i-1}\\u&=s_{i-1}\\v&=t_{i-1}\end{aligned}}$
    ${\begin{aligned}a_{1}&=(-1)^{i-1}t_{i}\\b_{1}&=(-1)^{i}s_{i}\end{aligned}}$
end

La prueba de que el algoritmo satisface las condiciones de partida se basa en el hecho de que, para cada i se tiene que

$r_{i}=as_{i}+bt_{i}$

$s_{i}t_{i+1}-t_{i}s_{i+1}=s_{i}t_{i-1}-t_{i}s_{i-1},$

la última igualdad implicando

$s_{i}t_{i+1}-t_{i}s_{i+1}=(-1)^{i}.$

La afirmación sobre los grados se deriva del hecho de que, en cada iteración, los grados de s_i y de t_i aumentan como máximo a medida que disminuye el grado de r_i.

Una característica interesante de este algoritmo es que, cuando se necesitan los coeficientes de la identidad de Bezout, se obtiene sin cálculos adicionales el cociente de los polinomios de entrada por su MCD.

Aritmética de extensiones algebraicas

Una aplicación importante del algoritmo MCD extendido es que permite calcular la división en extensiones algebraicas de cuerpos.

Sea L una extensión algebraica de un cuerpo K, generado por un elemento cuyo polinomio mínimo f tiene grado n. Los elementos de L suelen estar representados por polinomios de una variable sobre K de grado menor que n.

La adición en L es simplemente la adición de polinomios:

$a+_{L}b=a+_{K[X]}b.$

La multiplicación en L es la multiplicación de polinomios seguida de la división por f:

$a\cdot _{L}b=\operatorname {rem} (a._{K[X]}b,f).$

El inverso de un elemento distinto de cero a de L es el coeficiente u en la identidad de Bézout au + fv = 1, que puede calcularse mediante el algoritmo MCD extendido (el MCD es 1 porque el polinomio mínimo f es irreducible). La desigualdad de grados en la especificación del algoritmo MCD extendido muestra que no se necesita una división adicional por f para obtener que deg (u) < deg(f).

Subresultantes

En el caso de los polinomios de una variable, existe una fuerte relación entre los máximos divisores comunes y la resultante. Más precisamente, la resultante de dos polinomios P, Q es una función polinómica de los coeficientes de P y Q que tiene el valor cero si y solo si el MCD de P y Q no son constantes.

La teoría de los subresultantes es una generalización de esta propiedad que permite caracterizar genéricamente el MCD de dos polinomios, y el resultante es el polinomio subresultante 0-ésimo.​

El i-ésimo polinomio subsultante S_i(P, Q) de dos polinomios P y Q es un polinomio de grado como máximo i cuyos coeficientes son funciones polinómicas de los coeficientes de P y de Q, y el i-ésimo coeficiente principal subresultante s_i(P, Q) es el coeficiente de grado i de S_i(P, Q). Tienen la propiedad de que el MCD de P y Q tiene un grado d si y solo si

$s_{0}(P,Q)=\cdots =s_{d-1}(P,Q)=0\ ,s_{d}(P,Q)\neq 0$.

En este caso, S_d(P, Q) es un MCD de P y Q y

$S_{0}(P,Q)=\cdots =S_{d-1}(P,Q)=0.$

Cada coeficiente de los polinomios subresultantes se define como el determinante de una submatriz de la matriz de Sylvester de P y Q. Esto implica que los subresultantes se especializan bien. Más precisamente, los subresultantes se definen para polinomios sobre cualquier anillo conmutativo R, y tienen la siguiente propiedad.

Sea φ un homomorfismo sobre un anillo de R en otro anillo conmutativo S. Se extiende a otro homomorfismo, también denominado φ entre los anillos de polinomios sobre R y S. Entonces, si P y Q son polinomios de una variable con coeficientes en R tales que

$\deg(P)=\deg(\varphi (P))$

y

$\deg(Q)=\deg(\varphi (Q)),$

entonces los polinomios subresultantes y los coeficientes principales subresultantes de φ(P) y φ(Q) son la imagen mediante φ de los de P y Q.

Los subresultantes tienen dos propiedades importantes que los hacen fundamentales para el cálculo en computadoras del MCD de dos polinomios con coeficientes enteros.

En primer lugar, su definición mediante determinantes permite acotar, mediante la desigualdad de Hadamard, el tamaño de los coeficientes del MCD. En segundo lugar, esta cota y la propiedad de una buena especialización permiten calcular el MCD de dos polinomios con coeficientes enteros a través de la computación modular y del teorema chino del resto (véase algoritmo modular del MCD más adelante).

Definición técnica

Sean

$P=p_{0}+p_{1}X+\cdots +p_{m}X^{m},\quad Q=q_{0}+q_{1}X+\cdots +q_{n}X^{n}.$

dos polinomios de una variable con coeficientes en un cuerpo K. Se denotan por ${\mathcal {P}}_{i}$ el espacio vectorial K de dimensión i los polinomios de grado menor que i. Para un entero no negativo i tal que i ≤ m e i ≤ n, sea

$\varphi _{i}:{\mathcal {P}}_{n-i}\times {\mathcal {P}}_{m-i}\rightarrow {\mathcal {P}}_{m+n-i}$

la aplicación lineal tal que

$\varphi _{i}(A,B)=AP+BQ.$

El resultante de P y Q es el determinante de la matriz de Sylvester, que es la matriz (cuadrada) de $\varphi _{0}$ sobre la base de las potencias de X. De manera similar, el polinomio i-subresultante se define en términos de determinantes de submatrices de la matriz de $\varphi _{i}.$

Se describen ahora estas matrices con mayor precisión;

Sea p_i = 0 para i < 0 o i > m, y q_i = 0 para i < 0 o i > n. La matriz de Sylvester es la matriz de dimensión (m + n) × (m + n), tal que el coeficiente de la i-ésima fila y de la j-ésima columna es p_m+j−i para j ≤ n y q_j−i para j > n:​

$S={\begin{pmatrix}p_{m}&0&\cdots &0&q_{n}&0&\cdots &0\\p_{m-1}&p_{m}&\cdots &0&q_{n-1}&q_{n}&\cdots &0\\p_{m-2}&p_{m-1}&\ddots &0&q_{n-2}&q_{n-1}&\ddots &0\\\vdots &\vdots &\ddots &p_{m}&\vdots &\vdots &\ddots &q_{n}\\\vdots &\vdots &\cdots &p_{m-1}&\vdots &\vdots &\cdots &q_{n-1}\\p_{0}&p_{1}&\cdots &\vdots &q_{0}&q_{1}&\cdots &\vdots \\0&p_{0}&\ddots &\vdots &0&q_{0}&\ddots &\vdots &\\\vdots &\vdots &\ddots &p_{1}&\vdots &\vdots &\ddots &q_{1}\\0&0&\cdots &p_{0}&0&0&\cdots &q_{0}\end{pmatrix}}.$

La matriz T_i de $\varphi _{i}$ es la (m + n - i) × (m + n - 2i ) -submatriz de S que se obtiene eliminando las últimas i filas de ceros en la submatriz de las columnas 1 a (n - i) y (n + 1) a (m + n - i) de S (es decir, eliminar las columnas i en cada bloque y las últimas filas de ceros de la i). El coeficiente subresultante principal s_i es el determinante de las (m + n - 2i) primeras filas de T_i.

Sea V_i la matriz (m + n - 2i) × (m + n - i) definida como sigue. Primero se agregan (i + 1) columnas de ceros a la derecha de la matriz identidad de dimensión (m + n - 2i - 1) × (m + n - 2i - 1). Luego, se orla la parte inferior de la matriz resultante con una fila que consta de (m + n - i - 1) ceros seguidos de Xⁱ, Xⁱ⁻¹, ..., X, 1:

$V_{i}={\begin{pmatrix}1&0&\cdots &0&0&0&\cdots &0\\0&1&\cdots &0&0&0&\cdots &0\\\vdots &\vdots &\ddots &\vdots &\vdots &\ddots &\vdots &0\\0&0&\cdots &1&0&0&\cdots &0\\0&0&\cdots &0&X^{i}&X^{i-1}&\cdots &1\end{pmatrix}}.$

Con esta notación, el i-ésimo polinomio subresultante es el determinante del producto matricial V_iT_i. Su coeficiente de grado j es el determinante de la submatriz cuadrada de T_i que consiste en sus (m + n - 2i - 1) primeras filas y la (m + n - i - j) fila.

Bosquejo de la demostración

No es obvio que, tal como se definen, los subresultantes tengan las propiedades deseadas. Sin embargo, la demostración es bastante simple si se combinan las propiedades del álgebra lineal y las de los polinomios.

Tal como se define, las columnas de la matriz T_i son los vectores de los coeficientes de algunos polinomios pertenecientes a la imagen de $\varphi _{i}$. La definición del i-ésimo polinomio subsultante S_i muestra que el vector de sus coeficientes es una combinación lineal de estos vectores columna, y por lo tanto que S_i pertenece a la imagen de $\varphi _{i}.$

Si el grado de la MCD es mayor que i, entonces la identidad de Bézout muestra que cada polinomio distinto de cero en la imagen de $\varphi _{i}$ tiene un grado mayor que i. Esto implica que S_i = 0.

Si, por el contrario, el grado del MCD es i, entonces la identidad de Bézout permite nuevamente probar que los múltiplos del MCD que tienen un grado menor que (m + n - i) están en la imagen de $\varphi _{i}$. El espacio vectorial de estos múltiplos tiene la dimensión (m + n - 2i) y tiene una base de polinomios de grados diferentes por pares, no menor que i. Esto implica que la submatriz de las primeras (m + n - 2i) filas de la forma escalonada de columna de T_i es la matriz de identidad y, por lo tanto, que s_i no es 0. En consecuencia, S_i es un polinomio en la imagen de $\varphi _{i}$, que es un múltiplo del MCD y tiene el mismo grado. Por tanto, es un máximo común divisor.

MCD y búsqueda de raíces

Factorización libre de cuadrados

La mayoría de los procedimientos de resolución numérica de ecuaciones no lineales se comportan mal con polinomios que tienen raíces repetidas. Por lo tanto, es útil detectarlas y eliminarlas antes de utilizar un algoritmo de búsqueda de raíces. Un cálculo de MCD permite la detección de la existencia de raíces múltiples, ya que las raíces múltiples de un polinomio son las raíces del MCD del polinomio y de su derivada.

Después de calcular el MCD del polinomio y su derivada, los cálculos adicionales del MCD proporcionan una factorización libre de cuadrados completa del polinomio, con la forma

$f=\prod _{i=1}^{\deg(f)}f_{i}^{i}$

donde, para cada i, el polinomio f_i es 1 si f no tiene ninguna raíz de multiplicidad i o es un polinomio libre de cuadrados (es decir, un polinomio sin raíces múltiples) cuyas raíces son exactamente las raíces de multiplicidad i de f (véase algoritmo de Yun).

Por lo tanto, la factorización libre de cuadrados reduce la búsqueda de raíces de un polinomio con raíces múltiples a la búsqueda de raíces de varios polinomios libres de cuadrados de menor grado. La factorización libre de cuadrados también es el primer paso en la mayoría de los algoritmos de factorización de polinomios.

Secuencia de Sturm

La secuencia de Sturm de un polinomio con coeficientes reales es la secuencia de los residuos proporcionada por una variante del algoritmo de Euclides aplicada al polinomio y su derivada. Para obtener la secuencia de Sturm, simplemente se reemplaza la instrucción

$r_{i+1}:=\operatorname {rem} (r_{i-1},r_{i})$

del algoritmo de Euclides por

$r_{i+1}:=-\operatorname {rem} (r_{i-1},r_{i}).$

Sea V(a) el número de cambios de signo en la secuencia, cuando se evalúa en un punto a. El teorema de Sturm afirma que V(a) - V(b) es el número de raíces reales del polinomio en el intervalo [a, B]. Por tanto, la secuencia de Sturm permite calcular el número de raíces reales en un intervalo dado. Al subdividir el intervalo hasta que cada subintervalo contiene como máximo una raíz, se obtiene un algoritmo que ubica las raíces reales en intervalos de pequeña longitud arbitraria.

MCD sobre un anillo y su cuerpo de fracciones

En esta sección, se consideran polinomios sobre un dominio de factorización única R, típicamente el anillo de los enteros, y sobre su cuerpo de fracciones F, típicamente el cuerpo de los números racionales. Además, se denotan como R[X] y F[X] los anillos de polinomios en un conjunto de variables sobre estos anillos.

Factorización de contenido parcial primitivo

Véase también: Lema de Gauss

El contenido de un polinomio p ∈ R[X], denotado como cont(p), es el MCD de sus coeficientes. Se puede escribir un polinomio q ∈ F[X]:

$q={\frac {p}{c}}$

donde p ∈ R[X] y c ∈ R: es suficiente tomar para c un múltiplo de todos los denominadores de los coeficientes de q (por ejemplo, su producto) y p = cq. El contenido de q se define como:

$\operatorname {cont} (q)={\frac {\operatorname {cont} (p)}{c}}.$

En ambos casos, el contenido se define (salvo multiplicación) por la unidad de R.

La parte primitiva de un polinomio en R[X] o F[X] se define por

$\operatorname {primpart} (p)={\frac {p}{\operatorname {cont} (p)}}.$

En ambos casos, es un polinomio en R[X] que es primitivo, lo que significa que 1 es un MCD de sus coeficientes.

Por lo tanto, cada polinomio en R[X] o F[X] se puede factorizar como

$p=\operatorname {cont} (p)\,\operatorname {primpart} (p),$

y esta factorización es única (salvo multiplicación del contenido) por una unidad de R y de la parte primitiva por la inversa de esta unidad.

El lema de Gauss implica que el producto de dos polinomios primitivos es primitivo. Resulta que

$\operatorname {primpart} (pq)=\operatorname {primpart} (p)\operatorname {primpart} (q)$

y

$\operatorname {cont} (pq)=\operatorname {cont} (p)\operatorname {cont} (q).$

Relación entre el MCD sobre R y sobre F

Las relaciones de la sección anterior implican una fuerte relación entre los MCD en R[X] y en F[X]. Para evitar ambigüedades, la notación "mcd" será indexada, a continuación, por el anillo en el que se calcula el MCD.

Si q₁ y q₂ pertenecen a F[X], entonces

$\operatorname {primpart} (\gcd _{F[X]}(q_{1},q_{2}))=\gcd _{R[X]}(\operatorname {primpart} (q_{1}),\operatorname {primpart} (q_{2})).$

Si p₁ y p₂ pertenecen a R[X], entonces

$\gcd _{R[X]}(p_{1},p_{2})=\gcd _{R}(\operatorname {cont} (p_{1}),\operatorname {cont} (p_{2}))\gcd _{R[X]}(\operatorname {primpart} (p_{1}),\operatorname {primpart} (p_{2})),$

y

$\gcd _{R[X]}(\operatorname {primpart} (p_{1}),\operatorname {primpart} (p_{2}))=\operatorname {primpart} (\gcd _{F[X]}(p_{1},p_{2})).$

Por lo tanto, el cálculo de los MCD polinómicos es esencialmente el mismo problema sobre F[X] y sobre R[X].

Para polinomios de una variable sobre los números racionales, se puede pensar que el algoritmo de Euclides es un método conveniente para calcular el MCD. Sin embargo, implica simplificar una gran cantidad de fracciones de números enteros y el algoritmo resultante no es eficiente. Por esta razón, se han diseñado métodos para modificar el algoritmo de Euclides para trabajar solo con polinomios sobre los números enteros. Consisten en reemplazar la división euclídea, que introduce fracciones, por una llamada pseudodivisión, y reemplazar la secuencia restante del algoritmo de Euclides por la llamada secuencia de pseudorestos (véase secuencia de pseudorestos).

Demostración de que existe MCD para polinomios de varias variables

En la sección anterior se ha visto que el MCD de polinomios en R[X] se puede deducir de los MCD en R y en F[X]. Una mirada más cercana a la demostración evidencia que esto permite probar la existencia de MCD en R[X], si existen en R y en F[ X]. En particular, si los MCD existen en R, y si X se reduce a una variable, esto prueba que los MCD existen en R[X] (el algoritmo de Euclides prueba la existencia de MCD en F[X]).

Un polinomio con n variables se puede considerar como un polinomio de una variable sobre el anillo de polinomios con (n - 1) variables. Por lo tanto, la recursividad sobre el número de variables muestra que si existen MCD y pueden calcularse en R, entonces existen y pueden calcularse en cada anillo polinomios de varias variables sobre R. En particular, si R es el anillo de los números enteros o un cuerpo, entonces los MCD existen en R[x₁, ..., x_n], y lo que precede proporciona un algoritmo para calcularlos.

La prueba de que un anillo de polinomios sobre un dominio de factorización único es también un dominio de factorización único es similar, pero no proporciona un algoritmo, porque no existe un algoritmo general para factorizar polinomios de una variable en un cuerpo (hay ejemplos de cuerpos para los que no existe ningún algoritmo de factorización para los polinomios de una variable).

Secuencia de pseudo-restos

En esta sección, consideramos un dominio de integridad Z (típicamente el anillo Z de los enteros) y su cuerpo de fracciones Q (típicamente el cuerpo Q de los números racionales). Dados dos polinomios A y B en el anillo de los polinomios de una variante Z[X], la división euclídea (sobre Q) de A por B proporciona un cociente y un resto que pueden no pertenecer a Z[X].

Porque, si se aplica el algoritmo de Euclides a los siguientes polinomios​

$X^{8}+X^{6}-3X^{4}-3X^{3}+8X^{2}+2X-5$

y

$3X^{6}+5X^{4}-4X^{2}-9X+21,$

los restos sucesivos del algoritmo de Euclides son

${\begin{aligned}&-{\tfrac {5}{9}}X^{4}+{\tfrac {1}{9}}X^{2}-{\tfrac {1}{3}},\\&-{\tfrac {117}{25}}X^{2}-9X+{\tfrac {441}{25}},\\&{\tfrac {233150}{19773}}X-{\tfrac {102500}{6591}},\\&-{\tfrac {1288744821}{543589225}}.\end{aligned}}$

Se ve que, a pesar del pequeño grado y el pequeño tamaño de los coeficientes de los polinomios de entrada, se tiene que manipular y simplificar fracciones enteras de tamaño bastante grande.

La pseudo-división se ha introducido con el fin de obtener una variante del algoritmo de Euclides para la que todos los restos pertenecen a Z[X].

Si $\deg(A)=a$ y $\deg(B)=b$ y a ≥ b, el pseudo-resto de la pseudo-división de A por B, denotado por prem(A', B) es

$\operatorname {prem} (A,B)=\operatorname {rem} (\operatorname {lc} (B)^{a-b+1}A,B),$

donde lc(B) es el coeficiente principal de B (el coeficiente de X^b).

El pseudo-resto de la pseudo-división de dos polinomios en Z[X] pertenece siempre a Z[X].

Una secuencia de pseudo-restos es la secuencia de los (pseudo) restos r_i obtenida reemplazando la instrucción

$r_{i+1}:=\operatorname {rem} (r_{i-1},r_{i})$

del algoritmo de Euclides por

$r_{i+1}:={\frac {\operatorname {prem} (r_{i-1},r_{i})}{\alpha }},$

donde α es un elemento de Z que divide exactamente cada coeficiente del numerador. Las diferentes opciones de α dan diferentes secuencias de pseudo-restos, que se describen en las siguientes subsecciones.

Como los divisores comunes de dos polinomios no se modifican si los polinomios se multiplican por constantes invertibles (en Q), el último término distinto de cero en una secuencia de pseudo-restos es un MCD (en Q[X]) de los polinomios de partida. Por lo tanto, la secuencia de pseudo-restos permiten calcular el MCD en Q[X] sin introducir fracciones en Q.

En algunos contextos, es esencial controlar el signo del coeficiente principal del pseudo-resto. Este suele ser el caso al calcular resultantes y subresultantes, o al utilizar el teorema de Sturm. Este control se puede hacer reemplazando lc(B) por su valor absoluto en la definición del pseudo-resto, o controlando el signo de α (si α divide a todos los coeficientes de un resto, lo mismo es cierto para –α).​

Secuencia trivial de pseudo-restos

La secuencia de restos más simple (de definir) consiste en tomar siempre α = 1. En la práctica, no es interesante, ya que el tamaño de los coeficientes crece exponencialmente con el grado de los polinomios de entrada. Esto aparece claramente en el ejemplo de la sección anterior, para el que los sucesivos pseudo-restos son

$-15\,X^{4}+3\,X^{2}-9,$

$15795\,X^{2}+30375\,X-59535,$

$1254542875143750\,X-1654608338437500,$

$12593338795500743100931141992187500.$

El número de dígitos de los coeficientes de los restos sucesivos se duplica con creces en cada iteración del algoritmo. Este es el comportamiento típico de la secuencia trivial de pseudo-restos.

Secuencia primitiva de pseudo-restos

La "secuencia primitiva de pseudo-restos" consiste en tomar por α el contenido del numerador. Por tanto, todos los r_i son polinomios primitivos.

La secuencia primitiva de pseudo-restos genera los coeficientes más pequeños. Sin embargo, requiere calcular un número de MCD en Z, y por lo tanto, no es lo suficientemente eficiente como para usarse en la práctica, especialmente cuando Z es en sí mismo un anillo de polinomios.

Con la misma entrada que en las secciones anteriores, los sucesivos restos, después de la división por su contenido, son

$-5\,X^{4}+X^{2}-3,$

$13\,X^{2}+25\,X-49,$

$4663\,X-6150,$

$1.$

El pequeño tamaño de los coeficientes oculta el hecho de que se han calculado varios números enteros del MCD y divisiones por el MCD.

Secuencia subresultante de pseudo-restos

Una secuencia subsultante también se puede calcular con pseudo-restos. El proceso consiste en elegir α de tal manera que cada r_i sea un polinomio subresultante. Sorprendentemente, el cálculo de α es muy fácil (véase más abajo). Por otro lado, la prueba de corrección del algoritmo es difícil, porque deben tenerse en cuenta todas las posibilidades de diferencia de grados de dos residuos consecutivos.

Los coeficientes de la secuencia subsultante rara vez son mucho mayores que los de la secuencia de pseudo-restos primitiva. Como los cálculos del MCD en Z no son necesarios, la secuencia subresultante con pseudo-residuos proporciona el cálculo más eficiente.

Con la misma entrada que en las secciones anteriores, los sucesivos restos son

$15\,X^{4}-3\,X^{2}+9,$

$65\,X^{2}+125\,X-245,$

$9326\,X-12300,$

$260708.$

Los coeficientes tienen un tamaño razonable. Se obtienen sin ningún cálculo del MCD, solo divisiones exactas. Esto hace que este algoritmo sea más eficiente que el de la secuencia primitiva de pseudo-restos.

El algoritmo que calcula la secuencia subresultante con pseudo-residuos se da a continuación. En este algoritmo, la entrada (a, b) es un par de polinomios en Z[X]. r_i son los sucesivos pseudo-residuos en Z[X], las variables i y d_i son enteros no negativos, y las letras griegas denotan elementos en Z. Las funciones deg() y rem() denotan el grado de un polinomio y el resto de la división euclidiana. En el algoritmo, este resto siempre está en Z[X]. Finalmente, las divisiones indicadas con / son siempre exactas y tienen su resultado en Z[X] o en Z.

${\begin{aligned}r_{0}:=a\\r_{1}:=b\end{aligned}}$
for ($i:=1$; $r_{i}\neq 0$; $i:=i+1;$) do
    ${\begin{aligned}d_{i}&:=\deg(r_{i-1})-\deg(r_{i})\\\gamma _{i}&:=\operatorname {lc} (r_{i})\end{aligned}}$
    if $i=1$ then
        ${\begin{aligned}\beta _{1}&:=(-1)^{d_{1}+1}\\\psi _{1}&:=-1\end{aligned}}$
    else
        ${\begin{aligned}\beta _{i}&:=-\gamma _{i-1}\psi _{i}^{d_{i}}\\\psi _{i}&:={\frac {(-\gamma _{i-1})^{d_{i-1}}}{\psi _{i-1}^{d_{i-1}-1}}}\end{aligned}}$
    end if
    $r_{i+1}:={\frac {\operatorname {rem} (\gamma _{i}^{d_{i}+1}r_{i-1},r_{i})}{\beta _{i}}}$
end do.

Nota: "lc" representa el coeficiente principal, el coeficiente del grado más alto de la variable.

Este algoritmo calcula no solo el máximo común divisor (el último r_i distinto de cero), sino también todos los polinomios subresultantes: el resto r_i es el polinomio subresultante (deg(r_i−1) − 1)-ésimo. Si deg(r_i) < deg(r_i−1) − 1, el polinomio subresultante deg(r_i)-ésimo es lc(r_i)^{deg(r_i−1) - deg (r_i) -1}r_i. Todos los demás polinomios subsultantes son cero.

Secuencia de Sturm con pseudo-restos

Se pueden usar pseudo-restos para construir secuencias que tengan las mismas propiedades que la secuencia de Sturm. Esto requiere controlar los signos de los sucesivos pseudo-restos, para tener los mismos signos que en la secuencia de Sturm. Esto se puede hacer definiendo un pseudo-resto modificado como sigue.

Si $\deg(A)=a$ y $\deg(B)=b$ y a ≥ b, el pseudo-resto modificado prem2 (A, B) de la pseudo-división de A por B es

$\operatorname {prem2} (A,B)=-\operatorname {rem} (|\operatorname {lc} (B)|^{a-b+1}A,B),$

donde |lc (B)| es el valor absoluto del coeficiente principal de B (el coeficiente de X^b).

Para polinomios de entrada con coeficientes enteros, esto permite la recuperación de secuencias de Sturm que consisten en polinomios con coeficientes enteros. La secuencia de pseudo-restos subresultante puede modificarse de manera similar, en cuyo caso los signos de los restos coinciden con los calculados sobre los números racionales.

Téngase en cuenta que el algoritmo para calcular la secuencia de pseudo-restos subresultantes dada anteriormente calculará polinomios subresultantes incorrectos si se usa $-\mathrm {prem2} (A,B)$ en lugar de $\operatorname {prem} (A,B)$.

Algoritmo modular del MCD

Si f y g son polinomios en F[x] para algún cuerpo finitamente generado F, el algoritmo euclídeo es la forma más natural de calcular su MCD. Sin embargo, los sistemas modernos de cálculo simbólico solo lo usan si F es finito debido a un fenómeno llamado hinchamiento de la expresión intermedia. Aunque los grados siguen disminuyendo durante el proceso del algoritmo euclídeo, si F no es finito, entonces el tamaño en bits de los polinomios puede aumentar (a veces drásticamente) durante los cálculos porque las operaciones aritméticas repetidas en F tienden a conducir a expresiones más grandes. Por ejemplo, la suma de dos números racionales cuyos denominadores están limitados por b conduce a un número racional cuyo denominador está limitado por b², por lo que en el peor de los casos, el tamaño en bits podría casi duplicarse con solo una operación.

Para acelerar el cálculo, se debe tomar un anillo D para el que f y g están en D[x], y tomar un ideal I tal que D/I es un anillo finito. Luego se calcula el MCD sobre este anillo finito con el algoritmo de euclides. Utilizando técnicas de reconstrucción (como el teorema chino del resto o la reconstrucción racional) se puede recuperar el MCD de f y g de su imagen modular en una serie de ideales I. Se puede probar​ que esto funciona siempre que se descarten imágenes modulares con grados no mínimos y se eviten los ideales de módulo I en los que un coeficiente principal desaparece.

Supóngase que $F=\mathbb {Q} ({\sqrt {3}})$, $D=\mathbb {Z} [{\sqrt {3}}]$, $f={\sqrt {3}}x^{3}-5x^{2}+4x+9$ y $g=x^{4}+4x^{2}+3{\sqrt {3}}x-6$. Si se toma $I=(2)$, $D/I$ un anillo finito (que no es un cuerpo, ya que $I$ no es máximo en $D$). El algoritmo euclídeo aplicado a las imágenes de $f,g$ en $(D/I)[x]$ tiene éxito y devuelve 1. Esto implica que el MCD de $f,g$ en $F[x]$ también debe ser 1. Téngase en cuenta que este ejemplo podría manejarse fácilmente con cualquier método porque los grados eran demasiado pequeños para que se produzca un hinchamiento de la expresión, pero ilustra que si dos polinomios tienen MCD 1, es probable que el algoritmo modular termine después de un solo ideal $I$.

Bibliografía

• Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise (2006). Algorithms in real algebraic geometry, chapter 4.2. Springer-Verlag. 
• Davenport, James H.; Siret, Yvon; Tournier, Évelyne (1988). Computer algebra: systems and algorithms for algebraic computation. Translated from the French by A. Davenport and J.H. Davenport. Academic Press. ISBN 978-0-12-204230-0. 
• van Hoeij, M.; Monagan, M.B. (2004), Algorithms for polynomial GCD computation over algebraic function fields, pp. 297-304 .
• Javadi, S.M.M.; Monagan, M.B. (2007), A sparse modular GCD algorithm for polynomials over algebraic function fields, pp. 187-194 .
• Knuth, Donald E. (1969). The Art of Computer Programming II. Addison-Wesley. pp. 370-371. 
• Knuth, Donald E. (1997). Seminumerical Algorithms. The Art of Computer Programming 2 (Third edición). Reading, Massachusetts: Addison-Wesley. pp. 439-461, 678-691. ISBN 0-201-89684-2. 
• Loos, Rudiger (1982), «Generalized polynomial remainder sequences», en B. Buchberger; R. Loos; G. Collins, eds., Computer Algebra, Springer Verlag .

Enlaces externos

• Portal:Matemáticas. Contenido relacionado con Matemáticas.

• Datos: Q7226640