Archivo de la etiqueta: naturales

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

Álgebra Superior II: Ecuaciones en congruencias

Introducción

En entradas anteriores platicamos de congruencias y de algunos teoremas que se pueden usar para trabajar con potencias y factoriales módulo un entero. Ya que tenemos un buen manejo de la aritmética en congruencias, podemos comenzar a hacernos preguntas acerca de las ecuaciones que pueden se plantear y resolver en estos términos.

Ejemplo. ¿Cuáles son las soluciones enteras a la ecuación x\equiv 3 \pmod 6?

Solución. Un número x satisface la ecuación si y sólo si 6 divide a x-3, lo cual sucede si y sólo si x es de la forma x=6r+3, donde r es un número entero. Así, el conjunto de soluciones es de la forma

    \[6\mathbb{Z}+3:= \{6r+3: r\in \mathbb{Z}\}.\]

Dicho de otra forma, el conjunto de soluciones es la clase de equivalencia del 3 módulo 6, es decir, [3]_6.

\square

Cuando tengamos ecuaciones más complicadas, usualmente lo que haremos es dejar expresada la solución en términos de congruencias, es decir, como uno o varios elementos de \mathbb{Z}_n. Si se quiere encontrar a todos los enteros (en \mathbb{Z}) que sean solución, basta recordar este ejemplo para expresar a las soluciones en \mathbb{Z}_n como conjuntos de soluciones en \mathbb{Z}.

Ejemplo. ¿Cuáles son las soluciones enteras a la ecuación 2x+1\equiv 0 \pmod 7?

Solución. Trabajemos módulo 7. Restando 1 de ambos lados obtenemos

    \[2x\equiv -1\equiv 6 \pmod 7.\]

Multiplicando por 4 de ambos lados tenemos que

    \[8x\equiv 24\equiv 3\pmod 7.\]

Como 8x\equiv x \pmod 7, tenemos que x\equiv 3 \pmod 7 es la solución.

\square

En el ejemplo anterior encontramos las soluciones módulo 7. Si queremos encontrar las soluciones en enteros, basta expresar esta congruencia en términos de enteros: las soluciones en \mathbb{Z} son los números de la forma 7r+3 con r entero.

Ecuaciones lineales en congruencias

Una ecuación lineal en congruencias es de la forma

    \[ax\equiv b\pmod n.\]

Vamos a estudiar esta ecuación, viendo cuándo tiene solución y cuántas soluciones módulo n tiene. Hay un caso fácil de estudiar, que es cuando a y n son primos relativos.

Proposición 1. Sean a,b enteros y n un entero positivo tales que \text{MCD}(a,n)=1. Entonces la ecuación

    \[ax\equiv b \pmod n\]

tiene una única solución x módulo n.

Demostración. Como a y n son primos relativos, a tiene un inverso multiplicativo módulo n, digamos a^{-1}. Afirmamos que x=a^{-1}b es solución. En efecto, a(a^{-1}b)\equiv 1\cdot b\equiv b \pmod n.

Ahora, afirmamos que la solución es única. Supongamos que x y y son solución. Tendríamos entonces que

    \[ax\equiv b \equiv ay \pmod n.\]

Multiplicando ambos extremos de esta ecuación por a^{-1}, tenemos que

    \[x\equiv a^{-1}ax\equiv a^{-1}a y \equiv y \pmod n.\]

\square

Sin embargo, como ya vimos antes, no siempre pasa que todo elemento tenga inverso multiplicativo. Necesitamos un análisis más detallado.

Notemos que x es solución de ax\equiv b\pmod n si y sólo si n divide a ax-b, lo cual sucede si y sólo si existe un entero y tal que ax-b=ny. Reordenando, tenemos que ax-ny=b. En otras palabras, la ecuación en congruencias tiene solución si y sólo si podemos expresar a b como combinación lineal entera de a y n, lo cual sucede si y sólo si

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

es decir, si y sólo si b es múltiplo del máximo común divisor de a y n. Resumimos esta primer parte del análisis en la siguiente proposición.

Proposición 2. Sean a,b enteros y n un entero positivo. La ecuación ax\equiv b\pmod n tiene solución si y sólo si \text{MCD}(a,n) divide a b.

Ahora, queremos entender cuántas soluciones diferentes hay módulo n.

Ejemplo. Encuentra todas las soluciones a la ecuación 4x\equiv 1 \pmod 8 y a la ecuación 4x\equiv 0 \pmod 8.

Solución. Tenemos que \text{MCD}(4,8)=4 y que 4 no divide a 1, así que la primer ecuación no tiene solución. Tenemos que 4 sí divide a 0, así que la segunda ecuación sí tiene solución. Veamos cuántas tiene.

