Álgebra Superior II: Máximo común divisor de polinomios y algoritmo de Euclides

2 respuestas

Introducción

En esta entrada continuamos estudiando propiedades aritméticas del anillo de polinomios con coeficientes reales. En la entrada anterior introdujimos el algoritmo de la división, la noción de divisibilidad y los polinomios irreducibles. Además, mostramos el teorema del factor y el teorema del residuo. Lo que haremos ahora es hablar del máximo común divisor de polinomios.

Mucha de la teoría que desarrollamos en los enteros también se vale para \mathbb{R}[x]. Como en \mathbb{Z}, lo más conveniente para desarrollar esta teoría es comenzar hablando de ideales. Con estos buenos cimientos, veremos que el máximo común divisor de dos polinomios se puede escribir como “combinación lineal de ellos”. Para encontrar la combinación lineal de manera práctica, usaremos de nuevo el algoritmo de Euclides.

Antes de comenzar, haremos una aclaración. Hasta ahora hemos usado la notación f(x), g(x),h(x), etc. para referirnos a polinomios. En esta entrada frecuentemente usaremos nada más f,g,h, etc. Por un lado, esto simplificará los enunciados y demostraciones de algunos resultados. Por otro lado, no corremos el riesgo de confusión pues no evaluaremos a los polinomios en ningún real.

Ideales de \mathbb{R}[x]

Comenzamos con la siguiente definición clave, que nos ayuda a hacer las demostraciones de máximo común divisor de polinomios de manera más sencilla.

Definición. Un subconjunto I de \mathbb{R}[x] es un ideal si pasa lo siguiente:

  1. El polinomio cero de \mathbb{R}[x] está en I.
  2. Si f y g son elementos de \mathbb{R}[x] en I, entonces f+g está en I.
  3. Si f y g son elementos de \mathbb{R}[x], y f está en I, entonces fg está en I.

Al igual que en los enteros, los únicos ideales consisten de múltiplos de algún polinomio. El siguiente resultado formaliza esto.

Teorema (caracterización de ideales en \mathbb{R}[x]). Un subconjunto I es un ideal de \mathbb{R}[x] si y sólo si existe un polinomio f tal que

    \[I=f\mathbb{R}[x]:=\{fg: g \in \mathbb{R}[x]\}.\]

Demostración de “la ida”. Primero mostraremos que cualquier conjunto de múltiplos de un polinomio dado f es un ideal. Tomemos f en \mathbb{R}[x] y

    \[I=f\mathbb{R}[x]=\{fg: g \in \mathbb{R}[x]\}.\]

La propiedad (1) de la definición de ideal se cumple pues tomando g=0 tenemos que f\cdot 0 = 0 está en I.

Para la propiedad (2), tomamos fg_1 en I y fg_2 en I, es decir, con g_1 y g_2 en \mathbb{R}[x]. Su suma es, por la ley de distribución, el polinomio f\cdot (g_1+g_2), que claramente está en I pues es un múltiplo de f.

Para la propiedad (3), tomamos fg en I y h en \mathbb{R}[x]. El producto (fg)\cdot h es, por asociatividad, igual al producto f\cdot(gh), que claramente está en I. De esta forma, I cumple (1), (2) y (3) y por lo tanto es un ideal.

\square

Demostración de “la vuelta”. Mostraremos ahora que cualquier ideal I es el conjunto de múltiplos de un polinomio. Si I=\{0\}, que sólo tiene al polinomio cero, entonces I es el conjunto de múltiplos del polinomio 0. Así, podemos suponer que I tiene algún elemento que no sea el polinomio 0.

Consideremos el conjunto A de naturales que son grado de algún polinomio en I. Como I tiene un elemento no cero, A es no vacío. Por el principio del buen orden, A tiene un mínimo, digamos n. Tomemos en I un polinomio f de grado n. Afirmamos que I es el conjunto de múltiplos de f, es decir,

    \[I=f\mathbb{R}[x].\]

Por un lado, como f está en I y I es un ideal, por la propiedad (3) de la definición de ideal se tiene que fg está en I para todo g en \mathbb{R}[x]. Esto muestra la contención f\mathbb{R}[x]\subseteq I.

Por otro lado, supongamos que hay un elemento h que está en I, pero no es múltiplo de f. Por el algoritmo de la división, podemos encontrar polinomios q y r tales que h-qf=r y r es el polinomio cero o de grado menor a f. No es posible que r sea el polinomio cero pues dijimos que h no es múltiplo de f. Así, r no es el polinomio cero y su grado es menor al de f.

