Máximo común divisor polinomial - Polynomial greatest common divisor

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

En el caso importante de polinomios univariados sobre un campo, el polinomio MCD puede calcularse, como para el entero MCD, mediante el algoritmo euclidiano usando división larga . El polinomio MCD se define solo hasta la multiplicación por una constante invertible.

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

El máximo común divisor puede definirse y existe, de manera más general, para polinomios multivariados sobre un campo o el anillo de números enteros, y también sobre un dominio de factorización único . Existen algoritmos para calcularlos tan pronto como se tiene un algoritmo GCD en el anillo de coeficientes. Estos algoritmos proceden mediante una recursividad sobre el número de variables para reducir el problema a una variante del algoritmo euclidiano. Son una herramienta fundamental en álgebra computacional , porque los sistemas de álgebra computacional los usan sistemáticamente para simplificar fracciones. Por el contrario, la mayor parte de la teoría moderna de la GCD polinomial se ha desarrollado para satisfacer la necesidad de eficiencia de los sistemas de álgebra por computadora.

Definición general

Deje que p y q sean polinomios con coeficientes en un dominio de integridad F , típicamente un campo o los números enteros. Un máximo común divisor de p y q es un polinomio d que divide p y q , y de tal manera que cada divisor común de p y q también divide d . Cada par de polinomios (no ambos cero) tiene un MCD si y solo si F es un dominio de factorización único .

Si F es un campo y p y q no sean ambos cero, un polinomio d es un máximo común divisor si y sólo si se divide ambos p y 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 no está definido en este caso.

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

El máximo común divisor no es única: si d es un MCD de p y q , entonces el polinomio f es otro GCD si y sólo si existe un elemento invertible u de F tal que

${\ Displaystyle f = ud}$

y

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

