En álgebra, el MÁXIMO común divisor (frecuentemente abreviado como MCD) de dos polinomios es otro polinomio del grado más alto posible, que es un factor de los dos polinomios originales. Este concepto es análogo al de máximo común divisor de dos enteros.
En el caso importante de polinomios de una sola variable sobre un cuerpo, el polinomio MCD puede ser calculado, como el MCD de dos enteros, mediante el algoritmo de Euclides usando la división polinómica. El polinomio MCD (salvo si se exceptúa la multiplicación por una constante invertible), es único.
La similitud entre el entero MCD y el polinomio MCD permite extender a polinomios de una variable todas las propiedades que se pueden deducir del algoritmo euclidiano y de la división euclídea. Además, el polinomio MCD tiene propiedades específicas que lo convierten en una noción fundamental en diversas áreas del álgebra. Normalmente, las raíces del MCD de dos polinomios son las raíces comunes de los dos polinomios, y esto proporciona información sobre las raíces sin necesidad de calcularlas. Por ejemplo, las raíces múltiples de un polinomio son las raíces del MCD del propio polinomio y de su derivada, y los cálculos adicionales del MCD permiten calcular el polinomio libre de cuadrados del polinomio de partida, lo que proporciona polinomios cuyas raíces son las raíces de un múltiples del polinomio original.
El máximo común divisor puede definirse y existe, de manera más general, para polinomios sobre un cuerpo numérico o sobre el anillo de los números enteros, y también sobre un dominio de factorización única. Existen algoritmos para calcularlos si se dispone de un algoritmo para calcular el MCD en el anillo de coeficientes. Estos algoritmos proceden mediante una recursión sobre el número de variables para reducir el problema a una variante del algoritmo euclidiano. Son una herramienta fundamental en cálculo simbólico, porque los sistemas algebraicos computacionales los usan sistemáticamente para simplificar fracciones. Por el contrario, la mayor parte de la teoría moderna del MCD polinómico se ha desarrollado para satisfacer la necesidad de eficiencia de los sistemas de álgebra por computadora.
Definición general Sean y dos polinomios con coeficientes en un dominio de integridad , normalmente un cuerpo o el anillo de los números enteros.
Un máximo común divisor de y es un polinomio que divide a y que divide a , y tal que cada divisor común de y de también divide a . Cada par de polinomios (ambos no nulos) tiene un MCD si y solo si es un dominio de factorización única.
Si es un cuerpo y y no son ambos cero, un polinomio es un máximo común divisor si y solo si divide tanto a como a , y tiene el mayor grado entre los polinomios que tienen esta propiedad. Si , el MCD es 0. Sin embargo, algunos autores consideran que en este caso el MCD no está definido.
El máximo común divisor de y generalmente se denota como .
El máximo común divisor no es único: si es un MCD de y , entonces el polinomio es otro MCD si y solo si hay un elemento invertible de tal que
y . En otras palabras, el MCD es único excepto si se considera la multiplicación por una constante invertible.
En el caso de los enteros, esta indeterminación se ha resuelto eligiendo como MCD el único que es positivo (hay otro, que es su contrario). Con esta convención, el MCD de dos enteros también es el divisor común más grande (para el orden habitual). Sin embargo, dado que no existe orden total natural entre los polinomios sobre un dominio integral, no se puede proceder de la misma manera aquí. Para polinomios de una sola variable sobre un cuerpo, se puede requerir adicionalmente que el MCD sea un polinomio mónico (es decir, que tenga 1 como su coeficiente del grado más alto), pero en casos más generales no existe una convención general. Por lo tanto, las igualdades como o son abusos comunes de notación que deben leerse como es un MCD de y de ; y como que y tienen el mismo conjunto de MCD que y que . En particular, significa que las constantes invertibles son los únicos divisores comunes. En este caso, por analogía con el caso entero, se dice que y son polinomios coprimos.
Propiedades
Como se indicó anteriormente, el MCD de dos polinomios existe si los coeficientes pertenecen a un cuerpo, el anillo de los números enteros o, de manera más general, a un dominio de factorización única. Si es un divisor común de y , divide al MCD de y de .
para cualquier polinomio . Esta propiedad está en la base de la prueba del algoritmo de euclides. Para cualquier elemento invertible del anillo de los coeficientes, . Por lo tanto, para cualquier escalar tal que sea invertible. Si , entonces . Si , entonces . Para dos polinomios de una variable y sobre un cuerpo, existen polinomios y , de modo que y dividen cada combinación lineal de y de (identidad de Bézout). El máximo común divisor de tres o más polinomios se puede definir de manera similar al de dos polinomios. Puede calcularse de forma recursiva a partir de los MCD de dos polinomios mediante las identidades:
y
MCD mediante cálculo manual Hay varias formas de encontrar el máximo común divisor de dos polinomios. Dos de ellas son:
Factorización de polinomios, mediante la que se determinan los factores de cada expresión, luego se selecciona el conjunto de factores comunes incluidos dentro de ambos conjuntos de factores. Este método puede ser útil solo en casos simples, ya que la factorización suele ser más difícil que calcular el máximo común divisor. El algoritmo de Euclides, que se puede usar para encontrar el MCD de dos polinomios de la misma manera que para dos números enteros.
Factorización Para encontrar el MCD de dos polinomios usando su factorización, basta con factorizar los dos polinomios por completo. A continuación, se selecciona el producto de todos los factores comunes. En esta etapa, no necesariamente se obtiene un polinomio mónico, por lo que finalmente se debe multiplicar por una constante para convertirlo en un polinomio mónico. Este será el MCD de los dos polinomios, ya que incluye todos los divisores comunes, y es mónico.
Ejemplo uno: Encontrar el MCD de y de .
Por lo tanto, su MCD es .
Algoritmo de Euclides Factorizar polinomios puede ser difícil, especialmente si los polinomios tienen un grado grande. El algoritmo de Euclides es un método que funciona para cualquier par de polinomios. Hace un uso repetido de la división euclídea. Cuando se usa este algoritmo con dos números enteros, el tamaño de los números disminuye en cada etapa. Con polinomios, el grado de los polinomios disminuye en cada etapa. El último resto distinto de cero, transformado en mónico si es necesario, es el MCD de los dos polinomios.
Más específicamente, para encontrar el mcd de dos polinomios y , se puede suponer que (de lo contrario, el MCD es ), y
La división euclídea proporciona dos polinomios , el cociente; y , el resto; tales que
Un polinomio divide a y a si y solo si divide a y . Por lo tanto
La configuración
permite repetir la división euclidiana para obtener nuevos polinomios y así sucesivamente. En cada etapa se tiene que
por lo que la secuencia finalmente llegará a un punto en el que
y se obtiene el MCD:
Ejemplo: encontrar el MCD de y :
Dado que es el último resto distinto de cero, es un MCD de los polinomios originales y el polinomio mónico MCD es .
En este ejemplo, no es difícil evitar la introducción de denominadores factorizando 12 antes del segundo paso. Esto siempre se puede hacer usando secuencias de pseudo-resto, pero si no se tiene cuidado con las operaciones, se pueden generar números enteros muy grandes durante el cálculo. Por lo tanto, para los cálculos con computadora, se utilizan otros algoritmos, que se describen a continuación.
Este método funciona solo si se puede probar la igualdad a cero de los coeficientes que aparecen durante el cálculo. Entonces, en la práctica, los coeficientes deben ser números enteros, números racionales, elementos de un cuerpo finito, o deben pertenecer a alguna extensión de cuerpos de uno de los cuerpos anteriores. Si los coeficientes son valores con coma flotante que representan números reales que se conocen solo aproximadamente, entonces se debe conocer el grado del MCD para obtener un resultado de cálculo bien definido (es decir, un resultado provisto de estabilidad numérica; en estos casos se pueden utilizar otras técnicas, generalmente basadas en descomposición en valores singulares.
Polinomios de una variable con coeficientes en un cuerpo
El caso de polinomios de una variable sobre un cuerpo es especialmente importante por varias razones. En primer lugar, es el caso más elemental y, por tanto, aparece en la mayoría de los primeros cursos de álgebra. En segundo lugar, es muy similar al caso de los números enteros, y esta analogía es la fuente de la noción de dominio euclídeo. Una tercera razón es que la teoría y los algoritmos para el caso de varias variables y para los coeficientes en un dominio de factorización única están fuertemente basados en este caso particular. Por último, pero no menos importante, los algoritmos de MCD polinómicos y los algoritmos derivados permiten obtener información útil sobre las raíces de un polinomio, sin calcularlas.
División euclídea La división euclídea de polinomios, que se usa en el Algoritmo de Euclides para calcular el MCD, es muy similar a la división euclídea de números enteros. Su existencia se basa en el siguiente teorema: Dados dos polinomios de una variable a y b ≠ 0 definidos sobre un cuerpo, existen dos polinomios q (el cociente) y r (el resto) que satisfacen
y
donde deg (...) denota el grado; y el grado del polinomio cero se define como negativo. Además, q y r se definen de forma única por estas relaciones.
La diferencia con la división euclidiana de números enteros es que, para los números enteros, el grado se reemplaza por el valor absoluto, y que para tener unicidad se tiene que suponer que r no es negativo. Los anillos para los que existe tal teorema se denominan dominios euclídeos.
Al igual que para los números enteros, la división euclídea de los polinomios puede calcularse mediante el algoritmo de división polinómica. Este algoritmo generalmente se presenta para el cálculo con lápiz y papel, pero funciona bien en computadoras cuando se formaliza de la siguiente manera (téngase en cuenta que los nombres de las variables corresponden exactamente a las regiones de la hoja de papel en un cálculo con lápiz y papel de división de polinomios). En el siguiente cálculo, deg representa el grado de su argumento (con la convención ), y lc representa el coeficiente principal, el coeficiente del grado más alto de la variable.
La prueba de la validez de este algoritmo se basa en el hecho de que durante todo el ciclo "while", se tiene que y es un número entero no negativo que disminuye en cada iteración. Así, la prueba de la validez de este algoritmo también prueba la validez de la división euclídea.
Algoritmo de Euclides En cuanto a los números enteros, la división euclídea permite definir el algoritmo de Euclides para calcular los MCD.
Partiendo de dos polinomios a y b, el algoritmo de Euclides consiste en reemplazar recursivamente el par por (donde "" denota el resto de la división euclídea, calculada por el algoritmo de la sección anterior), hasta obtener b = 0. El MCD es el último resto distinto de cero.
El algoritmo de Euclides se puede formalizar en el estilo de programación recursiva como:
En estilo de programación, dando un nombre a cada resto intermedio, el mismo algoritmo se convierte en: