Archivo de la etiqueta: enteros

Álgebra Superior II: El criterio de la raíz racional para polinomios de coeficientes enteros

Introducción

En esta entrada veremos el criterio de la raíz racional. Este es un método que nos permite determinar las únicas raíces racionales que puede tener un polinomio con coeficientes enteros. Es una más de las herramientas que podemos usar cuando estamos estudiando polinomios en \mathbb{R}[x].

Si encontramos una raíz con este método, luego podemos encontrar su multiplicidad mediante el teorema de derivadas y multiplicidad. Esto puede ayudarnos a factorizar el polinomio. Otras herramientas que hemos visto que nos pueden ayudar son el algoritmo de Euclides, la fórmula cuadrática, el teorema del factor y propiedades de continuidad y diferenciabilidad de polinomios.

El criterio de la raíz racional

Si un polinomio p(x) en \mathbb{R}[x] cumple que todos sus coeficientes son números enteros, entonces decimos que es un polinomio sobre los enteros. Al conjunto de polinomios sobre los enteros se le denota \mathbb{Z}[x].

Teorema (criterio de la raíz racional). Tomemos un polinomio p(x) en \mathbb{Z}[x] de la forma

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

Supongamos que el número \frac{p}{q} es número racional simplificado, es decir con p y q\neq 0 enteros primos relativos. Si \frac{p}{q} es raíz de p(x), entonces p divide a a_0, y q divide a a_n.

Demostración. Por definición, si \frac{p}{q} es una raíz, tenemos que

    \[0=a_0+a_1\cdot \frac{p}{q} + \ldots + a_n \cdot \frac{p^n}{q^n}.\]

Multiplicando ambos lados de esta igualdad por q^n, tenemos que

    \[0=a_0q^n+a_1pq^{n-1}+\ldots+a_{n-1}p^{n-1}q+a_np^n.\]

Despejando a_0q^n, tenemos que

    \begin{align*}a_0q^n&=-(a_1pq^{n-1}+\ldots+a_{n-1}p^{n-1}q+a_np^n)\\&=-p(a_1q^{n-1}+\ldots+a_{n-1}p^{n-2}q+a_np^{n-1})\end{align*}

Esto muestra que a_0q^n es múltiplo de p. Pero como \MCD{p,q}=1, tenemos que p debe dividir a a_0.

De manera similar, tenemos que

    \begin{align*}a_np^n&=-(a_0q^n+a_1pq^{n-1}+\ldots+a_{n-1}p^{n-1}q)\\&=-q(a_0q^{n-1}+a_1pq^{n-2}+\ldots+a_{n-1}p^{n-1}).\end{align*}

De aquí, q divide a a_np^n, y como \MCD{p,q}=1, entonces q divide a a_n.

\square

Como cualquier natural tiene una cantidad finita de divisores, el criterio de la raíz racional nos permite restringir la cantidad posible de raíces de un polinomio con coeficientes enteros a una cantidad finita de candidatos. Veamos un par de ejemplos.

Aplicación directa del criterio de la raíz racional

Ejercicio. Usa el criterio de la raíz racional para enlistar a todos los posibles números racionales que son candidatos a ser raíces del polinomio

    \[h(x)=2x^3-x^2+12x-6.\]

Después, encuentra las raíces racionales de p(x).

Solución. El polinomio h(x) tiene coeficientes enteros, así que podemos usar el criterio de la raíz racional. Las raíces racionales son de la forma \frac{p}{q} con p divisor de -6, con q divisor de 2 y además \MCD{p,q}=1. Los divisores enteros de -6 son

    \[-6,-3,-2,-1,1,2,3,6.\]

Los divisores enteros de 2 son

    \[-2,-1,1,2.\]

Pareciera que hay muchas posibilidades por considerar. Sin embargo, nota que basta ponerle el signo menos a uno de p o q para considerar todos los casos. Así, sin pérdida de generalidad, q>0. Si q=1, obtenemos a los candidatos

    \[-6,-3,-2,-1,1,2,3,6.\]

Si q=2, por la condición de primos relativos basta usar los valores -3,-1,1,3 para p. De aquí, obtenemos al resto de los candidatos

    \[-\frac{3}{2},-\frac{1}{2},\frac{1}{2},\frac{3}{2}.\]

En el peor de los casos, ya solo bastaría evaluar el polinomio en estos 12 candidatos para determinar si son o no son raíz. Sin embargo, a veces podemos hacer algunos trucos para disminuir todavía más la lista.

