Archivo de la etiqueta: aritmética

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

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?

Álgebra Superior II: Algoritmo de la división, teorema del factor y teorema del residuo

Introducción

Tal vez te hayas dado cuenta de que ya hablamos de suma, producto y resta de polinomios, pero aún no hemos hablado de la división. Una razón es que no todos los polinomios tienen inverso multiplicativo. Sin embargo, los polinomios sí tienen un algoritmo de la división parecido al que estudiamos para el conjunto \mathbb{Z} de enteros. A partir de él podemos extender varios de los conceptos aritméticos de \mathbb{Z} a \mathbb{R}[x]: divisibilidad, máximo común divisor, factorización, etc. Luego, estos aspectos se pueden conectar a evaluación de polinomios mediante el un teorema clave: el teorema del factor.

Como recordatorio, hasta ahora, ya construimos el anillo \mathbb{R}[x] de polinomios con coeficientes reales y vimos que era un dominio entero. También, vimos que una copia de \mathbb{R} vive en \mathbb{R}[x], con lo justificamos pasar de la notación de sucesiones, a la notación usual de polinomios usando el símbolo x y sus potencias. En la entrada anterior también hablamos de del grado de un polinomio (cuando no es el polinomio cero), de la evaluación de polinomios y de raíces.

Algoritmo de la división

Recordemos que en \mathbb{Z} tenemos un algoritmo de la división que dice que para enteros a y b\neq 0 existen únicos enteros q y r tales que a=qb+r y 0\leq r < |b|.

En \mathbb{R}[x] hay un resultado similar. Pero hay que tener cuidado al generalizar. En \mathbb{R}[x] no tenemos una función valor absoluto que nos permita decir que encontramos un «residuo más chiquito». Para la versión polinomial del algoritmo de la división tenemos que usar una función que diga «qué tan grande es un polinomio»: el grado.

Teorema (algoritmo de la división en \mathbb{R}[x]). Sean f(x) y g(x) polinomios en \mathbb{R}[x], donde g(x) no es el polinomio cero. Entonces, existen únicos polinomios q(x) y r(x) en \mathbb{R}[x] tales que

    \[f(x)=q(x)g(x)+r(x),\]

en donde r(x) es el polinomio cero, o \deg(r(x))<\deg(g(x)).

Demostración. Probaremos la parte de existencia. La parte de unicidad queda como tarea moral. Para probar la existencia, haremos inducción fuerte sobre el grado de f(x). Sin embargo, antes de poder hacer esto, necesitamos hacer el caso en el que f(x) no tiene grado, es decir, cuando es el polinomio cero.

Si f(x) es el polinomio cero, entonces g(x)=0 y r(x)=0 son polinomios que funcionan, pues 0=0\cdot 0 y r(x) es el polinomio cero.

Asumamos entonces a partir de ahora que f(x) no es el polinomio cero. Hagamos inducción sobre el grado de f(x). Si f(x) es de grado 0, entonces es un polinomio de la forma f(x)=a para a en \mathbb{R}. Hay dos casos de acuerdo al grado de g(x):

  • Si g(x) es de grado 0, es de la forma g(x)=b para un real no cero y podemos tomar q(x)=a/b y r(x)=0.
  • Si g(x) es de grado mayor a 0, entonces tomamos q(x)=0 y r(x)=f(x). Esta es una elección válida pues se cumple

        \begin{align*}\deg(r(x))&=\deg(f(x))\\& =0\\& <\deg(g(x)).\end{align*}

Esto termina la demostración de la base inductiva.

Supongamos que el resultado es cierto para cuando f(x) tiene grado menor a n y tomemos un caso en el que f(x) tiene grado n. Hagamos de nuevo casos con respecto al grado de g(x), al que llamaremos m. Si m>n, entonces tomamos q(x)=0 y r(x)=f(x), que es una elección válida pues

    \[\deg(r(x))=n<m.\]

En el caso de que m\leq n, escribamos explícitamente a f(x) y a g(x) en términos de sus coeficientes como sigue:

    \begin{align*}f(x)&=a_0+\ldots+a_nx^n\\g(x)&=b_0+\ldots+b_mx^m.\end{align*}

Consideremos el polinomio

    \[h(x):=f(x)-\frac{a_n}{b_m}x^{n-m}g(x).\]

En h(x) justo se cancela el término con x^n, así que su grado es menor al de f(x) y por lo tanto podemos usar la hipótesis inductiva para escribir

    \[h(x)=t(x)g(x)+u(x)\]

con u(x) el polinomio 0 o \deg(u(x))<\deg(g(x)). De esta forma,

    \begin{align*}f(x)&=t(x)g(x)+u(x)+\frac{a_n}{b_m}x^{n-m}g(x)\\&=\left(t(x)+\frac{a_n}{b_m}x^{n-m}\right)g(x)+u(x).\end{align*}

Así, eligiendo q(x)=t(x)+\frac{a_n}{b_m}x^{n-m} y r(x)=u(x), terminamos la hipótesis inductiva.

\square

Aplicando el algoritmo de la división de forma práctica

Veamos ahora un ejemplo de cómo se puede aplicar este teorema anterior de forma práctica. A grandes rasgos, lo que podemos hacer es «ir acumulando» en q(x) a los términos \frac{a_n}{b_m}x^{n-m} que van apareciendo en la inducción, y cuando h(x) se vuelve de grado menor a q(x), lo usamos como residuo. Hagamos un ejemplo concreto.

Ejemplo. Tomemos f(x)=x^5+x^4+x^3+x^2+2x+3 y g(x)=x^2+x+1. Vamos a aplicar iteradamente las ideas de la demostración del teorema anterior para encontrar los polinomios q(x) y r(x) tales que

    \[f(x)=q(x)g(x)+r(x),\]

con r(x) el polinomio 0 o de grado menor a g(x).

Como el grado de f(x) es 5, el de g(x) es 2 y 5>2, lo primero que hacemos es restar x^{5-2}g(x)=x^3g(x) a f(x) y obtenemos:

    \[h_1(x)=f(x)-x^3g(x)=x^2+2x+3.\]