En otras palabras, el GCD es único hasta 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 un orden total natural para los polinomios en un dominio integral, no se puede proceder de la misma manera aquí. Para polinomios univariados sobre un campo, se puede requerir adicionalmente que el MCD sea monico (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, igualdades como d = mcd ( p , q ) o gcd ( p , q ) = mcd ( r , s ) son abusos comunes de notación que deben leerse " d es un MCD de p y q " y " p y q tener el mismo conjunto de GCDs como r y 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 número entero, se dice que p y q son polinomios coprimos .

Propiedades

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

${\ Displaystyle \ gcd (p, q, r) = \ gcd (p, \ gcd (q, r)),}$

y

${\ Displaystyle \ gcd (p_ {1}, p_ {2}, \ dots, p_ {n}) = \ gcd (p_ {1}, \ gcd (p_ {2}, \ dots, p_ {n})) .}$

GCD por cálculo manual

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

1. La factorización de polinomios , en la que uno encuentra los factores de cada expresión, luego selecciona el conjunto de factores comunes que tienen todos dentro de cada conjunto 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 euclidiano , que se puede usar para encontrar el MCD de dos polinomios de la misma manera que para dos números.

Factorización

Para encontrar el MCD de dos polinomios usando factorización, simplemente factoriza los dos polinomios por completo. Luego, tome el producto de todos los factores comunes. En esta etapa, no necesariamente tenemos un polinomio monico, por lo que finalmente multiplique esto por una constante para convertirlo en un polinomio monico. Este será el MCD de los dos polinomios, ya que incluye todos los divisores comunes y es monico.

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

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

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

Por lo tanto, su MCD es x + 1 .

Algoritmo euclidiano

Factorizar polinomios puede ser difícil, especialmente si los polinomios tienen un grado grande. El algoritmo euclidiano es un método que funciona para cualquier par de polinomios. Hace un uso repetido de la división euclidiana . Cuando se usa este algoritmo en dos números, 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, convertido en monico 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

${\ Displaystyle \ deg (b (x)) \ leq \ deg (a (x)) \ ,.}$

La división euclidiana proporciona dos polinomios q ( x ) , el cociente y r ( x ) , el resto tal que

${\ Displaystyle 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 ( x ) y b ( x ) si y solo si divide a b ( x ) y r ₀ ( x ) . Por lo tanto

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

Configuración

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

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

${\ Displaystyle \ 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

${\ Displaystyle b_ {N} (x) = 0}$

y uno tiene el GCD:

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

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

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

x ² - 5 x - 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 MCD mónico 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, sin cuidado, esto puede introducir números enteros muy grandes durante el cálculo. Por lo tanto, para la computación por 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 ocurren durante el cálculo. Entonces, en la práctica, los coeficientes deben ser números enteros , números racionales , elementos de un campo finito o deben pertenecer a alguna extensión de campo generada finitamente de uno de los campos anteriores. Si los coeficientes son números de punto flotante que representan números reales que se conocen solo aproximadamente, entonces se debe conocer el grado de la MCD para tener un resultado de cálculo bien definido (que es un resultado numéricamente estable ; en estos casos, se pueden usar otras técnicas). , generalmente basado en la descomposición de valores singulares .

Polinomios univariados con coeficientes en un campo

El caso de polinomios univariados sobre un campo 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 euclidiano . Una tercera razón es que la teoría y los algoritmos para el caso multivariado y para los coeficientes en un dominio de factorización único se basan fuertemente en este caso particular. Por último, pero no menos importante, los algoritmos GCD polinomiales y los algoritmos derivados permiten obtener información útil sobre las raíces de un polinomio, sin calcularlos.

División euclidiana

La división euclidiana de polinomios, que se utiliza en el algoritmo de Euclides para calcular los MCD, es muy similar a la división euclidiana de números enteros. Su existencia se basa en el siguiente teorema: Dados dos polinomios univariantes a y b ≠ 0 definido sobre un campo, existen dos polinomios q (el cociente ) y r (el resto ) que satisfacen

${\ Displaystyle a = bq + r}$

y

${\ Displaystyle \ deg (r) <\ deg (b),}$

donde "deg (...)" denota el grado y el grado del polinomio cero se define como negativo. Por otra parte, q y r se definen de manera ú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 uno tiene que suponer que r no es negativo. Los anillos para los que existe tal teorema se denominan dominios euclidianos .

Al igual que para los números enteros, la división euclidiana de los polinomios puede calcularse mediante el algoritmo de división larga . Este algoritmo generalmente se presenta para el cálculo de papel y lápiz, pero funciona bien en computadoras cuando se formaliza de la siguiente manera (tenga en cuenta que los nombres de las variables corresponden exactamente a las regiones de la hoja de papel en un cálculo de lápiz y papel de largo división). 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 euclidiana

Entrada:  un y b ≠ 0 dos polinomios en la variable x ;
Salida:  q , el cociente yr , el resto;

Comenzar
     q  : = 0
     r  : = a 
    d  : = deg ( b )
     c  : = lc ( b )
     mientras que deg ( r ) ≥ d  hacer
         s  : =lc ( r )/C x deg ( 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 bucle "while", tenemos un = 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 euclidiana.

Algoritmo de Euclides

En cuanto a los números enteros, la división euclidiana nos permite definir el algoritmo de Euclides para calcular GCD.

A partir de dos polinomios una y b , el algoritmo de Euclides consiste en reemplazar de forma recursiva el par ( un , b ) por ( b , rem ( un , b )) (donde " rem ( un , b ) " indica el resto de la división euclidiana, calculado por el algoritmo de la sección anterior), hasta que b = 0. El MCD es el último resto distinto de cero.

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

${\ Displaystyle \ gcd (a, b): = {\ text {if}} b = 0 {\ text {then}} a {\ text {else}} \ gcd (b, \ operatorname {rem} (a, B)).}$

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

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

para (;;) hacer${\ Displaystyle i: = 1}$${\ Displaystyle r_ {i} \ neq 0}$${\ Displaystyle i: = i + 1}$
     do extremo${\ Displaystyle {\ begin {alineado} r_ {i + 1} &: = \ operatorname {rem} (r_ {i-1}, r_ {i}) \ end {alineado}}}$


regreso ${\ Displaystyle (r_ {i-1}).}$

La secuencia de los grados de r _i es estrictamente decreciente. Por lo tanto, después de, como máximo, pasos deg ( b ) , se obtiene un residuo nulo, digamos 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 una y b son por lo tanto los divisores comunes de r _{k -1} y 0. Por lo tanto r _{k -1} es un MCD de una y b . Esto no solo prueba que el algoritmo de Euclid calcula los GCD, sino que también prueba que existen los GCD.

Identidad de Bézout y algoritmo GCD extendido

La identidad de Bézout es un teorema relacionado con GCD, inicialmente probado para los enteros, que es válido para todos los dominios ideales principales . En el caso de los polinomios univariados sobre un campo, se puede enunciar de la siguiente manera.

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

${\ Displaystyle au + bv = g \ quad}$ (Identidad de Bézout)

y u = 1, v = 0 , o u = 0, v = 1 , o

${\ Displaystyle \ 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 GCD extendido . Otra diferencia con el algoritmo de Euclides es que también usa el cociente, denotado "quo", de la división euclidiana en lugar de solo el resto. Este algoritmo funciona de la siguiente manera.

Algoritmo GCD extendido

Entrada:  a , b , polinomios univariados

Salida:
     g , el MCD de a y b 
    u , v , como en el enunciado anterior
     a 1 , b 1 , tal que
         Begin${\ Displaystyle {\ begin {alineado} a = ga_ {1} \\ b = gb_ {1} \ end {alineado}}}$

    ${\ Displaystyle {\ begin {array} {ll} r_ {0} = a & r_ {1} = b \\ s_ {0} = 1 & s_ {1} = 0 \\ t_ {0} = 0 & t_ {1} = 1 \ end {array}}}$
  
    para ( i = 1 ; r i ≠ 0 ; i = i +1 ) do 
        end do end${\ Displaystyle q = \ operatorname {quo} (r_ {i-1}, r_ {i})}$
        ${\ Displaystyle {\ begin {alineado} 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 {alineado}}}$
    
    ${\ Displaystyle {\ begin {alineado} g & = r_ {i-1} \\ u & = s_ {i-1} \\ v & = t_ {i-1} \ end {alineado}}}$
    ${\ Displaystyle {\ begin {alineado} a_ {1} & = (- 1) ^ {i-1} t_ {i} \\ b_ {1} & = (- 1) ^ {i} s_ {i} \ final {alineado}}}$

La prueba de que el algoritmo satisface su especificación de salida se basa en el hecho de que, para cada i tenemos

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

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

la última igualdad implicando

${\ Displaystyle 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 t _i aumentan como máximo a medida que el grado de r _i disminuye.

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

Aritmética de extensiones algebraicas

Una aplicación importante del algoritmo GCD extendido es que permite calcular la división en extensiones de campos algebraicos .

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

La suma en L es simplemente la suma de polinomios:

${\ Displaystyle 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 :

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

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

Subresultantes

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

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

El i - ésimo polinomio subresultante S _i ( P , Q ) de dos polinomios P y Q es un polinomio de grado como máximo i cuyos coeficientes son funciones polinomiales de los coeficientes de P y 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 la MCD de P y Q tiene un grado d si y solo si

${\ Displaystyle 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

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

Cada coeficiente de los polinomios subresultante 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.

Deje φ ser un homomorfismo de anillo de R en otro anillo conmutativo S . Se extiende a otro homomorfismo, denotado también φ entre los polinomios de anillos más de R y S . Entonces, si P y Q son polinomios univariados con coeficientes en R tales que

${\ Displaystyle \ deg (P) = \ deg (\ varphi (P))}$

y

${\ Displaystyle \ deg (Q) = \ deg (\ varphi (Q)),}$

a continuación, los polinomios subresultante y los principales coeficientes subresultante de φ ( P ) y φ ( Q ) son la imagen por φ de las de P y Q .

Los subresultantes tienen dos propiedades importantes que los hacen fundamentales para el cálculo en computadoras de la MCD de dos polinomios con coeficientes enteros. En primer lugar, su definición a través de determinantes permite acotar, a través de la desigualdad de Hadamard , el tamaño de los coeficientes de la MCD. En segundo lugar, este límite y la propiedad de una buena especialización permiten calcular la MCD de dos polinomios con coeficientes enteros mediante el cálculo modular y el teorema del resto chino (ver más abajo ).

Definición técnica

Dejar

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

ser dos polinomios univariantes con coeficientes en un campo K . Denotemos por el espacio vectorial K de dimensión i de polinomios de grado menor que i . Para no negativo número entero i tal que i ≤ m y i ≤ n , deja ${\ Displaystyle {\ mathcal {P}} _ {i}}$

${\ Displaystyle \ varphi _ {i}: {\ mathcal {P}} _ {ni} \ times {\ mathcal {P}} _ {mi} \ rightarrow {\ mathcal {P}} _ {m + ni}}$

ser el mapa lineal tal que

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

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

Describamos estas matrices con mayor precisión;

Let 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 ( m + n ) × ( m + n ) -matriz tal que el coeficiente de la i -ésima fila y la j -ésima columna es p _{m + j - i} para j ≤ n y q _{j - i} para j > n :

${\ displaystyle 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 es la ( m + n - i ) × ( m + n - 2 i ) -submatriz de S que se obtiene eliminando las últimas i filas de ceros en la submatriz de las columnas 1 an - i y n + 1 am + n - i de S (es decir, eliminar i columnas en cada bloque y las i últimas filas de ceros). El principal coeficiente subsultante s _i es el determinante de las primeras filas m + n - 2 i de T _i . ${\ Displaystyle \ varphi _ {i}}$

Sea V _i la matriz ( m + n - 2 i ) × ( m + n - i ) definida como sigue. Primero agregamos ( i + 1) columnas de ceros a la derecha de la matriz identidad ( m + n - 2 i - 1) × ( m + n - 2 i - 1) . Luego, bordeamos la parte inferior de la matriz resultante con una fila que consta de ( m + n - i - 1) ceros seguidos de X ⁱ , X ^{i −1} , ..., X , 1:

${\ displaystyle 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 subsultante es el determinante del producto matricial V _i T _i . Su coeficiente de grado j es el determinante de la submatriz cuadrada de T _{i que} consiste en sus primeras filas m + n - 2 i - 1 y la ( m + n - i - j ) -ésima fila.

Bosquejo de la prueba

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

Como se define, las columnas de la matriz T _i son los vectores de los coeficientes de algunos polinomios pertenecientes a la imagen de . 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 tanto que S _i pertenece a la imagen de${\ Displaystyle \ varphi _ {i}}$${\ Displaystyle \ 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 tiene un grado mayor que i . Esto implica que S _i = 0. ${\ Displaystyle \ varphi _ {i}}$

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

GCD y búsqueda de raíces

Factorización libre de cuadrados

La mayoría de los algoritmos de búsqueda de raíces se comportan mal con polinomios que tienen múltiples raíces . Por lo tanto, es útil detectarlos y eliminarlos antes de llamar a un algoritmo de búsqueda de raíces. Un cálculo de GCD permite la detección de la existencia de múltiples raíces, ya que las raíces múltiples de un polinomio son las raíces de la MCD del polinomio y su derivada .

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

${\ Displaystyle 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íz múltiple) cuyas raíces son exactamente las raíces de la multiplicidad i de f (ver algoritmo de Yun ).

Por lo tanto, la factorización libre de cuadrados reduce la búsqueda de raíces de un polinomio con múltiples raíces 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 polinomial .

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

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

del algoritmo de Euclides por

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

Sea V ( a ) el número de cambios de signos 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, esto proporciona un algoritmo que ubica las raíces reales en intervalos de pequeña longitud arbitraria.

MCD sobre un anillo y su campo de fracciones

En esta sección, consideramos polinomios sobre un dominio de factorización único R , típicamente el anillo de los enteros, y sobre su campo de fracciones F , típicamente el campo de los números racionales, y denotamos R [ X ] y F [ X ] el anillos de polinomios en un conjunto de variables sobre estos anillos.

Factorización primitiva de contenido parcial

El contenido de un polinomio p ∈ R [ X ], denotado "cont ( p )", es el MCD de sus coeficientes. Un polinomio q ∈ F [ X ] puede escribirse

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

donde p ∈ R [ X ] yc ∈ R : basta 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:

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

En ambos casos, el contenido se define hasta la multiplicación por una unidad de R .

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

${\ Displaystyle \ 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 ] puede factorizarse como

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

y esta factorización es única hasta la 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

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

y

${\ Displaystyle \ 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 " gcd " será indexada, a continuación, por el anillo en el que se calcula la GCD.

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

${\ Displaystyle \ 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

${\ Displaystyle \ 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

${\ Displaystyle \ 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 polinomiales es esencialmente el mismo problema sobre F [ X ] y sobre R [ X ].

Para polinomios univariados sobre los números racionales, uno 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 Euclid para trabajar solo con polinomios sobre los números enteros. Consisten en reemplazar la división euclidiana, que introduce fracciones, por una llamada pseudo-división , y reemplazar la secuencia restante del algoritmo de Euclides por las llamadas secuencias pseudo-resto (ver más abajo ).

Prueba de que existe GCD para polinomios multivariados

En la sección anterior hemos 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 muestra que esto nos permite probar la existencia de MCD en R [ X ], si existen en R y en F [ X ]. En particular, si existen GCD en R , y si X se reduce a una variable, esto prueba que existen GCD en R [ X ] (el algoritmo de Euclides prueba la existencia de GCD en F [ X ]).

Un polinomio en n variables puede considerarse como un polinomio univariado sobre el anillo de polinomios en ( n - 1) variables. Así, una recursividad en el número de variables muestra que si existen GCDs y puede ser computado en R , entonces existen y se pueden calcular en cada anillo polinomio multivariable sobre R . En particular, si R es el anillo de los números enteros o un campo, entonces los GCD existen en R [ x ₁ , ..., x _n ], y lo que precede proporciona un algoritmo para calcularlos.

La prueba de que un anillo polinomial 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 univariados en un campo (hay ejemplos de campos para los que no existe no existe ningún algoritmo de factorización para los polinomios univariados).

Secuencias de pseudo-resto

En esta sección, consideramos un dominio integral Z (típicamente el anillo Z de los enteros) y su campo de fracciones Q (típicamente el campo Q de los números racionales). Dados dos polinomios A y B en el anillo polinomial univariante Z [ X ], la división euclidiana (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

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

y

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

los restos sucesivos del algoritmo de Euclides son

${\ Displaystyle {\ begin {alineado} & - {\ 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 {alineado}}}$

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

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

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

${\ Displaystyle \ 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-resto es la secuencia de los (pseudo) restos r _i obtenida al reemplazar la instrucción

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

del algoritmo de Euclides por

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

donde α es un elemento de Z que divide exactamente todos los coeficientes del numerador. Las diferentes elecciones de α dan diferentes secuencias de pseudoresto, que se describen en las siguientes subsecciones.

Como los divisores comunes de dos polinomios no se cambian si los polinomios se multiplican por constantes invertibles (en Q ), el último término distinto de cero en una secuencia de pseudo-resto es un MCD (en Q [ X ]) de los polinomios de entrada. Por lo tanto, las secuencias de pseudo-resto permite la computación GCD de en Q [ X ] sin introducir fracciones en Q .

En algunos contextos, es esencial controlar el signo del coeficiente principal del pseudo-resto. Este es típicamente el caso cuando se calculan resultantes y subresultantes , o cuando se usa 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 todos los coeficientes de un resto, lo mismo es cierto para - α ) .

Secuencia de pseudo-resto trivial

La secuencia de resto 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 cual los sucesivos pseudo-residuos son

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

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

${\ displaystyle 1254542875143750 \, X-1654608338437500,}$

${\ displaystyle 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 las secuencias de pseudo-resto triviales.

Secuencia de pseudo-resto primitivo

La secuencia de pseudoresto primitiva consiste en tomar como α el contenido del numerador. Por tanto, todos los r _i son polinomios primitivos.

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

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

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

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

${\ Displaystyle 4663 \, X-6150,}$

${\ Displaystyle 1.}$

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

Secuencia de pseudo-resto subsiguiente

También se puede calcular una secuencia subsultante con pseudo-residuos. El proceso consiste en elegir α de tal forma que todo r _i sea ​​un polinomio subsultante. Sorprendentemente, el cálculo de α es muy fácil (ver más abajo). Por otro lado, la prueba de corrección del algoritmo es difícil, porque debe tener 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 pseudoresto primitiva. Como los cálculos de GCD en Z no son necesarios, la secuencia subsultante con pseudo-residuos proporciona el cálculo más eficiente.

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

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

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

${\ displaystyle 9326 \, X-12300,}$

${\ displaystyle 260708.}$

Los coeficientes tienen un tamaño razonable. Se obtienen sin ningún cálculo GCD, solo divisiones exactas. Esto hace que este algoritmo sea más eficiente que el de las secuencias de pseudo-resto primitivas.

El algoritmo que calcula la secuencia subsultante con pseudo-residuos se da a continuación. En este algoritmo, la entrada ( a , b ) es un par de polinomios en Z [X]. El r _i son los pseudo sucesivos restos en Z [X], las variables i y D _i son enteros no negativos, y las letras griegas indican 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 denotados / son siempre exacta y tienen su resultado sea en Z [X], o en Z .

${\ displaystyle {\ begin {alineado} r_ {0}: = a \\ r_ {1}: = b \ end {alineado}}}$
para (;;) hacer${\ Displaystyle i: = 1}$${\ Displaystyle r_ {i} \ neq 0}$${\ Displaystyle i: = i + 1;}$
     si a continuación, otrafinal si final hacer.${\ Displaystyle {\ begin {alineado} d_ {i} &: = \ deg (r_ {i-1}) - \ deg (r_ {i}) \\\ gamma _ {i} &: = \ operatorname {lc } (r_ {i}) \ end {alineado}}}$
     ${\ Displaystyle i = 1}$ 
        ${\ Displaystyle {\ begin {alineado} \ beta _ {1} &: = (- 1) ^ {d_ {1} +1} \\\ psi _ {1} &: = - 1 \ end {alineado}} }$
    
        ${\ Displaystyle {\ begin {alineado} \ 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 {alineado}}}$
    
    ${\ Displaystyle r_ {i + 1}: = {\ frac {\ operatorname {rem} (\ gamma _ {i} ^ {d_ {i} +1} r_ {i-1}, r_ {i})} { \ beta _ {i}}}}$

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 (deg ( r _{i −1} ) - 1) -ésimo polinomio subresultante. Si deg ( r _i ) <deg ( r _{i −1} ) - 1 , el polinomio deg ( r _i ) -ésimo subresultante 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-residuos para construir secuencias que tengan las mismas propiedades que las secuencias de Sturm . Esto requiere controlar los signos de los sucesivos pseudo-residuos, para tener los mismos signos que en la secuencia de Sturm. Esto se puede hacer definiendo un pseudo-resto modificado como sigue.

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

${\ Displaystyle \ 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 constan de polinomios con coeficientes enteros. La secuencia de pseudo-resto subsultante puede modificarse de manera similar, en cuyo caso los signos de los restos coinciden con los calculados sobre los racionales.

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

Algoritmo modular GCD

Si f y g son polinomios en F [ x ] para algún campo F generado de forma finita , el algoritmo euclidiano es la forma más natural de calcular su MCD. Sin embargo, los sistemas modernos de álgebra por computadora solo lo usan si F es finito debido a un fenómeno llamado hinchamiento de expresión intermedia . Aunque los grados continúan disminuyendo durante el algoritmo euclidiano, si F no es finito, entonces el tamaño de bits de los polinomios puede aumentar (a veces dramáticamente) 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 de bits podría casi duplicarse con una sola operación.

Para acelerar el cálculo, tomar un anillo D para el que f y g están en D [ x ], y tomar un ideal I de tal manera que D / I es un anillo finito. Luego calcule el MCD sobre este anillo finito con el algoritmo euclidiano. Utilizando técnicas de reconstrucción ( teorema chino del resto , reconstrucción racional , etc.) se puede recuperar el GCD de f y g de su imagen de módulo un número de ideales I . Se puede demostrar que esto funciona siempre que haya una descartes imágenes modulares con títulos no mínimos, y evita ideales Me módulo, que una de las principales desvanece coeficientes.

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

Ver también

• Lista de temas polinomiales
• Algoritmo de división multivariante

Referencias

• Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise (2006). Algoritmos en geometría algebraica real, capítulo 4.2 . Springer-Verlag .
• Davenport, James H .; Siret, Yvon; Tournier, Évelyne (1988). Álgebra informática: sistemas y algoritmos para el cálculo algebraico . Traducido del francés por A. Davenport y JH Davenport. Prensa académica. ISBN 978-0-12-204230-0.
• van Hoeij, M .; Monagan, MB (2004). Algoritmos para el cálculo de polinomios GCD sobre campos de funciones algebraicas . ISSAC 2004. págs. 297-304.
• Javadi, SMM; Monagan, MB (2007). Un algoritmo GCD modular disperso para polinomios sobre campos de funciones algebraicas . ISSAC 2007. págs. 187–194.
• Knuth, Donald E. (1969). El arte de la programación informática II . Addison-Wesley. págs. 370–371.
• Knuth, Donald E. (1997). Algoritmos seminuméricos . El arte de la programación informática. 2 (Tercera ed.). Reading, Massachusetts: Addison-Wesley. págs. 439–461, 678–691. ISBN 0-201-89684-2.
• Loos, Rudiger (1982), "Secuencias de resto polinomiales generalizadas", en B. Buchberger; R. Loos; G. Collins (eds.), Álgebra informática , Springer Verlag