Máximo común divisor de polinomios

En álgebra, el máximo común divisor (abreviado frecuentemente 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 cuerpo, el MCD polinómico puede calcularse, como en el caso del MCD entero, mediante el algoritmo euclidiano utilizando la división larga. El MCD polinómico se define sólo hasta la multiplicación por una constante invertible.

La similitud entre el MCD de enteros y el MCD de polinomios permite extender a polinomios univariados todas las propiedades que se pueden deducir del algoritmo de Euclides y de la división de Euclides. Además, el MCD de polinomios tiene propiedades específicas que lo convierten en una noción fundamental en varias á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 calcularlas. Por ejemplo, las raíces múltiples de un polinomio son las raíces del MCD del polinomio y su derivada, y cálculos posteriores del MCD permiten calcular la factorización libre de cuadrados del polinomio, lo que proporciona polinomios cuyas raíces son las raíces de una multiplicidad dada del polinomio original.

El máximo común divisor puede definirse y existe, de manera más general, para polinomios multivariados sobre un cuerpo 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 MCD en el anillo de coeficientes. Estos algoritmos proceden por una recursión sobre el número de variables para reducir el problema a una variante del algoritmo euclidiano. Son una herramienta fundamental en el álgebra computacional, porque los sistemas de álgebra computacional los utilizan sistemáticamente para simplificar fracciones. Por el contrario, la mayor parte de la teoría moderna del MCD polinomial se ha desarrollado para satisfacer la necesidad de eficiencia de los sistemas de álgebra computacional.

Sean p y q polinomios con coeficientes en un dominio integral F, típicamente un cuerpo o los números enteros. Un máximo común divisor de p y q es un polinomio d que divide a p y q, y tal que todo divisor común de p y q también divide a 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 cuerpo y p y q no son ambos cero, un polinomio d es máximo común divisor si y sólo 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 no está definido en este caso.

El máximo común divisor de p y q se suele denotar como "mcd(p, q)".

El divisor común más grande no es único: si d es un GCD de p y q, entonces el polinomio f es otro GCD si y sólo si hay un elemento invertible u de F tales 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 números enteros, esta indeterminación se ha resuelto eligiendo como MCD el único que es positivo (existe otro, que es su opuesto). Con esta convención, el MCD de dos números enteros es también el máximo común divisor (para el ordenamiento habitual). Sin embargo, como no existe un orden total natural para los polinomios sobre un dominio entero, no se puede proceder de la misma manera en este caso. Para polinomios univariados sobre un cuerpo, se puede exigir además que el MCD sea mónico (es decir, que tenga 1 como su coeficiente de 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 mcd(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 tienen el mismo conjunto de MCD que 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 entero, se dice que p y q son polinomios coprimos.

• Como se indicó anteriormente, el GCD de dos polinomios existe si los coeficientes pertenecen a un campo, el anillo de los enteros, o más generalmente a un dominio de factorización único.
• Si c es cualquier divisor común p y qEntonces 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 se basa en la prueba del algoritmo de Euclidean.
• Para cualquier elemento invertible k del anillo de los coeficientes, ${\displaystyle \gcd(p,q)=\gcd(p,kq)}$.
• Por lo tanto ${\displaystyle \gcd(p,q)=\gcd( a_{1}p+b_{1}q,a_{2}p+b_{2}q)}$ para cualquier escalar ${\displaystyle a_{1},b_{1},a_{2},b_{2}$ tales que ${\displaystyle a_{1}b_{2}-a_{2}b_{1}$ es invertible.
• Si ${\displaystyle \gcd(p,r)=1}$Entonces ${\displaystyle \gcd(p,q)=\gcd(p,qr)}$.
• Si ${\displaystyle \gcd(q,r)=1}$Entonces ${\displaystyle \gcd(p,qr)=\gcd(p,q)\,\gcd(p,r)}$.
• Para dos polinomios univarios p y q sobre un campo, existen polinomios a y b, tal que ${\displaystyle \gcd(p,q)=ap+bq}$ y ${\displaystyle \gcd(p,q)}$ divide cada combinación lineal de p y q (Identidad de Bézout).
• El mayor divisor común de tres o más polinomios puede definirse de forma similar a dos polinomios. Puede ser computado recursivamente de GCD de dos polinomios por las identidades: $${\displaystyle \gcd(p,q,r)=\gcd(p,\gcd(q,r)),}$$ y $${\displaystyle \gcd(p_{1},p_{2},\dotsp_{n})=\gcd(p_{1},\gcd(p_{2},\dotsp_{n}).}}$$

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

1. Factorización de los polinomios, en el que se encuentran los factores de cada expresión, entonces se selecciona el conjunto de factores comunes mantenidos por todos dentro de cada conjunto de factores. Este método puede ser útil sólo en casos simples, ya que el factoring suele ser más difícil que calcular el mayor divisor común.
2. El algoritmo de Euclide, que se puede utilizar para encontrar el GCD de dos polinomios de la misma manera que para dos números.

Para hallar el MCD de dos polinomios mediante factorización, simplemente factorizamos los dos polinomios por completo. Luego, tomamos el producto de todos los factores comunes. En esta etapa, no necesariamente tenemos un polinomio mónico, por lo que finalmente multiplicamos esto 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: Halla el MCD de x² + 7x + 6 y x² − 5x − 6.

Por lo tanto, su MCD es x + 1.

La factorización de 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 uso repetido de la división euclidiana. Cuando se utiliza este algoritmo en dos números, el tamaño de los números disminuye en cada etapa. Con los polinomios, el grado de los polinomios disminuye en cada etapa. El último resto distinto de cero, convertido en mónico si es necesario, es el MCD de los dos polinomios.

Más específicamente, para encontrar el gcd de dos polinomios a()x) y b()x), uno puede suponer b ل 0 (Otra vez, el GCD es a()x)), y $${\displaystyle \deg(b(x))\leq \deg(a(x))\,}$$

La división Euclideana proporciona dos polinomios q()x), el quot;ient y r()x), el resto tales que $${\displaystyle a(x)=q_{0}(x)b(x)+r_{0}(x)\quad {\text{and}}\quad \deg(r_{0}(x)) made\deg(b(x)}}}$$