Observa que si evaluamos

    \[h(x)=2x^3-x^2+12x-6\]

en un número negativo, entonces la expresión quedará estrictamente negativa, así que ninguno de los candidatos negativos puede ser raíz. De este modo, sólo nos quedan los candidatos

    \[1,2,3,6,\frac{1}{2},\frac{3}{2}.\]

Si evaluamos en x=2 o x=6, entonces la parte de la expresión 2x^3-x^2+12x es múltiplo de 4, pero -6 no. De esta forma, h(x) no sería un múltiplo de 4, y por lo tanto no puede ser 0. Si evaluamos en x=1 o x=3, tendríamos que la parte de la expresión 2x^3+12x-6 sería par, pero -x^2 sería impar, de modo que h(x) sería impar, y no podría ser cero. Así, ya sólo nos quedan los candidatos

    \[\frac{1}{2},\frac{3}{2}.\]

Para ellos ya no hagamos trucos, y evaluemos directamente. Tenemos que

    \begin{align*}h\left(\frac{1}{2}\right) &= 2\cdot \frac{1}{8} - \frac{1}{4} + 12 \cdot \frac{1}{2}-6\\&=\frac{1}{4}-\frac{1}{4}+6-6\\&=0.\end{align*}

y que

    \begin{align*}h\left(\frac{3}{2}\right) &= 2\cdot \frac{27}{8} - \frac{9}{4} + 12 \cdot \frac{3}{2}-6\\&=\frac{27}{4}-\frac{9}{4}+18-6\\&=\frac{9}{2}+12\\&=\frac{33}{2}.\end{align*}

Habiendo considerado todos los casos, llegamos a que la única raíz racional de h(x) es \frac{1}{2}.

\square

Aplicación indirecta del criterio de la raíz racional

El criterio de la raíz racional lo podemos usar en algunos problemas, aunque en ellos no esté escrito un polinomio de manera explícita.

Problema. Muestra que \sqrt[7]{13} no es un número racional.

Solución. Por definición, el número \sqrt[7]{13} es el único real positivo r que cumple que r^7=13. Se puede mostrar su existencia usando que la función f:\mathbb{R}\to\mathbb{R} dada por f(x)=x^7 es continua, que f(0)=0, que f(2)=128, y aplicando el teorema del valor intermedio. Se puede mostrar su unicidad mostrando que la función f es estrictamente creciente en los reales positivos. Lo que tenemos que mostrar es que este número real no es racional.

Si consideramos el polinomio p(x)=x^7-13, tenemos que p(r)=r^7-13=0, de modo que r es raíz de p(x). Así, para terminar el problema, basta mostrar que p(x) no tiene raíces racionales.

El polinomio p(x) tiene coeficientes enteros, así que podemos aplicarle el criterio de la raíz racional. Una raíz racional tiene que ser de la forma \frac{p}{q} con p divisor de -13 y q divisor de 1.

Sin perder generalidad, q>0, así que q=1. De esta forma, los únicos candidatos a ser raíces racionales de p(x) son -13,-1,1,13. Sin embargo, una verificación de cada una de estas posibilidades muestra que ninguna de ellas es raíz de p(x). Por lo tanto, p(x) no tiene raíces racionales, lo cual termina la solución del problema.

\square

Aplicación en polinomio con coeficientes racionales

A veces un polinomio tiene coeficientes racionales, por ejemplo,

    \[r(x)=\frac{x^3}{2}+\frac{x^2}{3}-4x-1.\]

A un polinomio con todos sus coeficientes en \mathbb{Q} se les conoce como polinomio sobre los racionales y al conjunto de todos ellos se le denota \mathbb{Q}[x]. Para fines de encontrar raíces racionales, los polinomios en \mathbb{Q}[x] y los polinomios en \mathbb{Z}[x] son muy parecidos.

Si tenemos un polinomio q(x) en \mathbb{Q}[x], basta con multiplicar por el mínimo común múltiplo de los denominadores de los coeficientes para obtener un polinomio p(x) con coeficientes enteros. Como q(x) y p(x) varían sólo por un factor no cero, entonces tienen las mismas raíces. Por ejemplo, el polinomio r(x) de arriba tiene las mismas raíces que el polinomio

    \[s(x)=6r(x)=3x^3+2x^2-24x-6.\]

A este nuevo polinomio se le puede aplicar el criterio de la raíz racional para encontrar todas sus raíces racionales.

Ejemplo. Consideremos el polinomio

    \[q(x)=x^3+\frac{x^2}{3}+5x+\frac{5}{3}.\]