Hasta ahora, sabemos que q(x)=x^3+\ldots, donde en los puntos suspensivos va el cociente que le toca a h_1(x)=x^2+2x+3. Como el grado de h_1(x) es 2, el de g(x) es 2 y 2\geq 2, restamos x^{2-2}g(x)=1\cdot g(x) a h_1(x) y obtenemos.

    \[h_2(x)=h_1(x)-g(x)=x+2.\]

Hasta ahora, sabemos que q(x)=x^3+1+\ldots, donde en los puntos suspensivos va el cociente que le toca a h_2(x)=x+2. Como el grado de h_2(x) es 1, el de g(x) es 2 y 2>1, entonces el cociente es 0 y el residuo es h_2(x)=x+2.

De esta forma, concluimos que

    \[q(x)=x^3+1\]

y

    \[r(x)=x+2.\]

En conclusión,

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

Esto se puede verificar fácilmente haciendo la operación polinomial.

\square

Hay una forma más visual de hacer divisiones de polinomios «haciendo una casita». Puedes ver cómo se hace esto en el siguiente video en Khan Academy, y los videos que le siguen en la lista.

Divisibilidad en polinomios

Cuando trabajamos en \mathbb{Z}, estudiamos la noción de divisibilidad. Si en el algoritmo de la división obtenemos que r(x) es el polinomio 0, entonces obtenemos una noción similar para \mathbb{R}[x].

Definición. Sean f(x) y g(x) polinomios en \mathbb{R}[x]. Decimos que g(x) divide a f(x) si existe un polinomio q(x) tal que f(x)=q(x)g(x).

Ejemplo. El polinomio x^3-1 divide al polinomio x^4+x^3-x-1, pues

    \[x^4+x^3-x-1 = (x^3-1)(x+1).\]

\square

Ejemplo. Si g(x) es un polinomio no cero y constante, es decir, de la forma g(x)=a para a\neq 0 un real, entonces divide a cualquier otro polinomio en \mathbb{R}[x]. En efecto, si

    \[f(x)=a_0+a_1x+\ldots + a_nx^n\]

es cualquier polinomio y tomamos el polinomio

    \[q(x)=\frac{a_0}{a}+\frac{a_1}{a}x+\ldots + \frac{a_n}{a}x^n,\]

entonces f(x)=g(x)q(x).

\square

El último ejemplo nos dice que los polinomios constantes y no cero se comportan «como el 1 se comporta en los enteros». También nos dice que cualquier polinomio tiene una infinidad de divisores. Eso nos pone en aprietos para definir algo así como los «polinomios primos» en términos del número de divisores. En la siguiente sección hablaremos de cómo hacer esta definición de manera adecuada.

Polinomios irreducibles

Cuando trabajamos con enteros, vimos que es muy útil poder encontrar la factorización en términos de números primos. En polinomios no tenemos «polinomios primos», pero tenemos un concepto parecido.

Definición. Un polinomio p(x) en \mathbb{R}[x] es irreducible en \mathbb{R}[x] si no es un polinomio constante, y no es posible escribirlo como producto de dos polinomios en \mathbb{R}[x] no constantes.

Ejemplo. El polinomio

    \[x^4+x^2+1\]

no es irreducible en \mathbb{R}[x] pues

    \[x^4+x^2+1=(x^2+x+1)(x^2-x+1).\]

Los polinomios x^2+x+1 y x^2-x+1 sí son irreducibles en \mathbb{R}[x]. Más adelante veremos por qué.

\square

La razón por la cual quitamos a los polinomios constantes es parecida a la cual en \mathbb{Z} no consideramos que 1 sea primo: ayuda a enunciar algunos teoremas más cómodamente.

Hay unos polinomios que fácilmente se puede ver que son irreducibles: los de grado 1.

Proposición. Los polinomios de grado 1 en \mathbb{R}[x] son irreducibles.

Demostración. Si f(x) es un polinomio de grado 1, entonces no es constante. Además, no se puede escribir a f(x) como el producto de dos polinomios no constantes pues dicho producto tiene grado al menos 2.

\square

Hay otros polinomios en \mathbb{R}[x] que no son de grado 1 y que son irreducibles. Por ejemplo, con la teoría que tenemos ahora te debe ser fácil mostrar de tarea moral que x^2+1 es irreducible en \mathbb{R}[x].

La razón por la que siempre insistimos en que la irreducibilidad sea en \mathbb{R}[x] es por que a veces un polinomio no se puede factorizar en polinomios con coeficientes reales, pero sí con coeficientes complejos. Aunque x^2+1 sea irreducible en \mathbb{R}[x], si permitimos coeficientes complejos se puede factorizar como

    \[x^2+1=(x+i)(x-i).\]

Más adelante seguiremos hablando de irreducibilidad. Por ahora, nos enfocaremos en los polinomios de grado 1.

Teorema del factor

Una propiedad clave de los polinomios de grado 1 es que es que es lo mismo que x-a divida a un polinomio p(x), a que a sea una raíz de p(x).

Teorema (del factor). Sea a un real y p(x) un polinomio en \mathbb{R}[x]. El polinomio x-a divide a p(x) si y sólo si p(a)=0.

Demostración. De acuerdo al algoritmo de la división, podemos escribir

    \[p(x)=(x-a)q(x)+r(x),\]

en donde r(x) es 0 o un polinomio de grado menor estricto al de x-a. Como el grado de x-a es 1, la única posibilidad es que r(x) sea un polinomio constante r(x)=r. Así, p(x)=(x-a)q(x)+r, con r un real.

Si p(a)=0, tenemos que

    \[0=p(a)=(a-a)q(a)+r=r,\]

de donde r=0 y entonces p(x)=(x-a)q(x), lo que muestra que x-a divide a p(x).

Si x-a divide a p(x), entonces p(x)=(x-a)q(x), de donde p(a)=(a-a)q(a)=0, por lo que a es raíz de p(x).

\square

Ejemplo. Consideremos el polinomio p(x)=x^3-6x^2+11x-6. ¿Podremos encontrar algunos polinomios lineales que lo dividan? A simple vista, notamos que la suma de sus coeficientes es 1-6+11-6=0. Esto nos dice que p(1)=0. Por el teorema del factor, tenemos que x-1 divide a p(x). Tras hacer la división, notamos que

    \[p(x)=(x-1)(x^2-5x+6).\]