Un polinomio g()x) divide ambos a()x) y b()x) si y sólo si divide ambos b()x) y r₀()x). Así $${\displaystyle \gcd(a(x),b(x))=\gcd(b(x),r_{0}(x)). }$$Ajuste $${\displaystyle a_{1}(x)=b(x),b_{1}(x)=r_{0}(x),}$$uno puede repetir la división Euclidea para conseguir 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})$$así que la secuencia eventualmente alcanzará un punto en el que $${\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: hallar el MCD de x² + 7x + 6 y x² − 5x − 6:

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 utilizando secuencias de pseudorestos, pero, sin cuidado, esto puede introducir números enteros muy grandes durante el cálculo. Por lo tanto, para el cálculo informático, se utilizan otros algoritmos, que se describen a continuación.

Este método funciona únicamente si se puede comprobar la igualdad a cero de los coeficientes que aparecen durante el cálculo. Por lo tanto, 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 un cuerpo finito generado de uno de los cuerpos anteriores. Si los coeficientes son números de punto flotante que representan números reales que se conocen sólo de forma aproximada, entonces se debe conocer el grado del MCD para tener un resultado de cálculo bien definido (es decir, un resultado numéricamente estable; en estos casos se pueden utilizar otras técnicas, generalmente basadas en la descomposición en valores singulares).

El caso de polinomios univariados sobre un cuerpo es especialmente importante por varias razones. En primer lugar, es el caso más elemental y, por lo 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 por ello menos importante, los algoritmos de MCD polinómico y los algoritmos derivados permiten obtener información útil sobre las raíces de un polinomio, sin calcularlas.

La división euclidiana de polinomios, que se utiliza en el algoritmo de Euclides para la computación de GCDs, es muy similar a la división euclidiana de enteros. Su existencia se basa en el siguiente teorema: Dados dos polinomios univarios a y b √ 0 definido sobre un campo, existen dos polinomios q ( quot;ient) y r ( resto) que satisface $${\displaystyle a=bq+r}$$y $${\displaystyle \deg(r)$$Dondedeg(...)" denota el grado y el grado del polinomio cero se define como negativo. Además, q y r se definen singularmente por estas relaciones.

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

Al igual que en el caso de los números enteros, la división euclidiana de los polinomios se puede calcular mediante el algoritmo de división larga. Este algoritmo se presenta habitualmente para el cálculo con lápiz y papel, pero funciona bien en las computadoras cuando se formaliza de la siguiente manera (nótese 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 larga). 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 EuclideaEntrada: a y b √ 0 dos polinomios en la variable x;
Producto: q, el cociente, y r, el resto;

Comienzo q:= 0
 r:= a d:= deg(b)
 c:= lcb)
 mientras deg(r) ≥ d do s:=r)/c) ⋅ xdeg(r) -d q:= q + s r:= r − sb fin do Regreso ()q, r)