Notemos que al multiplicar por 4 cada uno de los elementos 0,2,4,6 obtenemos respectivamente 0,8,16,24, que son todos múltiplos de 8, así que estos elementos de \mathbb{Z}_8 son solución. Al multiplicar 4 por 1,3,5,7 obtenemos 4,12,20,28, que módulo 8 son 4,4,4,4, así que ninguno de estos números son solución. Así, las soluciones son x\equiv 0,2,4,6\pmod 8.

\square

Una forma alternativa de expresar la solución del problema anterior es darse cuenta de que las soluciones en enteros son los números pares, o bien los enteros n tales que n\equiv 0\pmod 2. En general, cuando la solución existe, podemos encontrar un módulo en la que la podemos describir de manera única. Este es el contenido de las siguientes dos proposiciones.

Proposición 3. Sean a,b enteros y n un entero positivo tales que M=\text{MCD}(a,n) divide a b. Sean a'=a/M, b'=b/M y n'=n/M (con a', b', n' enteros). El entero x es solución a la ecuación en congruencias ax\equiv b \pmod n si y sólo si es solución a la ecuación en congruencias a'x\equiv b'\pmod {n'}.

Demostración. Tenemos que x es solución a ax\equiv b \pmod n si y sólo si existe una combinación lineal entera ax-ny=b. Al dividir entre M\neq 0, esto sucede si y sólo si a'x-n'y=b', lo cual sucede si y sólo si x es solución a la ecuación en congruencias a'x\equiv b'\pmod {n'}.

\square

Estamos listos para enunciar el resultado principal de esta sección. Viene de la combinación de las ideas anteriores.

Teorema 1. Sean a,b enteros y n un entero positivo. La ecuación ax\equiv b\pmod n tiene solución si y sólo si M:=\text{MCD}(a,n) divide a b. Cuando sí hay solución, ésta se puede expresar de manera única en módulo n':=n/M.

Demostración. La primer parte es la Proposición 2. Una vez que sabemos que la ecuación tiene solución, por la Proposición 3 podemos encontrar la ecuación equivalente a'x\equiv b'\pmod {n'}, en donde a'=a/M y b'=b/M. En esta ecuación, a' y n' son primos relativos (ver Tarea moral abajo). Por la Proposición 1, tiene una solución única módulo n'.

\square

Como empezamos con una ecuación módulo n, quizás queremos saber cuántas soluciones tiene módulo n, y no módulo n'. De manera inmediata, obtenemos el siguiente resultado.

Corolario. Con la notación del teorema anterior, cuando la ecuación tiene solución, entonces tiene M soluciones módulo n.

Ejercicio. Resuelve la ecuación lineal en congruencias

    \[12x\equiv 18 \pmod {30}.\]

Intenta resolver este ejercicio antes de ver la solución. Puedes comenzar calculando el máximo común divisor de 12 y 30.

Solución. El máximo común divisor de 12 y 30 es 6, que sí divide a 18. Entonces sí hay soluciones, y habrá 6 soluciones módulo 30. Para encontrar la ecuación reducida equivalente, dividimos entre 6 para obtener

    \[2x\equiv 3 \pmod 5.\]

El inverso de 2 módulo 5 es 3. Multiplicando en ambos lados por 3 obtenemos la solución

    \[x\equiv 9 \equiv 4 \pmod 5.\]

Para recuperar las soluciones módulo 30, a cada una de estas soluciones le sumamos 30/6=5 repetidamente para obtener las soluciones x\equiv 4, 9, 14, 19, 24, 29 \pmod {30}.

\square

En la siguiente entrada veremos cómo resolver sistemas de ecuaciones lineales en los que tenemos más de una congruencia.

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.

  • Sea a un entero y n un entero positivo. Sea M=\text{MCD}(a,n) y sean a'=a/M y n'=n/M. Muestra que \text{MCD}(a',n')=1.
  • Demuestra el corolario al Teorema 1.
  • Verifica que, en efecto, las soluciones que obtuvimos en el ejemplo después del Teorema 1 sí son soluciones de la ecuación original.
  • Diseña una ecuación lineal módulo 60 que tenga exactamente 15 soluciones módulo 60.
  • Para prepararte para la siguiente entrada, intenta resolver por completo el sistema de congruencias

    \begin{align*}x&\equiv -1 \pmod{77}\\x&\equiv -1 \pmod{55}\\\end{align*}

Seminario de Resolución de Problemas: Principio de Inducción, Parte 2

En esta entrada continuaremos con ejemplos de uso del principio de inducción en la resolución de problemas. Es una continuación de la entrada anterior. Como recordatorio, aquí está el principio de inducción en la forma en la que lo hemos estado usando:

Principio de inducción. Sea P(n) una afirmación (o proposición o propiedad) que depende del número natural n. Si

  • la afirmación P(a) es cierta y
  • la veracidad de la afirmación P(n) implica la veracidad de la afirmación P(n+1),

entonces la afirmación P(n) es cierta para toda n \geq a.

Lo que nos interesa ahora es ver cómo el principio de inducción se mezcla con algunas de las heurísticas de resolución de problemas.

Inducción y trabajar hacia atrás

Lo que hemos hecho hasta ahora es lo siguiente. Tomamos un enunciado que depende de un entero n. Comenzamos probándolo para la base inductiva. Luego, suponemos la veracidad del enunciado para cierto entero n. A partir de ahí, intentamos conseguir la veracidad del enunciado para el entero n+1.

Como vimos cuando platicamos de trabajar hacia atrás, eso no siempre es lo más natural en la resolución de un problema. En algunas ocasiones nos conviene más empezar con el enunciado que queremos demostrar y mostrar que mediante pasos reversibles podemos llegar a algo cierto. Queremos aplicar esta idea para la demostración del paso inductivo.

Consideremos el siguiente ejemplo.

Problema. Demuestra que para todo entero no negativo n se tiene que

    \[\frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30}\]