Notemos que -qf está en I por ser un múltiplo de f y que h está en I por cómo lo elegimos. Por la propiedad (2) de la definición de ideal se tiene entonces que r=h+(-qf) también está en I. Esto es una contradicción, pues habíamos dicho que f era un polinomio de grado mínimo en I, pero ahora r tiene grado menor y también está en I. Por lo tanto, es imposible que exista un h en I que no sea múltiplo de f. Esto muestra la contención I\subseteq f\mathbb{R}[x].

\square

El teorema anterior nos dice que cualquier ideal se puede escribir como los múltiplos de un polinomio f. ¿Es cierto que este polinomio f es único? Para responder esto, pensemos en qué sucede si se tiene

    \[f\mathbb{R}[x]=g\mathbb{R}[x],\]

o, dicho de otra forma, pensemos en qué sucede si f divide a g y g divide a f.

Si alguno de f ó g es igual a 0, entonces el otro también debe de serlo. Así, podemos suponer que ninguno de ellos es igual a 0. Como g divide a f, podemos escribir a f como hg para h un polinomio no cero. De manera similar, podemos escribir a g como un polinomio kf para k un polinomio no cero. Pero entonces

    \[f=hg=hkf.\]

El grado del lado izquierdo es \deg(f) y el del derecho es \deg(h)+\deg(k)+\deg(f), de donde obtenemos que \deg(h)=\deg(k)=0. En otras palabras, concluimos que h y k son polinomios constantes y distintos de cero. Resumimos esta discusión a continuación.

Proposición. Tomemos f(x) y g(x) polinomios en \mathbb{R}[x] distintos del polinomio 0. Si f(x) divide a g(x) y g(x) divide a f(x), entonces f(x)=hg(x) para un real h\neq 0. Del mismo modo, si f(x)=hg(x) con h un real, entonces f(x) divide a g(x) y g(x) divide a f(x).

Cuando sucede cualquiera de las cosas de la proposición anterior, decimos que f(x) y g(x) son asociados.

Ya que no hay un único polinomio que genere a un ideal, nos conviene elegir a uno de ellos que cumpla una condición especial. El coeficiente principal de un polinomio es el que acompaña al término de mayor grado. En otras palabras, si p(x) es un polinomio de grado n dado por

    \[p(x)=a_0+\ldots+a_nx^n,\]

con a_n\neq 0, entonces a_n es coeficiente principal.

Definición. Un polinomio es mónico si su coeficiente principal es 1.

Por la proposición anterior, existe un único polinomio mónico asociado a p(x), y es \frac{1}{a_n}p(x). Podemos resumir las ideas de esta sección mediante el siguiente teorema.

Teorema. Para todo ideal I de \mathbb{R}[x] distinto del ideal \{0\}, existe un único polinomio mónico f tal que I es el conjunto de múltiplos de f, en símbolos,

    \[I=f\mathbb{R}[x].\]

Máximo común divisor de polinomios

Tomemos f y g polinomios en \mathbb{R}[x]. Es sencillo ver, y queda como tarea moral, que el conjunto

    \[f\mathbb{R}[x]+g\mathbb{R}[x]=\{rf+sg: r,s \in \mathbb{R}[x]\}\]

satisface las propiedades (1), (2) y (3) de la definición de ideal. Por el teorema de caracterización de ideales, la siguiente definición tiene sentido.

Definición. El máximo común divisor de f y g es el único polinomio mónico d en \mathbb{R}[x] tal que

    \[f\mathbb{R}[x]+g\mathbb{R}[x] = d\mathbb{R}[x].\]

A este polinomio lo denotamos por \MCD{f,g}.

De manera inmediata, de la definición de \MCD{f,g}, obtenemos que es un elemento de f\mathbb{R}[x]+g\mathbb{R}[x], osea, una combinación lineal polinomial de f y g. Este es un resultado fundamental, que enunciamos como teorema.

Teorema (identidad de Bézout). Para f y g en \mathbb{R}[x] existen polinomios r y s en \mathbb{R}[x] tales que

    \[\MCD{f,g}=rf+sg.\]

El nombre que le dimos a \MCD{f,g} tiene sentido, en vista del siguiente resultado.

Teorema. Para f y g en \mathbb{R}[x] distintos del polinomio cero se tiene que:

  • \MCD{f,g} divide a f y a g.
  • Si h es otro polinomio que divide a f y a g, entonces h divide a \MCD{f,g}.

Demostración. Por definición,

    \[f\mathbb{R}[x]+g\mathbb{R}[x] = \MCD{f,g}\mathbb{R}[x].\]

El polinomio f pertenece al conjunto del lado izquierdo, pues lo podemos escribir como

    \[1\cdot f + 0 \cdot g,\]

así que también está en el lado derecho. Por ello, f es un múltiplo de \MCD{f,g}. De manera similar se prueba que g es un múltiplo de \MCD{f,g}.