final

La prueba de la validez de este algoritmo se basa en el hecho de que durante todo el bucle "while", tenemos a = bq + r y deg(r) es un entero no negativo que decrece en cada iteración. Por lo tanto, la prueba de la validez de este algoritmo también prueba la validez de la división euclidiana.

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

A partir de dos polinomios a y b, el algoritmo de Euclides consiste en sustituir recursivamente el par (a, b) por (b, rem(a, b)) (donde "rem(a, b)" denota el resto de la división euclidiana, calculada por el algoritmo de la sección precedente), hasta que b = 0. El MCD es el último resto distinto de cero.

El algoritmo de Euclid puede ser formalizado en el estilo de programación recurrente como: $${\displaystyle \gcd(a,b):={\begin{cases}a ventaja{if} - ¿Qué?$$

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

r0:= ar1:= bpara ()i:= 1; ri ≤ 0; i:= i + 1) do ri+ 1:= remri−1, ri)fin doRegreso ri-1.

La secuencia de los grados de r_i es estrictamente decreciente. Por lo tanto, después de, como máximo, deg(b) pasos, se obtiene un resto nulo, digamos r_k. Como (a, b) y (b, rem(a,b)) tienen los mismos divisores, el conjunto de divisores comunes no se modifica mediante el algoritmo de Euclides 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 lo tanto, los divisores comunes de r_k−1 y 0. Por lo tanto, r_k−1 es un MCD de a y b. Esto no solo demuestra que el algoritmo de Euclides calcula los MCD, sino que también demuestra que los MCD existen.

La identidad de Bézout es un teorema relacionado con el MCD, demostrado inicialmente para los números enteros, que es válido para todo dominio de ideales principales. En el caso de los polinomios univariados sobre un cuerpo, puede enunciarse de la siguiente manera.

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

${\displaystyle au+bv=g}$ (Identidad de Bélgica)

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

$${\displaystyle \deg(u) seleccion\deg(b)-\deg(g),\quad \deg(v) seleccion\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 difiere del algoritmo de Euclides en que se realizan unos pocos cálculos más en cada iteración del bucle. Por lo tanto, se denomina algoritmo MCD extendido. Otra diferencia con el algoritmo de Euclides es que también utiliza el cociente, denotado "quo", de la división euclidiana en lugar de solo el resto. Este algoritmo funciona de la siguiente manera.

GCD ampliado algoritmo

Entrada: a, b, polinomios univarios

Producto: g, el GCD a y b u, v, como se indica anteriormente
 a1, b1, tal que
 a = g a1 b = g b1Comienzo()r0, r1):=a, b)