Vamos a encontrar todos los candidatos a raíces racionales. Para ello, notamos que q(x) y p(x):=3q(x) varían sólo por un factor multiplicativo no nulo y por lo tanto tienen las mismas raíces. El polinomio

    \[p(x)=3x^3+x^2+15x+5\]

tiene coeficientes enteros, así que los candidatos a raíces racionales son de la forma \frac{a}{b} con a y b primos relativos, a\mid 5 y b\mid 3. Sin pérdida de generalidad b>0.

Los divisores de 5 son -5,-1,1,5. Los divisores positivos de 3 son 1 y 3. De esta forma, los candidatos a raíces racionales son

    \[-5,-1,1,5,-\frac{5}{3},-\frac{1}{3},\frac{1}{3},\frac{5}{3}.\]

Si ponemos un número positivo en p(x), como sus coeficientes son todos positivos, tenemos que la evaluación sería positiva, así que podemos descartar estos casos. Sólo nos quedan los candidatos

    \[-5,-1,-\frac{5}{3},-\frac{1}{3}.\]

La evaluación en -5 da

    \begin{align*}-3\cdot 125 + 25 - 15\cdot 5 +5&=-375+25-75+5\\&=-295,\end{align*}

así que -5 no es raíz.

La evaluación en -1 da

    \begin{align*}-3+1-15+5=-12,\end{align*}

así que -1 tampoco es raíz.

Como tarea moral, queda verificar que -\frac{5}{3} tampoco es raíz, pero que -\frac{1}{3} sí lo es.

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

  • Realiza las evaluaciones que faltan en el último ejemplo.
  • Determina las raíces racionales del polinomio

        \[x^7-6x^4+3x^3+18x-1.\]

  • Muestra que \sqrt[3]{12} no es un número racional.
  • Encuentra todos los candidatos a ser raíces racionales de

        \[x^3+\frac{2x^2}{3}-7x-\frac{14}{3}.\]

    Determina cuáles sí son raíces.
  • Puede que un polinomio en \mathbb{Z}[x] no tenga raíces racionales, pero que sí se pueda factorizar en \mathbb{Z}[x]. Investiga acerca del criterio de irreducibilidad de Eisenstein.

Á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: Esbozo de construcción de los números racionales y reales

Introducción

En la unidad pasada vimos la construcción de los números enteros a partir de los números naturales. Lo que hicimos fue considerar a parejas de naturales (a,b) para las cuales dimos la relación de equivalencia (a,b)\sim (c,d) si y sólo si a+d=b+c. Dijimos que, aunque era incorrecto formalmente, convenía pensar a (a,b) como a-b (es incorrecto pues en \mathbb{N} no hay resta).

La relación de equivalencia \sim creó clases de equivalencia en \mathbb{N}\times \mathbb{N}, en donde cada clase la denotamos por \overline{(a,b)}. El conjunto \mathbb{Z} lo construimos justo como el conjunto de todas las clases de equivalencia. En él dimos las operaciones

  • Suma: \overline{(a,b)}+\overline{(c,d)}=\overline{(a+c,b+d)}
  • Producto: \overline{(a,b)}\overline{(c,d)}=\overline{(ac+bd,ad+bc)}

Vimos que estas operaciones estaban bien definidas. La suma es bastante natural. El producto parece algo artificial, pero se vuelve natural si pensamos en que «queremos multiplicar a a-b con c-d«, pues justo (a-b)(c-d)=(ac+bd)-(ad+bc). Recordemos que es una justificación informal, pero ayuda a entender la intuición.

Después, nos dedicamos a probar que con esta operación suma y producto, el conjunto \mathbb{Z} era un anillo conmutativo con 1 en donde se vale cancelar. A partir de ahí empezamos a ver a \mathbb{Z} desde un punto de vista de teoría de números. Estudiamos al máximo común divisor, la relación de divisibilidad, el anillo de enteros módulo n, congruencias, ecuaciones en congruencias, teorema chino del residuo y mencionamos un poco de ecuaciones diofantinas.

Con eso terminamos la unidad de enteros, correspondiente al segundo segundo parcial del curso.

Las siguientes dos unidades contempladas por el temario oficial son:

  • Números complejos
  • Anillo de polinomios

Aquí vale la pena hacer una observación. Típicamente, tenemos la siguiente cadena de contenciones entre sistemas numéricos

    \[\mathbb{N}\subset \mathbb{Z}\subset \mathbb{Q} \subset \mathbb{R}\subset \mathbb{C}.\]