Para la segunda parte, escribimos a \MCD{f,g} como combinación lineal polinomial de f y g,

    \[\MCD{f,g}=rf+sg.\]

De aquí es claro que si h divide a f y a g, entonces h divide a \MCD{f,g}.

\square

Todo esto va muy bien. El máximo común divisor de dos polinomios en efecto es un divisor, y es “el mayor”, en un sentido de divisibilidad. Además, como en el caso de \mathbb{Z}, lo podemos expresar como una combinación lineal de sus polinomios. En la tarea moral puedes ver algunos ejemplos que hablan del concepto dual: el mínimo común múltiplo.

El algoritmo de Euclides

Al igual que como sucede en los enteros, podemos usar el algoritmo de la división iteradamente para encontrar el máximo común divisor de polinomios, y luego revertir los pasos para encontrar de manera explícita al máximo común divisor como una combinación lineal polinomial de ellos. Es un buen ejercicio enunciar y demostrar que esto es cierto. No lo haremos aquí, pero veremos un ejemplo de cómo aplicar el algoritmo.

Problema: Encuentra el máximo común divisor de los polinomios

    \begin{align*}a(x)&=x^7+x^6+x^5+x^4+x^3+x^2+x+1\\b(x)&=x^4+x^3+x^2+x+1,\end{align*}

y exprésalo como combinación lineal de a(x) y b(x).

Solución. Aplicando el algoritmo de la división repetidamente, tenemos lo siguiente:

    \begin{align*}a(x)&=x^3b(x)+(x^2+x+1)\\b(x)&=x^2(x^2+x+1)+(x+1)\\x^2+x+1&=x(x+1)+1.\end{align*}

Esto muestra que a(x) y b(x) tienen como máximo común divisor al polinomio 1. Por lo que discutimos antes, debe haber una combinación lineal polinomial de a(x) y b(x) igual a 1 Para encontrarla de manera explícita, invertimos los pasos:

    \begin{equation*}\begin{split}1 & =(x^2+x+1)-x(x+1)\\& =(x^2+x+1)-x(b(x)-x^2(x^2+x+1))\\& =(x^2+x+1)(x^3+1)-xb(x)\\& =(x^3+1)(a(x)-x^3(b(x))-xb(x)\\& =(x^3+1)a(x)-x^3(x^3+1)b(x)-xb(x)\\& =(x^3+1)a(x)+(-x^6-x^3-x)b(x)\end{split}\end{equation*}

Así, concluimos que una combinación lineal que sirve es:

    \[(x^3+1)a(x)+(-x^6-x^3-x)b(x) = 1.\]

\square

Tarea moral

Los siguientes ejercicios no forman parte de la evaluación del curso, pero te servirán para entender mucho mejor los conceptos vistos en esta entrada, así como temas posteriores.

  • Verifica que el conjunto

        \[f\mathbb{R}[x]+g\mathbb{R}[x]=\{rf+sg: r,s \in \mathbb{R}[x]\}\]

    satisface las propiedades (1), (2) y (3) de la definición de ideal.
  • Encuentra el máximo común divisor de los polinomios x^8-1 y x^6-1. Exprésalo como combinación lineal de ellos.
  • Muestra que la intersección de dos ideales de \mathbb{R}[x] es un ideal de \mathbb{R}[x].
  • Al único polinomio mónico m tal que

        \[f\mathbb{R}[x]\cap g\mathbb{R}[x]=m\mathbb{R}[x]\]

    le llamamos el mínimo común múltiplo de f y g, y lo denotamos \mcm{f,g}. Muestra que es un múltiplo de f y de g y que es “mínimo” en el sentido de divisibilidad.
  • Muestra que si f y g son polinomios mónicos en \mathbb{R}[x] distintos del polinomio cero, entonces fg = \MCD{f,g} \mcm{f,g}. ¿Es necesaria la hipótesis de que sean mónicos? ¿La puedes cambiar por una hipótesis más débil?

2 comentarios en “Álgebra Superior II: Máximo común divisor de polinomios y algoritmo de Euclides”

  1. junior micha velasque

    Buenas noches Dr. L.Martinez , disculpe usted la molestia quisiera, por favor, que me recomiende libros de donde pueda leer acerca de este tema. Estudio Matemática en Perú; sin embargo no sé que libro me podria recomendar para poder estudiar el tema de MCD de polinomios y como expresarlos como combinación lineal. Estaria muy agradecido de que me pudiera responder .,disculpe las molestias, buenas noches.

    Responder ↓
    1. LeoLeo Autor

      Hola. Aquí mismo en el blog puedes leer de polinomios en la parte de “Docencia -> Álgebra Superior II”. Luego, en esta misma entrada puedes leer acerca de cómo expresar al MCD como combinación lineal.

      Responder ↓

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.