Veamos si podemos seguir factorizando polinomios lineales que no sean x-1. Si un polinomio x-a divide a p(x), por el teorema del factor debemos tener

    \[0=p(a)=(a-1)(a^2-5a+6).\]

Como a\neq 1, entonces a-1\neq 0, de modo que tiene que pasar

    \[a^2-5a+6=0,\]

en otras palabras, hay que encontrar las raíces de x^2-5x+6.

Usando la fórmula general cuadrática, tenemos que las raíces de x^2-5x+6 son

    \begin{align*}x_1&=\frac{5+\sqrt{25-24}}{2}=3\\x_2&=\frac{5-\sqrt{25-24}}{2}=2.\end{align*}

Usando el teorema del factor, concluimos que tanto x-2 como x-3 dividen a p(x). Hasta ahora, sabemos entonces que

    \[p(x)=(x-1)(x-2)(x-3)h(x),\]

donde h(x) es otro polinomio. Pero (x-1)(x-2)(x-3) ya es un polinomio de grado 3, como p(x) y su coeficiente de x^3 es 1, como el de p(x). Concluimos que h(x)=1 y entonces

    \[p(x)=(x-1)(x-2)(x-3).\]

\square

Teorema del residuo

En realidad, la técnica que usamos para el teorema del factor nos dice algo un poco más general. Cuando escribimos

    \[p(x)=(x-a)q(x)+r\]

y evaluamos en a, obtenemos que p(a)=r. Reescribimos esta observación como un teorema.

Teorema (del residuo). Sea a un real y p(x) un polinomio en \mathbb{R}[x]. El residuo de dividir p(x) entre x-a es p(a).

Problema. Encuentra el residuo de dividir el polinomio p(x)=x^8-x^5+2x^3+2x entre el polinomio x+1.

Solución. Se podría hacer la división polinomial, pero esto es largo y no nos piden el polinomio cociente, sólo el residuo. Así, podemos resolver este problema más fácilmente usando el teorema del residuo.

Como x+1=x-(-1), el residuo de la división de p(x) entre x+1 es p(-1). Este número es

    \begin{align*}p(-1)&=(-1)^8-(-1)^5+2(-1)^3+2(-1)\\&=1+1-2-2\\&=-2.\end{align*}

\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.

  • Muestra que el polinomio x no tiene inverso multiplicativo.
  • Demuestra la parte de unicidad del algoritmo de la división.
  • Muestra que el polinomio x^2+1 es irreducible en \mathbb{R}[x]. Sugerencia. Procede por contradicción. Una factorización tiene que ser de la forma x^2+1=p(x)q(x) con p y q de grado 1.
  • Factoriza en términos lineales al polinomio p(x)=x^3-12x^2+44x-48. Sugerencia. Intenta enteros pequeños (digamos de -3 a 3) para ver si son raíces. Uno de ellos funciona. Luego, usa el teorema del factor para expresar a p(x) como un polinomio lineal por uno cuadrático. Para encontrar el resto de factores lineales, encuentra las raíces del cuadrático.
  • Encuentra el residuo de dividir el polinomio x^5-x^4+x^3-x^2+x-1 entre el polinomio x-2.

Seminario de Resolución de Problemas: Aritmética de números complejos

Introducción

En entradas anteriores de esta sección hablamos de propiedades aritméticas de números enteros. En esta entrada veremos varias de las propiedades aritméticas de los números complejos y cómo se pueden usar para resolver problemas, incluso aquellos en los que los números complejos no están mencionados de manera explícita en el enunciado.

Distintas formas de los números complejos

La forma más común en la que pensamos en números complejos es en su forma rectangular, en donde un complejo se escribe de la forma z=a+bi, en donde a y b son números reales y pensamos a i como un número tal que i^2=-1. A a le llamamos la parte real y a b la parte imaginaria.

Podemos colocar al complejo z=a+ib en el plano cartesiano, identificándolo con el punto (a,b). De aquí, la forma polar del complejo es z=r(\cos \theta + i \sin \theta), en donde r es la norma |z|:=\sqrt{a^2+b^2} y si z\neq 0, \theta es el argumento, que es el ángulo en el sentido antihorario desde el origen entre el eje horizontal y el punto (a,b). Si z=0+i0=0, no definimos el argumento.

Forma polar y rectangular de un complejo
Forma polar y rectangular de un complejo.

Así como le hacíamos en el caso de trabajar con módulos, a veces conviene pensar que el argumento es el único ángulo en [0,2\pi) que cumple lo anterior. En otras ocasiones, conviene pensar al argumento como a veces que es la clase de todos los ángulos módulo 2\pi.

Cuando tenemos a complejos w=a+ib y z=c+id en forma rectangular, su suma w+z=(a+c) + i(b+d) corresponde geométricamente a encontrar la diagonal del paralelogramo definido por (a,b), (c,d) y el origen, pues corresponde justo al punto (a+c,b+d).

Suma de números complejos
Suma de números complejos.

Su multiplicación wz en forma rectangular es (ac-bd)+(ad+bc)i, que geométricamente no es tan claro que sea.

La forma exponencial z=re^{i\theta} es simplemente una forma de abreviar a la forma polar, pues por definición e^{i\theta}=\cos \theta + i \sin \theta. En forma exponencial, el producto es más sencillo de entender.

Ejercicio. Demuestra lo siguiente:

  • Muestra que la norma es multiplicativa, es decir, que para complejos r y s se tiene que |rs|=|r||s|.
  • Muestra que e^{i\alpha}e^{i\beta}=e^{i(\alpha+\beta)}.

Sugerencia. Para el primer punto, haz las cuentas usando la forma rectangular. Para el segundo punto, escribe las definiciones de todos los términos en forma polar. Haz las multiplicaciones en el lado izquierdo y usa las fórmulas trigonométricas para sumas de ángulos.