()s0, s1):= (1, 0)
()t0, t1):= (0, 1)

 para ()i:= 1; ri ل 0; i:= i+1) do q:= quori−1, ri) ri+ 1:= ri−1 − qri si+ 1:= si−1 − qsi ti+ 1:= ti−1 − qti fin do g:= ri−1 u:= si−1 v:= ti−1 a1:= (−1)i−1 ti b1:= (−1)i tiFinal

La prueba de que el algoritmo satisface su especificación de salida depende del hecho de que, por cada i tenemos $${\displaystyle ¿Qué?$$$${\displaystyle s_{i}t_{i}-t_{i+1}=s_{i}t_{i-1}-t_{i-1}$$la última igualdad que implica $${\displaystyle s_{i}t_{i+1}-t_{i+1}=(-1)^{i}$$La afirmación en los grados se deriva del hecho de que, en cada iteración, los grados s_i y t_i aumento en la mayoría como el grado r_i disminuciones.

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

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

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 se representan habitualmente por polinomios univariados sobre K de grado menor que n.

La adición L es simplemente la adición de polinomios: $${\displaystyle a+_{L}b=a+_{K[X]}b.}$$

La multiplicación en L es la multiplicación de polinomios seguidos por la división por f: $${\displaystyle a\cdot _{L}b=\operatorname {rem} (a._{K[X]}b,f). }$$

La inversa 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 es necesaria una división adicional por f para obtener deg(u) < deg(f).

En el caso de polinomios univariados, existe una fuerte relación entre los máximos comunes divisores y las resultantes. 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 es constante.

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

El i- subresultant polynomial S_i()PQ) de dos polinomios P y Q es un polinomio de grado en la mayoría i cuyos coeficientes son funciones polinómicas de los coeficientes P y Q, y i- principal subresultant coefficient s_i()PQ) es el coeficiente de grado i de S_i()P, Q). Tienen la propiedad que el GCD de P y Q tiene un título d si $${\displaystyle S_{0}(P,Q)=\cdots =s_{d-1}(P,Q)=0\s_{d}(P,Q)\neq 0.}$$

En este caso, S_d()PQ) es un GCD de P y Q y $${\displaystyle 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.

Vamos. φ ser un homomorfismo de anillo R en otro anillo conmutativo S. Se extiende a otro homomorfismo, denotado también φ entre los anillos de polinomios 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)),}$$entonces los polinomios subresultantes y los principales coeficientes de subresultantes φ()P) y φ()Q) son la imagen por φ de los P y Q.

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

