Màxim comú divisor polinòmic

En àlgebra, el MÁXIMO comú divisor (freqüentment abreviat com MCD) de dos polinomis és un atre polinomi del grau més alt possible, que és un factor dels dos polinomis originals. Este concepte és anàlec al de màxim comú divisor de dos sancers.

En el cas important de polinomis d'una sola variable sobre un cos, el polinomi MCD pot ser calculat, com el MCD de dos sancers, per mig del algoritme de Euclides usant la divisió polinòmica. El polinomi MCD (llevat si s'exceptua la multiplicació per una constant invertible), és únic.

La similitut entre el sancer MCD i el polinomi MCD permet estendre a polinomis d'una variable totes les propietats que es poden deduir de l'algoritme euclidiano i de la divisió euclídea. Ademés, el polinomi MCD té propietats específiques que ho convertixen en una noció fonamental en diverses àrees de l'àlgebra. Normalment, les raïls de el MCD de dos polinomis són les raïls comunes dels dos polinomis, i açò proporciona informació sobre les raïls sense necessitat de calcular-les. Per eixemple, les raïls múltiples d'un polinomi són les raïls de el MCD del propi polinomi i de la seua derivada, i els càlculs adicionals de el MCD permeten calcular el polinomi lliure de quadrats del polinomi de partida, lo que proporciona polinomis les raïls dels quals són les raïls d'un múltiples del polinomi original.

El màxim comú divisor pot definir-se i existix, de manera més general, para polinomis sobre un cos numèric o sobre l'anell dels número entero, i també sobre un domini d'factorización única. Existixen algoritmes per a calcular-los si es dispon d'un algoritme per a calcular el MCD en l'anell de coeficients. Estos algoritmes procedixen per mig d'una recursión sobre el número de variables per a reduir el problema a una variant de l'algoritme euclidiano. Són una ferramenta fonamental en càlcul simbòlic, perque els sistemes algebraics computacionals els usen sistemàticament per a simplificar fraccions. Pel contrari, la major part de la teoria moderna de el MCD polinòmic s'ha desenrollat per a satisfer la necessitat d'eficiència dels sistemes d'àlgebra per computadora.

Definició general

Siguen p i q dos polinomis en coeficients en un domini d'integritat F, normalment un cos o l'anell dels número entero.

Un màxim comú divisor de p i q és un polinomi d que dividix a p i que dividix a q, i tal que cada divisor comuna de p i de q també dividix a d. Cada parell de polinomis (abdós no nuls) té un MCD si i solament si F és un domini d'factorización única.

Si F és un cos i p i q no són abdós zero, un polinomi d és un màxim comú divisor si i solament si dividix tant a p com a q, i té el major grau entre els polinomis que tenen esta propietat. Si p = q = 0, el MCD és 0. No obstant, alguns autors consideren que en este cas el MCD no està definit.

El màxim comú divisor de p i q generalment es denota com mcd(p, q).

El màxim comú divisor no és únic: si d és un MCD de p i q, llavors el polinomi f és un atre MCD si i solament si hi ha un element invertible o de F tal que

$f=ud$

i

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

En atres paraules, el MCD és únic excepto si es considera la multiplicació per una constant invertible.

En el cas dels sancers, esta indeterminación s'ha resolt elegint com MCD l'únic que és positiu (hi ha un atre, que és el seu contrari). En esta convenció, el MCD de dos sancers també és el divisor comú més gran (per a l'orde habitual). No obstant, ya que no existix orde total natural entre els polinomis sobre un domini integral, no es pot procedir de la mateixa manera ací. Per a polinomis d'una sola variable sobre un cos, es pot requerir adicionalment que el MCD siga un polinomi mónico (és dir, que tinga 1 com el seu coeficient del grau més alt), pero en casos més generals no existix una convenció general. Per lo tant, les igualtats com d = mcd(p, q) o mcd(p, q) = mcd(r, s) són abusos comuns de notació que deuen llegir-se com d és un MCD de p i de q; i com que p i q tenen el mateix conjunt de MCD que r i que s. En particular, mcd(p, q) = 1 significa que les constants invertibles són els únics divisores comuns. En este cas, per analogia en el cas sancer, es diu que p i q són polinomis coprimos.

Propietats

• Com es va indicar anteriorment, el MCD de dos polinomis existix si els coeficients pertanyen a un cos, l'anell dels número entero o, de manera més general, a un domini d'factorización única.
• Si c és un divisor comú de p i q, c dividix a el MCD de p i de q.
• $\text{mcd }(p,q)=\text{mcd }(q,p).$
• $\text{mcd }(p,q)=\text{mcd }(q,p+rq)$ per a qualsevol polinomi r. Esta propietat està en la base de la prova de l'algoritme de euclides.
• Per a qualsevol element invertible k de l'anell dels coeficients, $\text{mcd }(p,q)=\text{mcd }(p,kq)$.
• Per lo tant, $\text{mcd }(p,q)=\text{mcd }(a_{1}p+b_{1}q,a_{2}p+b_{2}q)$ per a qualsevol escalar $a_1,b_1,a_2,b_2$ tal que $a_1{b}_2-a_2{b}_1$ siga invertible.
• Si $\text{mcd }(p,r)=1$, llavors $\text{mcd }(p,q)=\text{mcd }(p,qr)$.
• Si $\text{mcd }(q,r)=1$, llavors $\text{mcd }(p,qr)=\text{mcd }(p,q)\text{mcd }(p,r)$.
• Per a dos polinomis d'una variable p i q sobre un cos, existixen polinomis a i b, de modo que $\text{mcd }(p,q)=ap+bq$ i $\text{mcd }(p,q)$ dividixen cada combinació llineal de p i de q (identitat de Bézout).
• El màxim comú divisor de tres o més polinomis es pot definir de manera similar al de dos polinomis. Pot calcular-se de forma recursiva a partir dels MCD de dos polinomis per mig de les identitats:

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

i

$\text{mcd }(p_1,p_2,\dots ,p_n)=\text{mcd }(p_1,\text{mcd }(p_2,\dots ,p_n)).$

Bibliografia

• (1988) Computer algebra: systems and algorithms for algebraic computation, Translated from the French by A. Davenport and J.H. Davenport, Academic Press. ISBN 978-0-12-204230-0.
• (2004).«Algorithms for polynomial GCD computation over algebraic function fields».

297–304.

• (2007).«A sparse modular GCD algorithm for polynomials over algebraic function fields».

187–194.

• Knuth, Donald E. (1969). The Art of Computer Programming II, Addison-Wesley, pp. 370–371.
• (1982).«Computer Algebra».Springer Verlag.