Archivo de la etiqueta: superior

Á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: Ejercicios de los teoremas de Fermat y de Wilson

Primero, un ejercicio más de congruencias:

Un ejercicio de congruencias

Un ejercicio utilizando el teorema de Fermat:

Ejercicio utilizando el teorema de Fermat

Ejercicio sencillo utilizando el Teorema de Wilson:

17!=1 (mod 19)

Otro ejercicio utilizando el Teorema de Wilson:

Si p primo, (p-1)! = -1 (mod p)

Á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*}

Álgebra Superior II: Problemas de divisibilidad

A continuación les dejo los links que les preparé para hoy. Se ven en el orden que están. Si tienen dudas, pueden ponerlas en la sección de comentairos de aquí del blog.

Ejemplo de algoritmo de la división de Euclides
Condición necesaria para que 2^n+1 sea primo
a-b divide a a^n-b^n

Álgebra Superior II: Congruencias y el anillo de enteros módulo n

Esta es una serie de entradas de blog para dar seguimiento a los estudiantes de mi curso de Álgebra Superior II durante la época de cuarentena debida al coronavirus.

Introducción

En clases pasadas hemos platicado del algoritmo de la división, del máximo común divisor, el mínimo común múltiplo, de primos, el teorema fundamental de la aritmética, la infinidad del conjunto de primos y del algoritmo de Euclides para encontrar el máximo común divisor.

En esta entrada platicaremos acerca del anillo de los enteros módulo n. La idea de esta entrada es:

  • Dar la intuición a través de un ejemplo concreto
  • Dar la definición formal de a\equiv b \pmod n
  • Definir a \mathbb{Z}_n, el anillo de enteros módulo n, dando sus elementos y sus operaciones de suma y resta.
  • Dar ejemplos adicionales de operaciones concretas.
  • Hablar de cuáles son los elementos de \mathbb{Z}_n que tienen inversos multiplicativos y cuándo \mathbb{Z}_n es un campo.

A grandes rasgos, el anillo de los enteros módulo n consiste en ver a los enteros «como si sólo nos importara el residuo que dejan al dividirse entre n«.

Ejemplo introductorio

Hablemos de las horas que tiene un día. Un día tiene 24 horas y las podemos llamar del 0 al 24 para no tener que hacer distinción entre AM y PM. Por ejemplo, las 4PM serían las 16. Las 10AM simplemente las 10. La hora 24 vamos a pensarla más bien como la hora 0 del siguiente día.

Si son las 8 (de la mañana, pero ya no hace falta aclarar), entonces tres horas después serán las 11. Si son las 10, entonces cuatro horas después serán las 14. Pero si son las 22 y pasan 7 horas, entonces van a ser las 29, pero conviene pensar a esa hora como las 5 (del día siguiente), pues así es más claro qué hora entre 0 y 23 es. Finalmente si son las 17 y pasan 24 horas, entonces la hora que obtenemos es la 17+24=41, pero justo como pasan 24 horas, siguen siendo las 17: aunque el día cambió, la hora no.

De esta discusión recuperamos lo siguiente:

  • En «el mundo de las horas», la hora 29 es la misma que la hora 5. En símbolos, esto lo ponemos como 29\equiv 5 \pmod {24}.
  • Podemos «sumar en el mundo de las horas». Ahí, 10+4 es 14, pero 22+7 es 5. Vamos a escribir 10+4\equiv 14 \pmod {24} y 22+7\equiv 5 \pmod {24}.
  • En «el mundo de las horas», si sumamos 24 horas no pasa nada.

Definición del anillo \mathbb{Z}_n

En el ejemplo de motivación trabajamos con horas, que «se ciclan cada 24». Pero aquí el 24 no tiene nada de especial y de hecho lo podemos hacer con cualquier número n. Comencemos definiendo qué quiere decir que dos enteros sean iguales «en el mundo de n«.

Definición. Sea n un entero positivo. Sean a y b enteros. Vamos a decir que a es congruente con b módulo n si n divide a a-b. En símbolos:

    \[a\equiv b \pmod n \quad \iff \quad n\mid b-a.\]

Proposición. Para todo entero positivo n la relación en \mathbb{Z} de «ser congruente módulo n » es una relación de equivalencia.

Demostración. Tenemos que probar que dicha relación es reflexiva, simétrica y transitiva.

Para ver que la relación es reflexiva, tomemos a en \mathbb{Z}. Tenemos que n divide a 0=a-a, pues n\cdot 0 =0 (dicho de otra forma, 0 está en n\mathbb{Z}). Así, a\equiv a \pmod n.

Veamos ahora que la relación es simétrica. Si a\equiv b \pmod n, entonces n divide a a-b, pero entonces también divide a su inverso aditivo b-a (aquí estamos usando que n\mathbb{Z} es ideal, y que los ideales son cerrados bajo inversos aditivos), de modo que b\equiv a \pmod n.

