Máximo común divisor de un polinomio

Para hallar el máximo común divisor (MCD) de dos polinomios mediante factorización, simplemente factoriza ambos polinomios por completo. Luego, multiplica todos los factores comunes. En este punto, no necesariamente obtendremos un polinomio mónico, así que finalmente multiplícalo 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 : Encuentra el MCD de x² + 7x + 6 ^y x² − 5x ⁻ 6 .

Por lo tanto, su MCD es x + 1 .

Factorizar polinomios puede ser difícil, especialmente si tienen un grado elevado. El algoritmo euclidiano es un método que funciona para cualquier par de polinomios. Utiliza repetidamente la división euclidiana . Al aplicar este algoritmo a dos números, el tamaño de estos disminuye en cada paso. En el caso de los polinomios, el grado disminuye en cada paso. El último resto distinto de cero, convertido a mónico si es necesario, es el máximo común divisor (MCD) de los dos polinomios.

Más específicamente, para hallar 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 , tales que $${\displaystyle a(x)=q_{0}(x)b(x)+r_{0}(x)\quad {\text{y}}\quad \deg(r_{0}(x))<\deg(b(x))}$$

Un polinomio g ( x ) divide tanto a ( x ) como a b ( x ) si y solo si divide tanto a b ( x ) como _a 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 eventualmente llegará a un punto en el que $${\displaystyle b_{N}(x)=0}$$ y uno tiene el MCD: $${\displaystyle \gcd(a,b)=\gcd(a_{1},b_{1})=\cdots =\gcd(a_{N},0)=a_{N}.}$$

Ejemplo: hallar el MCD de x² + 7x + ⁶ 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 el 12 antes del segundo paso. Esto siempre se puede lograr utilizando secuencias de pseudoresto , pero, sin cuidado, esto puede introducir números enteros muy grandes durante el cálculo. Por lo tanto, para el cálculo computacional se utilizan otros algoritmos, que se describen a continuación.

Este método solo funciona 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 enteros , números racionales , elementos de un cuerpo finito o pertenecer a alguna extensión de cuerpo finitamente generada de uno de los cuerpos anteriores. Si los coeficientes son números de coma flotante que representan números reales conocidos solo de forma aproximada, entonces se debe conocer el grado del MCD para obtener un resultado numéricamente estable ; en este caso, se pueden utilizar otras técnicas, generalmente basadas en la descomposición en valores singulares .