Por el ejercicio anterior, si tenemos a los complejos en forma polar w=re^{i\alpha}, z=se^{i\beta}, entonces el producto es wz=rse^{i(\alpha+\beta)}, de modo que el producto corresponde al complejo con el producto de normas y suma de argumentos. En ocasiones esto nos permite plantear algunos problemas geométricos en términos de números complejos.

Producto de números complejos.
Multiplicación de números complejos.


Aplicaciones de aritmética de complejos

Veamos dos aplicaciones de la teoría anterior a problemas que no mencionan en el enunciado a los números complejos.

Problema. Sean a y b enteros. Muestra que el número (a^2+b^2)^n se puede expresar como la suma de los cuadrados de dos números enteros.

Podría ser tentador usar el binomio de Newton para elevar el binomio a la n-ésima potencia. Sugerimos que intentes esto para darte cuenta de las dificultades que presenta.

Sugerencia pre-solución. Escribe a a^2+b^2 como el cuadrado de la norma de un complejo y usa que es multiplicativa.

Solución. El número r=a^2+b^2 es la norma al cuadrado del número complejo z=a+ib. Entonces, el número r^n=(a^2+b^2)^n es la norma al cuadrado del número complejo z^n=(a+ib)^n. Pero al desarrollar (a+ib)^n obtenemos únicamente a i, potencias de a y de b, y coeficientes binomiales. De modo que z^n=(a+ib)^n=c+id con c y d enteros (aquí estamos usando notación adecuada: no es necesario saber quienes son, sólo que son enteros). Así, r^n=c^2+d^2 con c y d enteros.

\square

Veamos ahora un ejemplo de geometría. Este problema es posible resolverlo de muchas formas, pero notemos que los números complejos nos dan una forma de hacerlo de manera algebraica de manera inmediata.

Problema. En la siguiente figura hay tres cuadrados de lado 1 pegados uno tras otro. Determina la suma de los ángulos marcados con \alpha y \beta.

Problema de suma de ángulos
Determinar el valor de la suma \alpha+\beta.

Sugerencia pre-solución. El problema pide determinar una suma de ángulos, así que conviene pensar esta suma de ángulos como el ángulo del producto de dos complejos. Haz tu propia figura, pero ahora sobre el plano complejo.

Solución. El ángulo \alpha es igual al argumento del complejo 2+i y el ángulo \beta es igual al argumento del complejo 3+i. De esta forma, \alpha+\beta es igual al argumento del complejo (2+i)(3+i)=(6-1)+(2+3)i=5+5i. Este complejo cae sobre la recta \text{Re}(z)=\text{Im}(z), de modo que su argumento es \pi / 4.

\square

Este problema también se puede resolver de (numerosas) maneras geométricas, que puedes consultar en este video.

Fórmula de De Moivre

El siguiente teorema se puede demostrar por inducción sobre n.

Teorema (fórmula de De Moivre). Para cualquier entero n y ángulo \theta se tiene que

    \[(\cos \theta + i \sin \theta)^n=\cos (n\theta) + i \sin (n\theta).\]

Dicho de otra forma, en términos de la forma exponencial, se vale usar la siguiente ley de los exponentes

    \[(e^{\theta i})^n=e^{(n\theta) i}.\]

La fórmula de De Moivre es otra herramienta que ayuda a resolver problemas de números reales enunciándolos en términos trigonométricos. El truco consiste en:

  1. Tomar una expresión real que queramos entender.
  2. Identificarla como la parte real o imaginaria de una expresión compleja.
  3. Usar la aritmética de números complejos para entender la expresión compleja.
  4. Regresar lo que entendamos a los reales.

Veamos un par de ejemplos, relacionados con funciones trigonométricas. Comenzamos con una fórma de encontrar la fórmula para el coseno de cinco veces un ángulo.

Problema. Sea \theta\in [0,2\pi). Expresa a \cos 5\theta en términos de \cos \theta.

Sugerencia pre-solución. Identifica a \cos 5\theta como la parte real de un número complejo. Inspírate en la fórmula de De Moivre. Usa binomio de Newton.

Solución. Por la fórmula de De Moivre, \cos 5\theta es la parte real del complejo (\cos \theta + i \sin \theta)^5, así que calculemos quién es exactamente este número usando binomio de Newton. Para simplificar la notación, definimos a=\cos \theta y b=\sin \theta. Tenemos que

    \begin{align*} (a+ib)^5&=a^5+5a^4(bi)+10a^3(ib)^2+10a^2(ib)^3+5a(ib)^4+(ib)^5\\&=(a^5-10a^3b^2+5ab^4) + (5a^4b-10a^2b^3+b^5) i.\end{align*}

Además, por la identidad pitagórica recordemos que a^2+b^2=1, de donde b^2=1-a^2, de modo que la parte real de la expresión anterior es

    \[a^5-10a^3(1-a^2)+5a(1-2a^2+a^4),\]

que agrupando es

    \[16a^5-20a^3+5a.\]

Recordando que a es \cos \theta, obtenemos la fórmula final

    \[\cos 5\theta = 16\cos^5 \theta - 20 \cos^3 \theta + 5\cos \theta.\]

\square

Raíces de la unidad

En muchos problemas se utilizan las raíces de la ecuación x^n=1.

Teorema. Sea n\geq 1 un entero. Las ecuación x^n=1 tiene n soluciones complejas, que en el plano complejo forman los vértices del n-ágono regular con centro en 0 y tal que uno de sus vértices es 1. Si \omega es la raíz de menor argumento positivo, entonces estas soluciones son 1,\omega, \omega^2,\ldots,\omega^{n-1}.

Raíces de la unidad en los números complejos
Raíces n-ésimas de la unidad para n=5.

A estas soluciones les llamamos las raíces n-ésimas de la unidad. Notemos que \omega^{n}=1, y que en general si escribimos a un entero m usando el algoritmo de la división como m=qn+r, entonces \omega^m=\omega^r. ¡Los productos de raíces de la unidad se comportan como los elementos de \mathbb{Z}_n bajo suma módulo n!

Proposición. Sea n\geq 2 un entero. La suma de las n raíces n-ésimas de la unidad es 0 y su producto es 1.