En las primeras dos unidades del curso hablamos de \mathbb{N} y de \mathbb{Z}. De acuerdo a la contención anterior, lo siguiente sería tratar a detalle a los racionales \mathbb{Q} y a los reales \mathbb{R}. Sin embargo, el temario oficial «se los salta». Esto es un poco raro, pero podría estar justificado en que estos sistemas numéricos se estudian en otros cursos del plan de estudios. Por ejemplo, \mathbb{R} se estudia con algo de profundidad en los cursos de cálculo.

De cualquier forma, nos va a ser muy útil mencionar por lo menos por encima cómo hacer la construcción de los \mathbb{Q} y de \mathbb{R}. La construcción de los números racionales ayuda a repasar la construcción de los enteros. En la construcción de los números reales nos encontraremos con propiedades útiles que usaremos repetidamente cuando hablemos de la construcción de los números complejos \mathbb{C}. Por estas razones, aunque no vayamos a evaluar las construcciones de \mathbb{Q} y de \mathbb{R} en el curso, las ponemos aquí para que las conozcas o las repases.

Motivación de construcción de los racionales

La motivación que tuvimos para construir los enteros es que los naturales no son suficientes para resolver todas las ecuaciones de la forma

    \[x+a=b,\]

pues si a>b, esta ecuación no tiene solución en \mathbb{N}.

En \mathbb{Z} todas estas ecuaciones tienen solución. Sin embargo, en \mathbb{Z} la ecuación

    \[ax=b\]

tiene solución si y sólo si a divide a b (por definición), pero no siempre sucede esto. Por ejemplo, 3x=7 no tiene solución en los enteros.

Construcción de los racionales

Para la construcción de los racionales, consideraremos de nuevo parejas, pero ahora de enteros. De esta forma, consideremos \mathbb{Z}\times \mathbb{Z} y sobre él consideremos la relación (a,b)\sim (c,d) si y sólo si ad=bc. Resulta que \sim es relación de equivalencia, así que para cada pareja (a,b) denotamos con \overline{(a,b)} como su clase de equivalencia.

Observa que la construcción que se parece mucho a cuando estábamos construyendo \mathbb{Z}, pero ahora nos estamos basando en el producto de \mathbb{Z} (antes era en la suma de \mathbb{N}). De nuevo, una forma de pensar bastante intuitiva (aunque formalmente incorrecta), es pensar a cada clase \overline{(a,b)} » como si fuera \frac{a}{b} «.

Hay un detalle. Para que todo funcione bien más adelante, necesitaremos considerar sólo aquellas parejas (a,b) tales que b\neq 0. De esta forma, por definición, \mathbb{Q} es el conjunto de clases de equivalencia de las parejas (a,b) en donde b\neq 0, en símbolos,

    \[\mathbb{Q}:=\{\overline{(a,b)}: a\in \mathbb{Z}, b\in \mathbb{Z}\setminus\{0\}\}.\]

Operaciones y orden en los racionales

Necesitamos definir las operaciones en \mathbb{Q}. Ahora el producto es «intuitivo» y la suma no tanto.

  • Suma: \overline{(a,b)} + \overline{(c,d)} = \overline{(ad+bc,bd)}
  • Producto: \overline{(a,b)}\overline{(c,d)}=\overline{(ac,bd)}

La suma se vuelve mucho más intuitiva pensando en nuestra interpretación (informal) de \overline{(a,b)} como \frac{a}{b}, pues por lo que aprendimos en educación primaria de la suma de fracciones, tenemos que

    \[\frac{a}{b}+\frac{c}{d}=\frac{ad+bc}{bd}.\]

Para definir el orden en \mathbb{Q} hacemos lo siguiente. Tomemos a la pareja (a,b) de enteros. Diremos que la clase \overline{(a,b)} es

  • Cero si a=0,
  • Positiva, si ambos o ninguno de a y b son negativos con el orden en \mathbb{Z} y
  • Negativa si exactamente uno de a y b son negativos con el orden en \mathbb{Z}.

Diremos que \overline{(a,b)}>\overline{(c,d)} si \overline{(a,b)}-\overline{(c,d)} es positiva.

Se puede probar que estas operaciones suma y producto, así como el orden están bien definidas (no dependen de la clase de equivalencia). Además, se puede probar lo siguiente.

Teorema. El conjunto \mathbb{Q} con sus operaciones de suma y producto es un campo ordenado.