La división euclidiana de polinomios, que se utiliza en el algoritmo de Euclides para calcular el MCD, es muy similar a la división euclidiana de enteros. Su existencia se basa en el siguiente teorema: Dados dos polinomios univariados${\textstyle a}$y${\displaystyle b\neq 0}$definidos sobre un cuerpo , existen dos polinomios${\displaystyle q}$(el cociente ) y${\displaystyle 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. Además, q y r están definidos unívocamente por estas relaciones.

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

Al igual que con los números enteros, la división euclidiana de los polinomios se puede calcular mediante el algoritmo de división larga . Este algoritmo se suele presentar para cálculos manuales, pero funciona bien en ordenadores 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 manual 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 euclidiana

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

comenzar

q := 0 r := a d := deg( b ) c := lc( b ) mientras deg( r ) ≥ d hacer s := (lc( r )/ c ) ⋅ x deg( r )− d q := q + s r := r − sb fin hacer devolver ( q , r )

fin

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 disminuye 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 el máximo común divisor (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 euclidiana, calculado mediante el algoritmo de la sección anterior), hasta que b = 0. El MCD es el último resto distinto de cero.

El algoritmo de Euclides puede formalizarse en el estilo de programación recursiva de la siguiente manera: $${\displaystyle \gcd(a,b):={\begin{cases}a&{\text{if }}b=0\\\gcd(b,\operatorname {rem} (a,b))&{\text{otherwise}}.\end{cases}}}$$

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

r ₀  := a r ₁  := b

para ( i  := 1; r _i ≤ 0; i  := i + 1) hacer

r i +1 := rem( r i −1 , r i )

fin hacer

devolver r _{i -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 por 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. Así, r _{k −1} es un MCD de a y b . Esto no solo prueba que el algoritmo de Euclides calcula MCD, sino que también prueba que los MCD existen.

La identidad de Bézout es un teorema relacionado con el MCD, demostrado inicialmente para los enteros, que es válido para todo dominio ideal principal . En el caso de los polinomios univariados 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 existen dos polinomios u y v tales que

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

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

$${\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 radica en que existe un algoritmo eficiente para calcular los polinomios u y v . Este algoritmo difiere del algoritmo de Euclides por realizar algunos cálculos adicionales en cada iteración del bucle. Por lo tanto, se le 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.

Algoritmo extendido de MCD

Entrada: a , b , polinomios univariados

Producción:

g , el MCD de a y b u , v , como en la afirmación anterior a 1 , b 1 , de tal manera que a = g a 1 b = g b 1

Comenzar

 ( r 0 , r 1 ) := ( a , b ) ( s 0 , s 1 ) := (1, 0) ( t 0 , t 1 ) := (0, 1) para ( i := 1; r i ≠ 0; i := i +1) hacer q := quo( r i −1 , r i ) r i +1 := r i −1 − qr i s i +1 := s i −1 − qs i t i +1 := t i −1 − qt i fin hacer g := r i −1 u := s i −1 v := t i −1 a 1 := (−1) i −1 t i b 1 := (−1) i s i

Fin

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 implica $${\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 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 gratuitamente el cociente de los polinomios de entrada por su máximo común divisor (MCD).

En el caso de polinomios univariados, existe una fuerte relación entre el máximo común divisor y el resultante . Más precisamente, el resultante de dos polinomios P ​​y Q es una función polinómica de los coeficientes de P y Q que tiene 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 genéricamente el MCD de dos polinomios, y el resultante es el polinomio subresultante 0. ^{[ 1 ]}

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 polinómicas de los coeficientes de P y Q , y el i -ésimo coeficiente subresultante principal 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 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 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 de anillos de R en otro anillo conmutativo S. Se extiende a otro homomorfismo, también denotado φ, entre los anillos de polinomios sobre 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 coeficientes subresultantes principales de φ ( P ) y φ ( Q ) son la imagen por φ de los de P y Q .

Los subresultantes poseen dos propiedades importantes que los hacen fundamentales para el cálculo computacional del máximo común divisor (MCD) de dos polinomios con coeficientes enteros. En primer lugar, su definición mediante determinantes permite acotar, a través de la desigualdad de Hadamard , el tamaño de los coeficientes del MCD. En segundo lugar, esta cota y la propiedad de buena especialización permiten calcular el MCD de dos polinomios con coeficientes enteros mediante computación modular y el teorema chino del resto (véase más adelante ).

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 ] y c ∈ R : basta con 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, se trata de un polinomio en R [ X ] que es primitivo , lo que significa que 1 es el MCD de sus coeficientes.

Por lo tanto, todo polinomio en R [ X ] o F [ X ] puede factorizarse como $${\displaystyle p=\operatorname {cont} (p)\,\operatorname {primpart} (p),}$$ y esta factorización es única salvo la multiplicación del contenido por una unidad de R y de la parte primitiva por el inverso de esta unidad.

El lema de Gauss implica que el producto de dos polinomios primitivos es primitivo. De ello se deduce 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 anterior 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 ₂ 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 de polinomios es esencialmente el mismo problema sobre F [ X ] y sobre R [ X ] .

Para polinomios univariados sobre los números racionales, podría pensarse que el algoritmo de Euclides es un método conveniente para calcular el MCD. Sin embargo, implica simplificar una gran cantidad de fracciones de enteros, y el algoritmo resultante no es eficiente. Por esta razón, se han diseñado métodos para modificar el algoritmo de Euclides y que funcionen únicamente con polinomios sobre los enteros. Estos métodos consisten en reemplazar la división euclidiana, que introduce fracciones, por una denominada pseudodivisión , y reemplazar la secuencia de restos del algoritmo de Euclides por secuencias de pseudorestos (véase más adelante ).

En la sección anterior vimos que el MCD de polinomios en R [ X ] se puede deducir 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 probar 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 prueba que existen MCD en R [ X ] (el algoritmo de Euclides prueba 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. Así, una recursión sobre el número de variables muestra que si existen MCD y pueden calcularse en R , entonces existen y pueden calcularse en todo anillo de polinomios multivariados sobre R . En particular, si R es el anillo de los enteros o un cuerpo, entonces existen MCD en R [ x ₁ , ..., x _n ] , y lo anterior proporciona un algoritmo para calcularlos.

La demostración de que un anillo de polinomios sobre un dominio de factorización única también es un dominio de factorización única 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).

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 cual los pseudorestos sucesivos 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 un comportamiento típico de las secuencias de pseudorestos triviales.

La secuencia pseudo-resto primitiva consiste en tomar por α el contenido del numerador. Por lo tanto, todos los r _i son polinomios primitivos.

La secuencia de pseudorestos primitiva es aquella que genera los coeficientes más pequeños. Sin embargo, requiere calcular varios MCD en Z , por lo que no es suficientemente eficiente para su uso práctico, especialmente cuando Z es 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 se han calculado varios máximos comunes divisores (MCD) y divisiones por el MCD.

También se puede calcular una secuencia subresultante con pseudorestos. El proceso consiste en elegir α de tal manera que cada r _i sea un polinomio subresultante. Sorprendentemente, el cálculo de α es muy sencillo (véase más adelante). Por otro lado, la demostración de la corrección del algoritmo es compleja, ya que debe tener en cuenta todas las posibilidades de diferencia de grados entre dos restos consecutivos.

Los coeficientes en la secuencia subresultante rara vez son mucho mayores que los de la secuencia primitiva de pseudorestos. Dado que no se requieren cálculos de MCD en Z , la secuencia subresultante con pseudorestos proporciona 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 necesidad de calcular el máximo común divisor, solo mediante divisiones exactas. Esto hace que este algoritmo sea más eficiente que el de las secuencias de pseudoresto primitivas.

El algoritmo que calcula la secuencia subresultante con pseudorestos se presenta a continuación. En este algoritmo, la entrada ( a , b ) es un par de polinomios en Z [ X ] . Los rᵢ son los pseudorestos sucesivos en Z [ X ] , las variables i y dᵢ son enteros no negativos, y las letras griegas denotan elementos en Z. Las funciones _y denotan el grado de un polinomiodeg() 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 en Z [ X ] o en Z.rem()

r ₀  := a r ₁  := b para ( i  := 1; r _i ≠ 0; i  := i +1) hacer

d i := deg( r i −1 ) − deg ( r i ) γ i := lc ( r i ) si i = 1 entonces β 1 := (−1) d 1 +1 ψ 1 := −1 sino ψ i := (− γ i −1 ) d i −1 / ψ i −1 d i −1 −1 β i := − γ i −1 ψ i d i fin si r i +1 := rem( γ i d i +1 r i −1 , r i ) / β i

fin para

Nota: "lc" significa 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 subresultantes son cero.

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

Si${\displaystyle \deg(A)=a}$y${\displaystyle \deg(B)=b}$y a ≥ b , el pseudoresto modificado prem2( A , B ) de la pseudodivisión de A por B es $${\displaystyle \operatorname {prem2} (A,B)=-\operatorname {rem} (\left|\operatorname {lc} (B)\right|^{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 recuperar secuencias de Sturm formadas por polinomios con coeficientes enteros. La secuencia de pseudorestos resultante puede modificarse de forma similar, en cuyo caso los signos de los restos coinciden con los calculados sobre los números racionales.

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