La proposición anterior nos permite, en ocasiones, «filtrar» ciertas expresiones algebraicas. A continuación presentamos un ejemplo, que retomamos de los primeros ejemplos que vimos, cuando estábamos aprendiendo la heurística de encontrar un patrón.

Problema. Determina el valor de la suma

    \[\binom{100}{0}+\binom{100}{3}+\binom{100}{6}+\ldots+\binom{100}{99}.\]

Sugerencia pre-solución. Si no recuerdas lo que debería salir, vuelve a experimentar con los primeros valores, para cuando en vez de usar 100 se usan números más chiquitos. Para entender mejor el patron, generaliza el problema, y en vez de sólo tener múltiplos de 3 abajo, explora también qué sucede cuando tienes los números que dejan residuo 0, 1 o 2 módulo 3.

Ya que recuerdes la fórmula que queremos, considera una raíz cúbica \omega de la unidad distinta de 1. Calcula (1+1)^{100}, (1+\omega)^{100} y (1+\omega^2)^{100} usando el binomio de Newton y aprovechando que toda potencia de \omega es 1, \omega u \omega^2 para simplificar la notación.

Solución. Sea \omega una raíz cúbica de la unidad distinta de 1. Tenemos que \omega^3=1 y que 1+\omega+\omega^2=0. De este modo, podemos usar \omega y el binomio de Newton para calcular las siguientes expresiones

    \begin{align*}(1+1)^{100}&=\binom{100}{0}+\binom{100}{1}+\binom{100}{2}+ \binom{100}{3}+ \ldots\\(1+\omega)^{100}&= \binom{100}{0}+\binom{100}{1}\omega+\binom{100}{2}\omega^2+\binom{100}{3}+\ldots\\(1+\omega^2)^{100}&= \binom{100}{0}+\binom{100}{1}\omega^2+\binom{100}{2}\omega+ \binom{100}{3}+\ldots \end{align*}

¿Qué sucede al sumar las tres expresiones? En el lado derecho, cada vez que m es un múltiplo de 3, tenemos 3\binom{100}{m}, y cada vez que m no es un múltiplo de 3, tenemos

    \[(1+\omega+\omega^2)\binom{100}{m}=0.\]

¡Se filtran exactamente los coeficientes binomiales con parte inferior múltiplo de 3! Así, tres veces la suma que buscamos es igual a

    \[2^{100}+(1+\omega)^{100}+(1+\omega^2)^{100}.\]

Esta ya es una expresión suficientemente cerrada, pero podemos simplificar todavía más:

    \begin{align*}(1+\omega)^{100}&=(-\omega^2)^{100}=\omega^{200}=\omega^2\\(1+\omega^2)^{100}&=(-\omega)^{100}=\omega\\(1+\omega)^{100}+(1+\omega^2)^{100}&=\omega^2+\omega=-1.\end{align*}

Así, la expresión que queremos es \frac{2^{100}-1}{3}.

\square

Más ejemplos

Puedes ver más ejemplos del uso de esta teoría en la Sección 3.5 del libro Problem Solving through Problems de Loren Larson.

Álgebra Superior II: Ecuaciones diofantinas

Introducción

En entradas anteriores platicamos de congruencias y teoremas que nos sirven para trabajar con aritmética modular. Así mismo, aprendimos a resolver ecuaciones lineales y sistemas de ecuaciones lineales en congruencias en una variable.

Regresemos a \mathbb{Z}. Se usa el término ecuación diofantina para referirse a una ecuación en la cual las variables deben tomar soluciones enteras. Existe una gran variedad de formas que puede tomar una ecuación diofantina. «Resolver una ecuación diofantina» se refiere a encontrar, con demostración, una descripción del conjunto de todas sus soluciones en «términos sencillos».

Ejemplo 1. Encuentra todas las soluciones enteras x a la ecuación 13x=91.

Ejemplo 2. Encuentra todas las soluciones enteras x,y a la ecuación 7x+5y=3.

Los ejemplos 1 y 2 son ecuaciones diofantinas lineales en una y dos variables respectivamente. El objetivo de esta entrada es explicar cómo resolver estas ecuaciones. Continuamos la discusión de más ejemplos para abrir el panorama del tipo de problemas que aparecen en el área, y de las técnicas que se pueden usar.

Ejemplo 3. Encuentra todas las soluciones con enteros x,y,z a la ecuación x^2+y^2=z^2.

Al Ejemplo 3 se le conoce como la ecuación pitagórica. Esa es posible resolverla con todo lo que hemos visto hasta ahora, pero no es tan sencillo. Requiere de un análisis cuidadoso de casos.

Ejemplo 4. Encuentra todas las soluciones enteras positivas x,y a la igualdad x^y=y^x.

El Ejemplo 4 es curioso. Si consideramos a la función real f(x)=x^{\frac{1}{x}}, el problema pide encontrar a aquellas parejas de enteros x y y tales que f(x)=f(y). Una forma de resolver la ecuación es utilizando herramientas de cálculo diferencial en f(x) para mostrar que para x>5 la función ya es estrictamente creciente. Esto reduce el análisis de casos de enteros que tenemos que intentar, y muestra que (2,4), (4,2) y (n,n) son las únicas parejas de enteros válidas. La moraleja de este ejemplo es que a veces se tienen que usar herramientas de otras áreas de las matemáticas para resolver una ecuación, aunque esta sólo requiera de soluciones enteras.

Ejemplo 5. Encuentra todas las soluciones con enteros x,y,z a la ecuación x^3+y^3=z^3.

El Ejemplo 5, o bien cualquier ecuación del estilo x^n+y^n=z^n se le llama una ecuación de tipo Fermat, pues Pierre Fermat conjeturó que no existen soluciones para cuando n\geq 3 y x,y,z son todos distintos de cero. Esta conjetura fue demostrada en 1995 por Andrew Wiles. Una demostración de esta conjetura queda muy lejos de la teoría que hemos desarrollado hasta ahora, pero vale la pena decir que esta ecuación motivó fuertemente el desarrollo de varias herramientas de teoría de números, sobre unas llamadas curvas elípticas.

Ejemplo 6. Encuentra todas las soluciones enteras positivas x,y a la igualdad |2^x-3^y|=1.