Vamos. $${\displaystyle P=p_{0}+p_{1}X+\cdots ###p_{m}X^{m},\quad Q=q_{0}+q_{1}X+\cdots - Sí.$$ser dos polinomios univariados con coeficientes en un campo K. Denotamos ${\fnMicrosoft Sans Ser}$ el K espacio vectorial de dimensión i de polinomios de grado menos que i. Para entero no negativo i tales que i ≤ m y i ≤ n, vamos $${\displaystyle \varphi ¿Qué? {}_{n-i}\times {\mathcal {P}_{m-i}\derecho {\fnMitcal {\fn} {\fnh}} {\fnh} {\fnh} {\fnh}} {\fn}} {\fn}}} {\fnh}}}}}}$$ser el mapa lineal tal que $${\displaystyle \varphi _{i}(A,B)=AP+BQ.}$$

El resultado de P y Q es el determinante de la matriz de Sylvester, que es la matriz (cuare) ${\displaystyle \varphi _{0}$ sobre las bases de los poderes X. Del mismo modo, el i- polinomio subresultante se define en el término de determinantes de submatrices de la matriz ${\displaystyle \varphi _{i}.}$

Describamos estas matrices con más precisión;

Vamos. p_i = 0 para i 0 o i ■ m, y q_i = 0 para i 0 o i ■ n. La matriz de Sylvester es ()m + n) ×m + n)-Matrix tal que el coeficiente del i- la fila y la j- la columna es p_m+j−i para j ≤ n y q_j−i para j ■ n: $${\displaystyle S={\begin{pmatrix}p_{m} < > > ###\p_{m-1} âTMa {m} . . . . . . ###\p_{m-2} {m-1} . . . . . . "0\\vdots > 'ddots > 'p_{m} limit\vdots &\vdots &\ddots &q_{n}\vdots &\vdots &\cdots > p_{m-1} limit\vdots > {1}\cdots 'vdots &q_{0} limitq_{1} {0}\ddots <\vdots > 'vdots > 'ddots > \\vdots >\vdots > 'ddots > p_{1} limit\vdots >s > q_{1}\0 limitada0 " p_{0} unos pocos0 .$$

La matriz T_i de ${\displaystyle \varphi _{i}$ es ()m + n − i) ×m + n − 2i)- Sumatrix S que se obtiene eliminando el último i filas de ceros en la submatrix de las columnas 1 a n − i y n + 1 a m + n − i de S (eso es quitar i columnas en cada bloque y la i últimas filas de ceros). El principal subresultant coefficient s_i es el determinante del m + n − 2i primeras filas de T_i.

Vamos. V_i ser el ()m + n − 2i) ×m + n − i) matriz definida como sigue. Primero agregamos ()i + 1) columnas de ceros a la derecha del ()m + n − 2i − 1) ×m + n − 2i −1) matriz de identidad. Luego bordeamos el fondo de la matriz resultante por una fila consistente en ()m + n − i −1) ceros seguidos Xⁱ, Xⁱ⁻¹,... X, 1: $${\displaystyle {0}={0} {0}={0}={0}={0}={0}=\cdots\0\0\0\0\0\0\0}$$

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 primeras filas m + n − 2i − 1 y la fila (m + n − i − j)-ésima.