Un campo lo puedes pensar como un conjunto con operaciones suma y multiplicación tales que:

  • La suma es asociativa, conmutativa, tiene un neutro 0 e inversos aditivos
  • La multiplicación es asociativa, conmutativa, tiene un neutro 1 y todo elemento distinto de 0 tiene inverso multiplicativo.
  • Se tiene distributividad a(b+c)=ab+ac.

Ejemplo. La clase \overline{(c,c)} es el neutro multiplicativo, pues si tenemos \overline{(a,b)} y hacemos la multiplicación de ambos, obtenemos \overline{(ac,bc)}, que es igual a \overline{(a,b)} pues (ac)b=abc=(bc)a. Nota que aquí estamos usando que el producto en \mathbb{Z} es asociativo y conmutativo.

La clase \overline{(a,b)} tiene inverso mutiplicativo \overline{(b,a)} pues el producto de ambas es \overline{(ab,ba)}, y como ab=ba, tenemos que esta es la clase \overline{(c,c)}, que ya dijimos que es el neutro multiplicativo.

\square

Notación simple de racionales y ecuaciones aún sin solución

Ya que se prueban las propiedades anteriores estas cosas, ya no vale la pena conservar la notación de parejas y de clases de equivalencia, por lo cual a la clase de equivalencia \overline{(a,b)} simplemente se le denota por \frac{a}{b}, a partir de lo cual nuestra interpretación de pensarlo así ya se vuelve formal. Se puede mostrar que todo lo que aprendimos de esta notación en la primaria se deduce de las propiedades de \mathbb{Q}.

Ahora sí, la ecuación

    \[ax=b\]

tiene solución casi siempre, el único problema es si a=0. Pero si a\neq 0, la solución es única y es x=\frac{b}{a}.

El conjunto \mathbb{Q} es bastante bueno algebraicamente, pero le falta todavía más para ser bueno para análisis y cálculo. Todavía tiene «bastantes hoyos»: en él no podemos probar, por ejemplo, el teorema del valor intermedio para funciones continuas. Así mismo, hay varias ecuaciones que todavía no tienen solución en \mathbb{Q}.

Ejercicio. La ecuación x^2=3 no tiene una solución en \mathbb{Q}.

Una forma de enunciar el resultado anterior es decir «\sqrt{3} es irracional». Pero nota que es incorrecto enunciarlo así, pues para ponerle un nombre a \sqrt{3}, es necesario saber quién es, y justo el punto del ejercicio es que, tan sólo con \mathbb{Q}, no podemos definirlo.

Solución. Vamos a proceder por contradicción. Supongamos que la ecuación x^2=3 tiene una solución p/q en los racionales. De esta forma,(p/q)^2=3. Multiplicando por q^2 en ambos lados, p^2=3q^2.

La factorización en primos del lado izquierdo tiene una cantidad par de 3‘s. La factorización en primos del lado derecho tiene una cantidad impar de 3‘s. Esto es una contradicción al teorema fundamental de la aritmética, por lo tanto, no existe p/q solución racional de x^2=3.

\square

Reales y hoyos en los racionales

Para la construcción de los reales, ya no podemos proceder como le hemos estado haciendo, considerando simplemente parejas de números del sistema anterior y construyendo una relación de equivalencia sobre ellas. Lo que buscamos cuando damos el paso entre \mathbb{Q} y \mathbb{R} ya no es simplemente que los números tengan «inversos aditivos» o «inversos multiplicativos», sino que «todos los conjuntos acotados por abajo tengan un mejor mínimo». Esto es lo que garantiza que se «llenen los hoyos» que tienen los racionales.

Entendamos más formalmente esta definición de «hoyo»:

Definición. Para un conjunto X con un orden total \le y S un subconjunto S de X, un ínfimo de S es un r\in X tal que

  • r\leq s para todo s\in S y
  • si t\leq s para todo t\in S, entonces t\leq s.

Definición. Un conjunto X con un orden total \le es completo si todo conjunto S acotado inferiormente tiene un ínfimo.

Ejemplo. El conjunto \mathbb{Q} no es completo, pues el conjunto

    \[S=\{x\in \mathbb{Q}: x^2\geq 3\}\]

está acotado inferiormente, pero no tiene un ínfimo.

Sucesiones de Cauchy y construcción de los reales

Hay varias formas de construir un sistema numérico que extienda a \mathbb{Q} y que no tenga hoyos. Se puede hacer mediante cortaduras de Dedekind, mediante expansiones decimales o mediante sucesiones de Cauchy de racionales. Todas estas construcciones son equivalentes. Daremos las ideas generales de la última.