El Ejemplo 6 se puede resolver también con herramientas que ya hemos visto en el curso, pero requiere de un análisis detallado. Este problema pide, en otras palabras, determinar cuándo «una potencia de 3 está junto a una potencia de 2«. Un ejemplo de esto son 2^3=8 y 3^2=9. Otra pregunta clásica del área es la conjetura de Catalán, la cual afirma que estas son las únicas dos potencias no triviales que son consecutivas. Fue demostrada en 2002 por Mihăilescu. Las técnicas también están muy lejos del alcance de este curso. Se usan técnicas en campos ciclotómicos y módulos de Galois.

En realidad, uno podría tomar cualquier ecuación en reales y hacerse la pregunta de si existirán soluciones en enteros y, de ser así, determinar cuántas o cuáles son. Ha existido (y existe) mucha investigación en el área. El interés de una ecuación diofantina en particular está relacionado con su aplicación a otros problemas y con la teoría que ayuda a desarrollar.

Ecuaciones diofantinas lineales

La ecuación diofantina del Ejemplo 1 se puede preguntar en general. Dados enteros a y b, ¿cuáles son las soluciones enteras x a la ecuación ax=b?

  • Si a=0, la ecuación tiene solución si y sólo si b=0, y en este caso, cualquier valor entero de x es solución.
  • Si a\neq 0, esta ecuación tiene solución en enteros si y sólo si a divide a b, y en este caso x=b/a es la única solución entera.

Estudiemos ahora la generalización del Ejemplo 2.

Problema. Sean a y b enteros distintos de 0 y c un entero. Determina todas las soluciones enteras a la ecuación

    \[ax+by=c.\]

Primero, determinemos condiciones necesarias y suficientes en a, b y c para que la ecuación tenga soluciones enteras x y y. Lo que nos está pidiendo la ecuación es que escribamos a c como combinación lineal entera de a y b. Recordemos que

    \[a\mathbb{Z}+b\mathbb{Z} = \text{MCD}(a,b) \mathbb{Z},\]

de modo que la ecuación tiene solución si y sólo si \text{MCD}(a,b) divide a c. ¿Cuáles son todas las soluciones? Esto lo determinaremos mediante las siguientes proposiciones.

Proposición. Sean a y b enteros distintos de 0 y c un entero divisible entre M:=\text{MCD}(a,b). Sean a'=a/M, b'=b/M, c'=c/M. Las soluciones enteras a la ecuación ax+by=c son las mismas que para la ecuación a'x+b'y=c'

Demostración. Se sigue de manera directa usando que M\neq 0, ya que de la original podemos pasar a la nueva dividiendo entre M, y de la nueva a la anterior multiplicando por M.

\square

Ejemplo. x=2 y y=7 son soluciones a la ecuación 6x-4y=-16, y también son soluciones a la ecuación 3x-2y=-8.

\square

Al dividir ambos lados de la ecuación entre el máximo común divisor de a y b obtenemos una ecuación en la que los coeficientes de las variables ahora son primos relativos. Este fenómeno ya lo habíamos visto cuando hablamos de ecuaciones en congruencias. Estudiemos este tipo de ecuaciones en enteros. Comenzaremos con unas un poco más sencillas: aquellas en las que c=0. A estas les llamamos ecuaciones homogéneas.

Proposición. Sean a y b enteros distintos de 0 y primos relativos. Las soluciones de la ecuación diofantina ax+by=0 son exactamente de la forma x=-kb, y=ka para k en los enteros.

Demostración. De la ecuación obtenemos -ax=by, por lo que a divide a by. Como a y b son primos relativos, tenemos que a divide a y. Así, existe un k entero tal que y=ka. Entonces, -ax=bka. Como a\neq 0, podemos cancelar y despejar x=-kb.

En efecto, todas estas parejas son soluciones pues a(-kb)+b(ka)=0.

\square

Ejemplo. Determina todas las soluciones a la ecuación diofantina 9x+5y=0.

Solución. Tenemos que 9 y 5 son primos relativos y que la ecuación es homogénea. Por el resultado anterior, las soluciones son de la forma x=-5k y y=9k.

\square

Ejemplo. Determina todas las soluciones a la ecuación diofrantina 9x-6y=0.

Solución. Aquí hay que tener cuidado. Si bien la ecuación es homogénea, los coeficientes de las variables no son primos relativos. Si sólo consideramos las soluciones de la forma x=6k y y=9k, en efecto todas estas son soluciones, pero nos faltará la solución x=2, y=3 que no es de esta forma.

Antes de poder usar la proposición, necesitamos dividir entre el máximo común divisor de 9 y 6, que es 3, para obtener primero la ecuación diofantina equivalente 3x-2y=0. Ahora sí, todas las soluciones enteras de esta ecuación (y por lo tanto de la original) son de la forma x=2k y y=3k.

\square

Pasemos ahora al caso en el que los coeficientes de las variables son primos relativos, pero la ecuación ya no es homogénea.

Proposición. Sean a y b enteros distintos de 0 y primos relativos. Sea c un entero divisible entre \text{MCD}(a,b). Se puede obtener una solución x_0, y_0 a la ecuación diofantina ax+by=c usando el algoritmo de Euclides. El resto de las soluciones son exactamente de la forma x=x_0-kb, y=y_0+ka en donde k es cualquier entero positivo.

Demostración. Notemos que en efecto las soluciones propuestas satisfacen la ecuación diofantina pues

    \begin{align*}ax+by&=a(x_0-kb)+b(y_0+ka)\\&=ax_0+by_0 + (-kab+kab)\\&=ax_0+by_0\\&=c.\end{align*}

Aquí usamos que x_0,y_0 es una solución de ax+by=c. Veamos que estas soluciones son las únicas.

Si x_1,y_1 es una solución, entonces tenemos

    \[ax_1+by_1=c=ax_0+by_0,\]

y entonces

    \[a(x_1-x_0)+b(y_1-y_0)=c-c=0,\]

de modo que (x_1-x_0), (y_1-y_0) es una solución de la ecuación homogénea ax+by=0, y por la proposición anterior, debe suceder que x_1-x_0=-ka y y_1-y_0=kb con k un entero. Así, x_1=x_0-ka y y_1=y_0+kb, como queríamos.