No es obvio que, tal como se define, las 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 ${\displaystyle \varphi _{i}$. La definición de la i-th subresultant polynomial S_i muestra que el vector de sus coeficientes es una combinación lineal de estos vectores de columna, y por lo tanto que S_i pertenece a la imagen de ${\displaystyle \varphi _{i}.}$

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

Si, por otro lado, el grado del GCD es i, entonces la identidad de Bézout de nuevo permite probar que los múltiples del GCD que tienen un grado inferior a m + n − i están en la imagen de ${\displaystyle \varphi _{i}$. El espacio vectorial de estos múltiples tiene la dimensión m + n − 2i y tiene una base de polinomios de dos grados diferentes, no menor que i. Esto implica que la submatrix de la m + n − 2i primera filas de la forma de echelon columna de T_i es la matriz de identidad y así s_i no es 0. Así S_i es un polinomio en la imagen de ${\displaystyle \varphi _{i}$, que es un múltiple del GCD y tiene el mismo grado. Es por lo tanto un divisor más común.

La mayoría de los algoritmos de búsqueda de raíces no funcionan bien 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 MCD permite detectar la existencia de múltiples raíces, ya que las múltiples raíces de un polinomio son las raíces del MCD del polinomio y su derivada.

Después de computar el GCD del polinomio y su derivado, otras computaciones GCD proporcionan el completo factorización sin plazas del polinomio, que es una factorización $${\displaystyle f=\prod ¿Qué?$$donde, para cada i, el polinomio f_i o es 1 si f no tiene ninguna raíz de la multiplicidad i o es un polinomio libre de cuadrado (que es un polinomio sin múltiples raíces) cuyas raíces son exactamente las raíces de la multiplicidad i de f (ver el algoritmo de Yun).

Por lo tanto, la factorización sin 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 sin cuadrados de grado inferior. La factorización sin cuadrados también es el primer paso en la mayoría de los algoritmos de factorización de polinomios.

El Secuencia robusta de un polinomio con coeficientes reales es la secuencia de los restos proporcionados por una variante del algoritmo de Euclides aplicado al polinomio y su derivado. Para obtener la secuencia Sturm, uno simplemente reemplaza la instrucción $${\displaystyle r_{i+1}:=\operatorname {rem} (r_{i-1},r_{i})}$$del algoritmo de Euclid por $${\displaystyle 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 lo 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 contenga como máximo una raíz, se obtiene un algoritmo que ubica las raíces reales en intervalos de longitud arbitrariamente pequeña.

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

El contenido de un polinomio p ▪ R[X], denotado "cont(p)", es el GCD de sus coeficientes. Un polinomio q ▪ F[X] puede ser escrito $${\displaystyle q={\frac {C}}$$Donde p ▪ R[X] y c ▪ R: basta tomar para c a múltiples 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}{c}}}}$$En ambos casos, el contenido se define hasta la multiplicación por una unidad de R.

El 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, se trata de un polinomio en R[X] que es primitivo, lo que significa que 1 es un MCD de sus coeficientes.

Así cada polinomio en R[X] o F[X] se puede tener en cuenta $${\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 el inverso de esta unidad.

La lema de Gauss implica que el producto de dos polinomios primitivos es primitivo. De ello se desprende que $${\displaystyle \operatorname {primpart} (pq)=\operatorname {primpart} (p)\operatorname {primpart} (q)}$$y $${\displaystyle \operatorname {cont} (pq)=\operatorname {cont} (p)\operatorname {cont} (q). }$$

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

Si q₁ y q₂ pertenecer 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₂ pertenecer 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 MCD polinómicos es esencialmente el mismo problema sobre F[X] y sobre R[X].

Para polinomios univariados sobre 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 que funcione solo con polinomios sobre números enteros. Estos métodos consisten en reemplazar la división euclidiana, que introduce fracciones, por una denominada pseudodivisión, y reemplazar la secuencia de residuos del algoritmo de Euclides por las denominadas secuencias de pseudoresiduos (ver más abajo).

En la sección anterior hemos visto que el MCD de polinomios en R[X] puede deducirse a partir de los MCD en R y en F[X]. Un análisis más detallado de la demostración muestra que esto nos permite demostrar la existencia de MCD en R[X], si existen en R y en F[X]. En particular, si existen MCD en R, y si X se reduce a una variable, esto demuestra que existen MCD en R[X] (el algoritmo de Euclides demuestra la existencia de MCD en F[X]).

Un polinomio en n variables puede considerarse como un polinomio univariado sobre el anillo de polinomios en (n − 1) variables. Por lo tanto, una recursión sobre el número de variables muestra que si los MCD existen y pueden calcularse en R, entonces existen y pueden calcularse en cada anillo de polinomios multivariado sobre R. En particular, si R es el anillo de los números enteros o un cuerpo, entonces existen MCD 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 univariados sobre un cuerpo (hay ejemplos de cuerpos para los que no existe ningún algoritmo de factorización para los polinomios univariados).

En esta sección, consideramos un dominio integral Z (normalmente el anillo Z de los números enteros) y su campo de fracciones Q (normalmente el campo Q de los números racionales). Dados dos polinomios A y B en el anillo polinomial univariado 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].

Para, si uno aplica el algoritmo de Euclid 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 sucesivos restos del algoritmo de Euclid son $${\displaystyle {\begin{aligned} [5] {9}X^{4}+{\tfrac {1}{9}X^{2}-{2} {1} {3}}},\\\\\\\tfrac {117}{25}}X^{2}-9X+{\tfrac {441}}\2}\2}\2}\2} {21} {\2}}} {\2}}}\2}} {\2}}}}}}}}} {\2}}}}}}\2}}}}\2}}}}}}}\2}}}} {\2}}}}}}}}}} {\2} {\2}}}}}\2}\2}}}}}}}}}}}}}}} {\2}}}}}}}}}}}}} {\2}\2}\2}\2}\2}\2}}}}}}}}}}}}}}}}}}}}}}}}}\2}}}}}}}}}}}}}}}}\$$Se ve que, a pesar del pequeño grado y del pequeño tamaño de los coeficientes de los polinomios de entrada, uno tiene que manipular y simplificar las fracciones enteros de tamaño bastante grande.