Finalmente, veamos que la relación es transitiva. Para ello, a partir de enteros a, b y c tales que a\equiv b \pmod n y b\equiv c \pmod n tenemos que mostrar que a\equiv c \pmod n. Por definición, las primeras dos congruencias quieren decir que n divide a a-b y a b-c. Pero sabemos que si un entero divide a dos enteros, entonces divide a su suma. Así, n\mid (a-b)+(b-c)=a-c, que por definición quiere decir que a\equiv c \pmod n.

\square

Ya que «ser congruente módulo n» es una relación de equivalencia, entonces podemos dividir a todo \mathbb{Z} en las clases de equivalencia de esta relación, y escribir como [a]_n a la clase de equivalencia que tiene al entero a. La siguiente proposición muestra que para cada clase de equivalencia siempre podemos encontrar un representante chiquito.

Proposición. Sea n un entero positivo. Se tiene que a\equiv b \pmod n si y sólo si a y b dejan el mismo residuo al dividirse entre n en el algorimo de la división. En particular, para cada a siempre existe un entero r en \{0,1,\ldots,n-1\} tal que a\equiv r \pmod n.

Demostración. Usemos el algoritmo de la división para escribir a=qn+r y b=pn+s con r y s los residuos de la división, que el algoritmo de la división garantiza que están en \{0,1,\ldots,n-1\}.

Si r=s, entonces a-b=(q-p)n, así que n\mid a-b y así a\equiv b \pmod n. Si a\equiv b \pmod n, entonces

    \[n\mid a-b= (q-p)n+(r-s).\]

Como n\mid (q-p)n, entonces n\mid r-s. Sin embargo, usando que r y s están en \{0,1,\ldots,n-1\}, tenemos que r-s es un número entre -(n-1) y n-1, de modo que la única posibilidad es r-s=0, es decir, r=s. Esto prueba la primer parte de la proposición.

Como a y r dejan el mismo residuo r al dividirse entre n, entonces a\equiv r \pmod n.

\square

Ejemplo. Fijemos n=7. Tenemos que las siguientes clases de equivalencia son la misma: [13]_7, [20]_7, [-1]_7. Esto es ya que, por ejemplo, 7 divide a 20-13=14 y 7 divide a 20-(-1)=21. De hecho, todas estas clases son iguales a la clase [6]_7, pues tanto -1, 6, 13 como 20 son números que al dividirse entre 7 dejan residuo 6.

Estamos listos para presentar a los elementos del anillo de enteros módulo n.

Definición. Para n un entero positivo, definimos a Z_n como el conjunto de clases de equivalencia de la relación «ser congruente módulo n«. Por la proposición anterior, tenemos entonces que

    \[Z_n=\{[0]_n, [1]_n, \ldots, [n-1]_n\}\]

Nota que Z_n tiene exactamente n elementos, uno por cada uno de los posibles residuos de dividir un número entre n. Nota también que \mathbb{Z}_n no es lo mismo que el ideal n\mathbb{Z}, y que hay que ser cuidadosos con la notación. De hecho, el ideal n\mathbb{Z} es uno de los elementos de \mathbb{Z}_n.

Ejemplo. Z_4=\{[0]_4,[1]_4, [2]_4,[3]_4\} tiene 4 elementos. El elemento [3]_4 consiste de todos los enteros que dejan residuo 3 al dividirse entre 4, es decir, [\ldots,-5,-1,3,7,\ldots].

Definición. Sea n un entero positivo y [a]_n y [b]_n clases de equivalencia de la relación «ser congruentes módulo n«. Definimos las siguientes operaciones de suma y producto:

  • [a]_n + [b]_n = [a+b]_n, y
  • [a]_n [b]_n = [ab]_n.

Estas operaciones es decir, esta suma y producto «están bien definidas» y no dependen de los representantes elegidos, como muestra la siguiente proposición:

Proposición. Sea n un entero positivo. Si a\equiv a' \pmod n y b\equiv b' \pmod n, entonces a+b \equiv a'+b' \pmod n y ab\equiv a'b' \pmod n.

Demostración. De la primer congruencia tenemos n\mid a-a' y de la segunda n\mid b-b'. Como n divide a estos dos números, divide a su suma, y reacomodando tenemos que n\mid (a+b) - (a'+b'), que es equivalente a a+b\equiv a'+b' \pmod n, una de las congruencias que queríamos.