Definición. Una sucesión

    \[\{x_n\}=\{x_1,x_2,x_3,\ldots\}\]

es de Cauchy si para todo N existe un M tal que si m\geq M y n\geq M, entonces |x_m-x_n|<\frac{1}{N}. Denotamos con C(\mathbb{Q}) al conjunto de todas las sucesiones de números racionales que sean de Cauchy.

Construiremos una relación de equivalencia \sim en C(\mathbb{Q}). Si tenemos dos de estas sucesiones:

    \begin{align*}\{x_n\}&=\{x_1,x_2,x_3,\ldots\} \quad \text{y}\\\{y_n\}&=\{y_1,y_2,y_3,\ldots\},\end{align*}

diremos que \{x_n\}\sim \{y_n\} si para todo natural N existe un natural M tal que para n\geq M tenemos que

    \[|x_n-y_n|<\frac{1}{N}.\]

Se puede probar que \sim es una relación de equivalencia. Para cada sucesión \{x_n\} de Cauchy usamos \overline{\{x_n\}} para denotar a la clase de equivalencia de \{x_n\}. Por definición, el conjunto \mathbb{R} es el conjunto de clases de equivalencia de \sim, en símbolos:

    \[\mathbb{R}:=\{\overline{\{x_n\}}: \{x_n\} \in C(\mathbb{Q})\}.\]

Operaciones y orden en los reales

En \mathbb{R} podemos definir las siguientes operaciones:

  • Suma: \overline{\{x_n\}} + \overline{\{y_n\}}= \overline{\{x_n + y_n\}} .
  • Producto: \overline{\{x_n\}} \overline{\{y_n\}}= \overline{\{x_ny_n\}}.

También podemos definir el orden en \mathbb{R}. Decimos que \overline{\{x_n\}} es positivo si para n suficientemente grande tenemos x_n>0. Decimos que \overline{\{x_n\}}>\overline{\{y_n\}} si \overline{\{x_n\}}- \overline{\{y_n\}} es positivo.

Se puede ver que las operaciones de suma y producto, así como el orden, están bien definidos. Más aún, se puede probar el siguiente resultado.

Teorema. El conjunto \mathbb{R} con sus operaciones de suma y producto es un campo ordenado y completo.

Como antes, una vez que se prueba este teorema, se abandona la notación de sucesiones y de clases de equivalencia. En realidad se oculta, pues la construcción siempre está detrás, como un esqueleto que respalda las propiedades que encontramos.

El teorema nos dice que \mathbb{R} ya no tiene hoyos, y esto es precisamente lo que necesitamos para resolver algunas ecuaciones como x^2=3. Un esbozo de por qué es el siguiente. Gracias a la existencia de ínfimos se puede probar el teorema del valor intermedio en \mathbb{R}. Se puede probar que la función x^2 es continua, que en x=0 vale 0 y que en x=2 vale 4, de modo que por el teorema del valor intermedio debe haber un real x tal que x^2=3.

Reflexión final y motivación de números complejos

Las muchas otras importantes consecuencias de que \mathbb{R} sea un campo ordenado y completo se discuten a detalle en cursos de cálculo. Si bien este es un logro enorme, aún tenemos un pequeño problema: ¡todavía no podemos resolver todas las ecuaciones polinomiales! Consideremos la ecuación

    \[x^2+1=0.\]

Podemos mostrar que para cualquier real x tenemos que x^2\geq 0, de modo que x^2+1\geq 1>0. ¡Esta ecuación no tiene solución en los números reales!

Para encontrar una solución, necesitaremos construir a los números complejos, a \mathbb{C}. Con ellos vamos a poder, finalmente, resolver todas las ecuaciones polinomiales, es decir, aquellas de la forma

    \[a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0=0.\]

Hablaremos de esto en el transcurso de las siguientes dos unidades: números complejos y polinomios.

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.

  • ¿Cuál de las clases de equivalencia sería el neutro aditivo en \mathbb{Q}?
  • ¿Por qué la definición de orden en \mathbb{Q} no depende del representante elegido?
  • ¿Cómo construirías el inverso multiplicativo de la sucesión de Cauchy \{x_n\}? Ten cuidado, pues algunos de sus racionales pueden ser 0.
  • Aprovecha esta entrada de transición entre unidades para repasar las construcciones de \mathbb{N} y de \mathbb{Z}.

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