Se ha introducido la pseudo-división para permitir una variante del algoritmo de Euclides en la que todos los residuos pertenecen a Z[X].

Si ${\displaystyle \deg(A)=a}$ y ${\displaystyle \deg(B)=b}$ y a ≥ b, el pseudo-remanente de la pseudo-división de A por B, denotado por prem(A,B) es $${\displaystyle \operatorname {prem} (A,B)=\operatorname {rem} (\operatorname {lc} (B)^{a-b+1}A,B),}$$Donde lc(B) es el coeficiente líder de B (el coeficiente de X^b).

El pseudoresto de la pseudodivisión de dos polinomios en Z[X] pertenece siempre a Z[X].

A secuencia pseudo-remanente es la secuencia de los (pseudo) restos r_i obtenido reemplazando la instrucción $${\displaystyle r_{i+1}:=\operatorname {rem} (r_{i-1},r_{i})}$$del algoritmo de Euclid por $${\displaystyle r_{i+1}:={\frac {\fnuncio {prem} (r_{i-1},r_{i}}{\alpha }}}}}}$$Donde α es un elemento Z que divide exactamente cada coeficiente del numerador. Diferentes opciones de α dar diferentes secuencias pseudo-remanente, que se describen en las subsecciones siguientes.

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 pseudorestos es un MCD (en Q[X]) de los polinomios de entrada. Por lo tanto, las secuencias de pseudorestos permiten calcular MCD en Q[X] sin introducir fracciones en Q.

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

La secuencia más simple (definir) sigue siendo consistente 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 la cual los sucesivos pseudo-remanentes son $${\displaystyle -15\,X^{4}+3\,X^{2}-9,}$$$${\displaystyle 15795\,X^{2}+30375\,X-59535,}$$$${\displaystyle 12542875143750\,X-1654608338437500,}$$$${\displaystyle 12593338795500743100931141992187500}$$El número de dígitos de los coeficientes de los restos sucesivos es más que duplicado en cada iteración del algoritmo. Este es el comportamiento típico de las secuencias triviales pseudo-remanente.

La secuencia de pseudorestos primitivos consiste en tomar como α el contenido del numerador. Por lo tanto, todos los r_i son polinomios primitivos.

La secuencia de pseudorestos primitiva es la secuencia de pseudorestos que genera los coeficientes más pequeños. Sin embargo, requiere calcular una cantidad de MCD en Z y, por lo tanto, no es lo suficientemente eficiente para ser utilizada en la práctica, especialmente cuando Z es en sí misma un anillo de polinomios.

Con la misma entrada que en las secciones anteriores, los restos sucesivos, 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 una serie de enteros GCD y divisiones por el GCD han sido computados.

Una sucesión subresultante también puede calcularse con pseudoresiduos. 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 (ver más abajo). Por otra parte, la demostración de la 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 subresultante rara vez son mucho mayores que los de la secuencia primitiva de pseudorestos. Como no se necesitan los cálculos de MCD en Z, la secuencia subresultante con pseudorestos ofrece el cálculo más eficiente.

Con la misma entrada que en las secciones anteriores, los restos sucesivos 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, sólo divisiones exactas. Esto hace que este algoritmo sea más eficiente que el de las secuencias pseudo-remanentes primitivas.

A continuación se muestra el algoritmo que calcula la secuencia subresultante con pseudoresiduos. En este algoritmo, la entrada (a, b) es un par de polinomios en Z[X]. Las r_i son los pseudoresiduos sucesivos en Z[X], las variables i y d_i son números 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 denotadas / son siempre exactas y tienen su resultado ya sea en Z[X] o en Z.