Para el producto, de n\mid a-a' podemos obtener

    \[n\mid (a-a')b=ab-a'b\]

y de n\mid b-b' podemos obtener

    \[n\mid a'(b-b')=a'b-a'b'.\]

Así,

    \[n\mid (ab-a'b)+(a'b-a'b')=ab-a'b'.\]

De aqui, ab\equiv a'b' \pmod n, la otra congruencia que queríamos.

\square

El anillo de enteros módulo n es precisamente \mathbb{Z}_n equipado con las operaciones de suma y producto que acabamos de definir.

Ejemplos de operaciones en \mathbb{Z}_n

Estos son algunos ejemplos básicos de operaciones en \mathbb{Z}_7 y en \mathbb{Z}_{11}:

  • [8]_7+[4]_7=[12]_7=[5]_7
  • [4]_{11}[8]_{11}=[32]_{11}=[21]_{11}=[10]_{11}

En una siguiente entrada, preparada por Clau, verán más ejemplos de operaciones en \mathbb{Z}_n.

Inversos multiplicativos en \mathbb{Z}_n

El cero del anillo de enteros módulo n es [0]_n, pues para cualquier entero a se tiene que [a]_n+[0]_n=[a+0]_n=[a]_n. Como [0]_n consiste precisamente de los múltiplos de n, tenemos entonces que [a]_n+[kn]_n=[a]_n.

La multiplicación en este anillo tiene como identidad a [1]_n, de lo cual te puedes convencer con una cuenta similar.

La suma de este anillo tiene inversos aditivos pues para cualquier entero a se tiene que la clase de a y la de -a cumplen

    \[[a]_n+[-a]_n=[a+(-a)]_n=[0]_n.\]

Sin embargo, no es cierto que para cualquier clase [a]_n esta tenga un inverso multiplicativo. A los números que sí tienen un inverso multiplicativo se les conoce como unidades del anillo.

Problema: Muestra que [4]_{12} no tiene inverso multiplicativo en \mathbb{Z}_{12}

Intenta resolver este problema antes de ver la solución.

Solución. Procedamos por contradicción. Si [a]_{12} fuera el inverso multiplicativo de [4]_{12}, tendríamos que [1]_{12}=[4a]_{12} y por lo tanto que 4a\equiv 1 \pmod {12}, es decir, que 12\mid 4a-1. Como 4\mid 12 y 4\mid 4a, tendríamos entonces que 4\mid (4a-1)-4a = -1. Esto es una contradicción.

La siguiente proposición dice exactamente quienes son los elementos en \mathbb{Z}_n que tienen inversos multiplicativos en \mathbb{Z}_n.

Teorema. Sea n un entero positivo. La clase [a]_n de \mathbb{Z}_n tiene inverso multiplicativo si y sólo si a y n son primos relativos.

Demostración. Recordemos que por definición a y n son primos relativos si su máximo común divisor MCD(a,n) es igual a 1. Recordemos también que MCD(a,n) puede escribirse como combinación lineal entera de a y n.

Si a y n son primos relativos, entonces existen p y q enteros tales que 1=ap+nq. Así,

    \[[ap]_n=[ap+nq]_n=[1]_n,\]

de modo que la clase [a]_n tiene como inverso multiplicativo a la clase [p]_n.

Si a y n no son primos relativos y suponemos que [a]_n tiene inverso multiplicativo, entonces llegaremos a una contradicción similar a la del problema anterior. Verifica los detalles.

\square

Recuerda que un campo es un anillo conmutativo en el cual todo elemento distinto de cero tiene un inverso multiplicativo. Terminamos esta sesión con un resultado que nos dice cuándo \mathbb{Z}_n es un campo.

Proposición. Sea n un entero. El conjunto \mathbb{Z}_n con las operaciones de suma y producto que definimos es un campo si y sólo si n es un número primo.

Demostración. Como ya sabemos que es un anillo conmutativo, basta con determinar cuándo sucede que todos los elementos distintos de cero tienen un inverso multiplicativo. Estos elementos son son [1]_n, \ldots, [n-1]_n. Por la proposición anterior, estos tienen inversos si y sólo si cada uno de los números 1,2,\ldots,n-1 es primos relativos con n.

Si n es primo, entonces todos esos números son primos relativos con n pues el único factor en común que tienen con n es 1. Si n no es primo, entonces tiene un divisor d que satisface 1<d<n, y por lo tanto n y d no son primos relativos, así que [d]_n no tiene inverso multiplicativo.

De esta forma, \mathbb{Z}_n es un campo si y sólo si n es primo.

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

  • Argumenta por qué «el mundo de los minutos» también es un ejemplo de enteros módulo n.
  • Muestra que n\mathbb{Z} es uno de los elementos de \mathbb{Z}_n.
  • Muestra que las operaciones de suma y producto en \mathbb{Z}_n en efecto satisfacen la definición de anillo conmutativo. Sugerencia: aprovecha que \mathbb{Z} es un anillo conmutativo con sus operaciones de suma y producto.
  • Muestra que [1]_n es identidad para el producto en \mathbb{Z}_n.
  • Completa la prueba del teorema de inversos multiplicativos.