\square

Ejemplo. Determina todas las soluciones a la ecuación diofantina 12x+13y=1.

Solución. Por inspección, una solución es x=-1, y=1. Los coeficientes de las variables son primos relativos. Por la proposición anterior, todas las soluciones son de la forma -13k-1, 12k+1 donde k es un entero arbitrario.

\square

Resumimos todo lo obtenido en el siguiente resultado.

Teorema. Sean a y b enteros distintos de 0 y c un entero. Consideremos la ecuación diofantina ax+by=c. Si M:=\text{MCD}(a,b) no divide a c, entonces la ecuación no tiene solución. Si sí, podemos usar el algoritmo de Euclides para encontrar una solución x_0,y_0. El resto de las soluciones son de la forma x_0-ka', y_0+kb', en donde a'=a/M, b'=b/M y k es cualquier entero.

Veamos un ejemplo en el que juntamos todo lo que ya sabemos.

Ejemplo. Determina todas las soluciones a la ecuación diofantina 21x-35y=14.

Solución. Los coeficientes de las variables no son primos relativos, pues su máximo común divisor es 7. Tenemos que 7 divide a 14, así que la ecuación sí tiene soluciones y son las mismas que las de la ecuación 3x-5y=2. Por inspección, una solución es x=-1, y=-1. Así, todas las soluciones a esta ecuación (y por lo tanto a la original), son de la forma x=5k-1, y=3k-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.

  • Resuelve el Ejemplo 2
  • En todos los ejemplos, verifica que las soluciones obtenidas en efecto son soluciones del sistema original.
  • ¿Para cuántos enteros c entre 1 y 100 se tiene que la ecuación lineal 21x+18y=c tiene solución x,y en enteros?
  • Sólo hemos visto ecuaciones diofantinas lineales en dos variables. Sin embargo, con lo visto hasta ahora puedes argumentar por qué la ecuación diofantina 91x+14y-70z=100 no tiene soluciones en enteros. ¿Por qué?
  • Investiga acerca de la ecuación pitagórica x^2+y^2=z^2.

Seminario de Resolución de Problemas: Primos y factorización única

Introducción

En entradas anteriores hablamos de divisibilidad y de aritmética modular. Ahora platicaremos de las bloques que nos ayudan a construir a todos los enteros de manera multiplicativa: los números primos. Lo que dice el teorema fundamental de la aritmética es que todo número es producto de primos «de manera única». Tanto la teoría de números primos, como este teorema, son de gran ayuda en la resolución de problemas

Como en entradas anteriores, el enfoque no es demostrar los resultados principales de la teoría. Esto se hace en un curso de Álgebra Superior II o en uno de Teoría de Números. La idea de la entrada es ver aplicaciones de estos resultados en situaciones concretas.

Números primos

Un entero es primo si tiene exactamente dos divisores positivos. El 1 no es primo pues su único divisor es él mismo. Pero 2, 17 y 31 sí son primos. De aquí y el algoritmo de la división, si p es primo y a es un entero, entonces p\mid a o \MCD{p,a}=1.

Proposición 1. Si p es un número primo que divide al producto de enteros ab, entonces p\mid a ó p\mid b.

Demostración. Si p no divide a a, entonces \MDC(p,a)=1, así que existe una combinación lineal entera pn+am=1. Multiplicando esta combinación por b, tenemos que pbn+abm=b. Como p divide a pbn y a ab, entonces divide a b.

\square

Problema. Muestra que si p es un primo que divide a 123456^{654321}, entonces p divide a 123456.

Sugerencia pre-solución. Aquí 123456 y 654321 no tienen nada de especial. Generaliza el problema y procede por inducción en el exponente.

Solución. Sea a un entero, n un entero positivo y p un primo. Vamos a mostrar por inducción en n que si p\mid a^n, entonces p\mid a. Para n=1 la conclusión es inmediata. Supongamos el resultado cierto para n. Si p\mid a^{n+1}, por la Proposición 1 tenemos que p\mid a (en cuyo caso terminamos), o que p\mid a^n (en cuyo caso terminamos por hipótesis inductiva). El problema se resuelve tomando a=123456 y n=6543321.

\square

Extendiendo la idea del problema anterior, se puede demostrar la siguiente proposición.

Proposición 2. Si p es primo, a un entero y n un entero positivo tales que p\mid a^n, entonces p^n\mid a^n.

Teorema fundamental de la aritmética

Todo número es producto de primos de manera única. Más específicamente

Teorema (teorema fundamental de la aritmética). Sean a un entero positivo. Entonces existe un único n, únicos primos p_1<\ldots<p_n y exponentes \alpha_1,\ldots,\alpha_n tales que

    \[a=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n}.\]

La idea de la demostración es factorizar y factorizar. Si n está expresado como producto de primos, ya está. Si no, hay uno de sus factores que no es primo y entonces se puede factorizar en dos números menores. Para probar la unicidad se usa la Proposición 1.

Veamos algunas aplicaciones del teorema fundamental de la aritmética.

Problema. Muestra que \sqrt[3]{7} es un número irracional.

Sugerencia pre-solución. Procede por contradicción suponiendo que es racional para igualarlo a una fracción y eleva al cubo.

Solución. Si no fuera irracional, lo podríamos expresar como una fracción, digamos \sqrt[3]{7}=\frac{a}{b} con a y b enteros. De aquí, 7b^3=a^3. En la factorización en primos de a^3 y b^3 tenemos una cantidad múltiplo de 3 de factores 7. Así, en el lado derecho tenemos una cantidad mútiplo de 3 de factores 7 (por la Proposición 2), pero en el lado izquierdo no. Esto es una contradicción a la unicidad de la factorización en primos.

\square

Es posible que en un problema tengamos que usar el teorema fundamental de la aritmética repetidas veces.

Problema. Determina todos los enteros positivos n para los cuales 2^8+2^{11}+2^n es un número entero al cuadrado.

Sugerencia pre-solución. Trabaja hacia atrás y usa notación adecuada. Intenta encontrar una diferencia de cuadrados.