r0:= ar1:= bpara ()i:= 1; ri ل 0; i:= i+1) do di:= deg(ri−1) − Deg(ri) γi:= lcri) si i = 1 entonces β1:= (−1)d1+ 1 ↑1:=-1 más ↑i:=γi−1)di−1 / ↑i−1di−1−1 βi:= −γi−1↑idi terminar si ri+ 1:= remγidi+ 1 ri−1, ri) βifinal for

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 polinomio 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 subresultantes son cero.

Se pueden utilizar pseudoresiduos para construir secuencias que tengan las mismas propiedades que las secuencias de Sturm. Esto requiere controlar los signos de los pseudoresiduos sucesivos, para que tengan los mismos signos que en la secuencia de Sturm. Esto se puede hacer definiendo un pseudoresiduo modificado de la siguiente manera.

Si ${\displaystyle \deg(A)=a}$ y ${\displaystyle \deg(B)=b}$ y a ≥ b, el pseudo-remanente modificado prem2(A, B) de la pseudo-división de A por B es $${\displaystyle \operatorname {prem2} (A,B)=-\operatorname {rem} (\left durable\operatorname {lc} (B)\right WordPress^{a-b+1}A,B),}$$Donde Silenciolc(B)Silencio es el valor absoluto del coeficiente líder 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 pseudoresiduos subresultante puede modificarse de manera similar, en cuyo caso los signos de los residuos coinciden con los calculados sobre los racionales.

Tenga en cuenta que el algoritmo para computar la secuencia pseudo-remanente del subresultante dada arriba calculará polinomios subresultantes incorrectos si se utiliza ${\displaystyle -\mathrm {prem2} (A,B)}$ en lugar de ${\displaystyle \operatorname {prem} (A,B)}$.

Si f y g son polinomios en F[x] para algún cuerpo finito F, el algoritmo euclidiano es la forma más natural de calcular su MCD. Sin embargo, los sistemas de álgebra computacional modernos solo lo utilizan si F es finito debido a un fenómeno llamado aumento de expresión intermedia. Aunque los grados siguen disminuyendo durante el algoritmo euclidiano, si F no es finito, entonces el tamaño de 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 acotados por b conduce a un número racional cuyo denominador está acotado 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, tomemos un anillo D para el cual f y g están en D[x], y tomemos un ideal I tal que D/I sea un anillo finito. Luego, calculemos el MCD sobre este anillo finito con el algoritmo euclidiano. Utilizando técnicas de reconstrucción (teorema del resto chino, reconstrucción racional, etc.) se puede recuperar el MCD de f y g a partir de su imagen módulo un número de ideales I. Se puede demostrar que esto funciona siempre que se descarten imágenes modulares con grados no mínimos y se eviten ideales I módulo en los que se anule un coeficiente principal.

Suppose ${\displaystyle F=\mathbb {} {}}}$, ${\displaystyle D=\Mathbb {Z} [{\sqrt {3}}}$, ${\displaystyle f={\sqrt {3}x^{3}-5x^{2}+4x+9}$ y ${\displaystyle g=x^{4}+4x^{2}+3{\sqrt {3}x-6}$. Si tomamos ${\displaystyle I=(2)}$ entonces ${\displaystyle D/I}$ es un anillo finito (no un campo desde ${\displaystyle I}$ no es maximal en ${\displaystyle D}$). El algoritmo de Euclidean aplicado a las imágenes de ${\displaystyle f,g}$ dentro ${\displaystyle (D/I)[x]}$ éxitos y retornos 1. Esto implica que el GCD ${\displaystyle f,g}$ dentro ${\displaystyle F[x]}$ Debe ser 1 también. Tenga en cuenta que este ejemplo podría ser manejado fácilmente por cualquier método porque los grados eran demasiado pequeños para que la expresión se hiciese bien, pero ilustra que si dos polinomios tienen GCD 1, entonces es probable que el algoritmo modular termine después de un solo ideal ${\displaystyle I}$.

• Lista de temas polinomios
• algoritmo de división multivariable