es un número entero.

Solución. Tenemos que probar la afirmación para n\geq 0 entero. Procedemos por inducción sobre n. Si n=0, la expresión es igual a 0, así que la afirmación es cierta. Supongamos entonces que

    \[\frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30}\]

es entero y consideremos la expresión

    \[\frac{(n+1)^5}{5}+\frac{(n+1)^4}{2}+\frac{(n+1)^3}{3}-\frac{(n+1)}{30}.\]

Nuestro objetivo es mostrar que esta expresión es entera. Nos gustaría usar la hipótesis inductiva, así que queremos intentar encontrar dentro de esta expresión la expresión para n. Esto lo podemos hacer usando el binomio de Newton para abrir los binomios a potencias y luego agrupando. Tenemos que

    \begin{align*}\frac{(n+1)^5}{5}&=\frac{n^5+5n^4+10n^3+10n^2+5n+1}{5}\\&=\frac{n^5}{5}+n^4+2n^3+2n^2+n+\frac{1}{5}\\\frac{(n+1)^4}{2}&=\frac{n^4+4n^3+6n^2+4n+1}{2}\\&=\frac{n^4}{4}+2n^3+3n^2+2n+\frac{1}{2}\\\frac{(n+1)^3}{3}&=\frac{n^3+3n^2+3n+1}{3}\\&=\frac{n^3}{3}+n^2+n+\frac{1}{3}\\-\frac{n+1}{30}&=-\frac{n}{30}-\frac{1}{30}.\end{align*}

Así, cuando hagamos la suma tenemos los términos

    \[\frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30},\]

cuya suma es entera por hipótesis inductiva,

    \[n^4+2n^3+2n^2+n+2n^3+3n^2+2n+n^2+n,\]

que es entero pues n es entero y \frac{1}{5}+\frac{1}{2}+\frac{1}{3}-\frac{1}{30}=1, de modo que la suma total es suma de enteros y por lo tanto es un entero. Esto termina la prueba por inducción.

\square

Si no comenzábamos a manipular la expresión para n+1, hubiera sido muy difícil, sólo a partir de la de n, llegar a la de n+1.

Inducción y generalización

Una forma sencilla de combinar inducción con generalización es la siguiente:

  • Nos piden demostrar una afirmación para un natural muy específico.
  • En vez de eso, construimos un problema más general que funcione «para todos los naturales».
  • Resolvermos ese problema por inducción.

Veamos un ejemplo.

Problema. Muestra que

    \[\left(\frac{3+\sqrt{17}}{2}\right)^{2020}+ \left(\frac{3-\sqrt{17}}{2}\right)^{2020}\]

es un entero impar.

Solución. Sean \alpha=\frac{3+\sqrt{17}}{2} y \beta=\frac{3-\sqrt{17}}{2}. Se pide mostrar que \alpha^{2020}+\beta^{2020} es un entero impar. Mostraremos que, de hecho, \alpha^n+\beta^n es un entero impar para todo entero n\geq 1. Vamos a proceder por inducción fuerte (hablaremos un poco más de eso más adelante).

El primer caso es n=1 y notemos que \alpha^1+\beta^1=\alpha+\beta=3. Notemos también que \alpha\beta=\frac{9-17}{4}=-2, de modo que \alpha^2+\beta^2=(\alpha+\beta)^2-2ab=9+4=13, que también es impar. Supongamos ahora que sabemos que la afirmación es cierta para exponentes n-1 y n.

Consideremos el polinomio cuadrático

    \[(x-\alpha)(x-\beta)=x^2-(\alpha+\beta)x+\alpha\beta=x^2-3x-2.\]