Solución. Vamos a comenzar suponiendo m^2=2^8+2^{11}+2^n. De aquí,

    \begin{align*}2^n&=m^2-2^8(1+2^3)\\&=m^2-(3\cdot 2^4)^2\\& =(m+48)(m-48).\end{align*}

Por la unicidad del teorema fundamental de la aritmética, cada uno de los números m+48 y m-48 tienen que ser potencias de 2, digamos m+48=2^a y m-48=2^b con a>b y a+b=n. Además tenemos que

    \[2^b(2^{a-b}-1)=96=2^5\cdot 3.\]

Como 2^{a-b}-1 es impar, de nuevo por la unicidad de la factorización en primos debemos tener que 2^{a-b}-1=3, y por lo tanto que 2^b=2^5. De aquí, b=5 y a-b=2, y así a=7. Por lo tanto, el único candidato es n=5+7=12.

Ya que trabajamos hacia atrás, hay que argumentar o bien que los pasos que hicimos son reversibles, o bien que n en efecto es solución. Hacemos esto último notando que 2^8+2^{11}+2^{12}=2^8(1+2^3+2^4)=2^8\cdot 5^2 que en efecto es un número cuadrado.

\square

Fórmulas que usan el teorema fundamental de la aritmética

Sean a y b números enteros positivos y P={p_1,\ldots,p_n} el conjunto de números primos que dividen a alguno de a o b. Por el teorema fundamental de la aritmética, existen exponentes \alpha_1,\ldots,\alpha_n y \beta_1,\ldots,\beta_n, tal vez algunos de ellos cero, tales que

    \begin{align*}a&=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\ldots\cdot p_n^{\alpha_n}\\ b&=p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot\ldots\cdot p_n^{\beta_n}. \end{align*}

Por ejemplo, si a=21, b=28, entonces P={2,3,7}, a=2^0 3^1 7^1 y b=2^2 3^0 7^1.

Proposición 3. Se tiene que a divide a b si y sólo si para todo primo p_i se tiene que \alpha_i\leq \beta_i.

Problema. ¿Cuántos múltiplos de 108 hay que sean divisores de 648?

Sugerencia pre-solución. Factoriza en primos a 108 y a 648 y usa la Proposición 3.

Solución. Tenemos que 108=2^23^3 y que 648=2^3\cdot 3^4. Por la Proposición 3, un número que funcione debe ser de la forma 2^a3^b con 2\leq a \leq 3 y con 3\leq b \leq 4. Así, a tiene 2 posibilidades y b también, de modo que hay 2\cdot 2=4 números que cumplen.

\square

Una consecuencia inmediata de la Proposición 3 anterior es la fórmula para el número de divisores de un entero en términos de los exponentes de su factorización en primos.

Proposición 4. El entero a tiene (\alpha_1+1)(\alpha_2+1)\cdots(\alpha_n+1) divisores positivos.

Problema. Determina cuántos enteros hay entre 1 y 10000 que tienen 49 divisores positivos.

Sugerencia pre-solución. Usa la fórmula de la Proposición 4 para trabajar hacia atrás y ver qué forma debe tener un entero que cumple lo que se quiere. Divide en casos para que el producto se 49.

Solución. Tomemos a un entero y p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n} su factorización en primos. Por la Proposición 4, necesitamos que (\alpha_1+1)(\alpha_2+1)\cdots(\alpha_n+1)=49.

A la izquierda tenemos puros números mayores o iguales que 2. El número 49 tiene como únicos divisores a 1, 7 y 49. De esta forma, sólo hay dos casos posibles:

  • El número a tiene sólo un divisor primo y a=p_1^{48}
  • El número a tiene dos divisores primos y a=p_1^6p_2^6

El primer caso es imposible, pues p_1 sería por lo menos 2 y 2^{48}>2^{20}=(1024)^2>(1000)^2>10000. Para el segundo caso, recordemos que p_2>p_1 en la factorización en primos. Si p_2\geq 5, entonces como p_1\geq 2, tendríamos a\geq (2\cdot 5)^6 = 1000000>10000, así que esto no es posible.

La única otra posibilidad es p_2=3 y por lo tanto p_1=2. En este caso obtenemos al número a=(2\cdot 3)^6=6^6=46656, que sí cae en el intervalo deseado. Así, sólo hay un número como el que se pide.

\square

La factorización en primos también sirve para encontrar máximos comunes divisores y mínimos comunes múltiplos.

Proposición 4.  Se pueden calcular \MCD{a,b} y \mcm{a,b} como sigue:

    \begin{align*}\text{MCD}(a,b)&=p_1^{\min(\alpha_1,\beta_1)}\cdot p_2^{\min(\alpha_2,\beta_2)}\cdot\ldots\cdot p_n^{\min(\alpha_n,\beta_n)}\\\text{mcm}(a,b)&=p_1^{\max(\alpha_1,\beta_1)}\cdot p_2^{\max(\alpha_2,\beta_2)}\cdot\ldots\cdot p_n^{\max(\alpha_n,\beta_n)}.\end{align*}

Volvamos a ver un problema que ya habíamos resuelto con anterioridad.

Problema. Demuestra que \MCD{a,b}\mcm{a,b}=ab.

Sugerencia pre-solución. Usa la Proposición 4. Puedes argumentar algunos pasos por simetría.

Solución. Expresemos a a y b en su factorización en primos como lo discutimos arriba. Al multiplicar \MCD{a,b} y \mcm{a,b}, el exponente de p_i es \min(\alpha_i,\beta_i)+\max(\alpha_i,\beta_i)=\alpha_i\beta_i. Este es el mismo exponente de p_i en ab. Así, ambos números tienen la misma factorización en primos y por lo tanto son iguales.

\square

Más ejemplos

Puedes ver más ejemplos del uso de esta teoría en la Sección 3.3 del libro Problem Solving through Problems de Loren Larson.

Si p es primo, entonces todo entero n que no sea múltiplo de p tiene inverso módulo n. Esto se usa en los teoremas de Fermat y Wilson. También hay una entrada con ejercicios de estos teoremas resueltos en video.