Como \alpha y \beta son raíces, tenemos que \alpha^2-3\alpha-2=0 y \beta^2-3\beta -2=0. Multiplicando estas igualdades por \alpha^{n-1} y \beta^{n-1} respectivamente, sumando ambas igualdades obtenidas, y despejando \alpha^{n+1}+\beta^{n+1} llegamos a

    \[\alpha^{n+1}+\beta^{n+1}=3(\alpha^n+\beta^n})+2(\alpha^{n-1}+\beta^{n-1}).\]

De aquí la conclusión inductiva es inmediata. Como la hipótesis inductiva es que el resultado es cierto para los exponentes n y n-1, entonces en el lado derecho tenemos una suma de un entero impar con un entero par, que es un entero impar. Esto muestra que la afirmación es cierta para cuando los exponentes son n+1.

Para demostrar el problema original, basta con hacer la observación de que, en particular, \alpha^{2020}+\beta^{2020} es un entero impar.

\square

Hay otra forma de combinar inducción con generalización, pero es un poco más sofisticada. Para explicarla, es mejor comenzar con un ejemplo.

Problema. Demuestra que para todo entero n\geq 1 se tiene que

    \[\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}+\ldots + \frac{1}{n(n+1)} <1.\]

Antes de resolver el problema, intentemos hacer una solución «ingenua» que quiera usar inducción de manera directa. No hay ningún problema con hacer la base de inducción, pues para n=1 al lado izquierdo tenemos únicamente \frac{1}{2} y al lado derecho 1. Supongamos que el resultado es cierto para n, es decir, que

    \[\frac{1}{1\cdot 2}+\ldots + \frac{1}{n(n+1)} <1.\]

Llamémosle M a la expresión del lado izquierdo. Lo que queremos probar ahora es que el resultado es cierto para n+1, es decir, que M+\frac{1}{(n+1)(n+2)}<1. Sabemos que M<1, pero ahora estamos sumando un término positivo adicional. Es posible que este término arruine la desigualdad, pues M<1 es una afirmación «muy débil». Veamos cómo darle la vuelta a esta dificultad.

Solución. Sea P(n) la afirmación del problema. Consideremos la afirmación Q(n) que dice que para todo entero n\geq 1 se tiene que

    \[\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\ldots + \frac{1}{n(n+1)}} =1-\frac{1}{n+1}.\]

Si logramos demostrar Q(n), entonces P(n) será cierta de manera inmediata, pues 1-\frac{1}{n+1}<1. Vamos a demostrar Q(n) por inducción.

Tenemos que Q(1) es cierto pues en ambos lados de la igualdad queda \frac{1}{2}. Supongamos que Q(n) es cierto. Usando esto, tenemos que

    \begin{align*}\frac{1}{1\cdot 2}+\ldots+\frac{1}{n(n+1)} + \frac{1}{(n+1)(n+2)} &=\left(1-\frac{1}{n+1}\right)+\frac{1}{(n+1)(n+2)}\\&=1-\frac{(n+2)-1}{(n+1)(n+2)}\\&=1-\frac{1}{n+2},\end{align*}

es decir, que Q(n+1) es cierto. Así, por inducción Q(n) es cierto para todo entero n y con eso P(n) también.

\square

Lo que sucedió fue lo siguiente. Al hacer el paso inductivo, intentamos mostrar que P(n) implica P(n+1). Pero esto es imposible pues P(n) «es muy débil», o bien «pierde información de todo lo que está pasando». Sin embargo, cuando consideramos la afirmación auxiliar Q(n), resulta que esta «tiene más información». Aquí, esta información es «qué tal lejos está la expresión de 1 «

La afirmación Q(n) tiene tanta información, que ahora sí con ella se puede probar Q(n+1). Se termina el problema usando que Q(n) implica P(n). Así, la estrategia fue la siguiente:

  • Se tiene una afirmación P(n) que se quiere demostrar para todos los naturales. Hacer inducción no parece funcionar, pues P(n) parece no ser suficiente para probar P(n+1)
  • Se considera entonces una afirmación Q(n) más fuerte (que implique a P(n)), pero para la cual Q(n) sí pueda probar Q(n+1).
  • Se prueba Q(n) por inducción, y se concluye que P(n) es cierta.

Hay que ser cuidadosos. Parte del ingenio en usar esta estrategia consiste en poder identificar un balance la generalización Q(n) que necesitamos de modo que sí sirva para solucionar el problema original, pero que no sea demasiado ambiciosa como para que sea falsa.

Más ejemplos

Hay más ejemplos bastante elaborados del uso de estas ideas en Problem Solving Through Problems de Loren Larson, Secciones 2.1, 2.2, 2.3 y 2.4. Otro libro con muchos ejemplos interesantes es el Putnam and Beyond, de Gelca y Andreescu. También hay otros ejemplos de inducción en las siguientes entradas: