Archivo de la etiqueta: teoría de números

Álgebra Superior II: Teorema chino del residuo

Por Leonardo Ignacio Martínez Sandoval

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. También, aprendimos a resolver una ecuación lineal módulo $n$ . El resultado principal fue el siguiente:

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

Ya que sabemos resolver una ecuación lineal, el siguiente paso es aprender a resolver sistemas que involucren dos o más ecuaciones lineales. En esta entrada veremos primero cómo resolver un sistema de dos ecuaciones lineales.

Luego, veremos cómo resolver un sistema con más ecuaciones y demostraremos un resultado clásico: el teorema chino del residuo. Pero para eso necesitaremos el resultado para dos ecuaciones lineales. Vamos poco a poco.

Sistemas de dos ecuaciones lineales

Supongamos que queremos entender por completo el sistema de ecuaciones
$\begin{aligned} a x & \equiv b (\mod m) \\ c x & \equiv d (\mod n), \end{aligned}$

es decir, determinar cuándo existe una $x$ que satisfaga ambas ecuaciones y, si existe, determinar cómo se ven todas las soluciones. Por lo primero que nos tenemos que preocupar es por que cada una de las ecuaciones tenga solución: si alguna no tiene, entonces no hay solución para el sistema.

Así, lo primero que tiene que pasar es que $MCD (a, m)$ divida a $b$ y que $MCD (c, n)$ divida a $d$ . Cuando sí tienen solución, entonces podemos intercambiar a las ecuaciones por sus ecuaciones reducidas y obtener el sistema de ecuaciones lineales equivalente
$\begin{aligned} a^{'} x & \equiv b^{'} (\mod m^{'}) \\ c^{'} x & \equiv d^{'} (\mod n^{'}) . \end{aligned}$

La primera ecuación tiene una única solución módulo $m^{'}$ y la segunda una única solución módulo $n^{'}$ , así que este sistema es equivalente al sistema
$\begin{aligned} x & \equiv e (\mod m^{'}) \\ x & \equiv f (\mod n^{'}), \end{aligned}$

en donde $e$ y $f$ son las soluciones a cada una de las ecuaciones lineales reducidas por separado. Ahora sí podemos combinar ambas ecuaciones. Lo único que nos falta es entender cuándo los sistemas de esta forma tienen solución.

Ejemplo 1. El sistema lineal de ecuaciones
$\begin{aligned} x & \equiv 2 (\mod 6) \\ x & \equiv 4 (\mod 15) \end{aligned}$
no tiene solución.

Solución. La primera ecuación implica que $6 ∣ x - 2$ . Como $3 ∣ 6$ , por transitividad tenemos $3 ∣ x - 2$ , así que la primera ecuación implica que $x$ deja residuo $2$ al dividirse entre $3$ .

La segunda ecuación implica que $15 ∣ x - 4$ . Como $3 ∣ 15$ , por transitividad $3 ∣ x - 4$ , o bien $x \equiv 4 \equiv 1 (\mod 3)$ . Es decir, la segunda ecuación implica que $x$ deja residuo $1$ al dividirse entre $3$ . De esta forma, es imposible satisfacer simultáneamente ambas ecuaciones.

$△$

En el ejemplo anterior, $3$ es el máximo común divisor de $6$ y $15$ y por eso convino estudiar la divisibilidad entre $3$ . La siguiente proposición justo dice cuándo el sistema tiene solución en términos de cierta divisibilidad por el máximo común divisor de los módulos.

Proposición 4. Sean $a$ y $b$ enteros y $m$ y $n$ enteros positivos. El sistema lineal de ecuaciones en congruencias
$\begin{aligned} x & \equiv a (\mod m) \\ x & \equiv b (\mod n) \end{aligned}$

tiene solución si y sólo si $M := MCD (m, n)$ divide a $a - b$ . En este caso, la solución se puede expresar de manera única módulo $N := mcm (m, n)$ , el mínimo común múltiplo de $m$ y $n$ .

Demostración. Supongamos que $x$ es solución. Por la primera ecuación, $m ∣ x - a$ y como $M ∣ m$ , entonces $M ∣ x - a$ . De manera análoga, $M ∣ x - b$ . Así, $M ∣ (x - b) - (x - a) = a - b$ , lo cual prueba una implicación de la proposición.

Por otro lado, si $M$ divide a $a - b$ , entonces existe una combinación lineal de $m$ y $n$ que da $a - b$ , digamos $y m + z n = a - b$ , que podemos reescribir como $b + z n = a - y m$ . Tomemos $x = b + z n = a - y m$ . Notemos que
$\begin{aligned} x & = a - y m \equiv a (\mod m) \\ x & = b + z n \equiv b (\mod n), \end{aligned}$

de modo que $x$ es solución para el sistema. Notemos que $x + r N$ para cualquier $r$ entero y $N$ el mínimo común múltiplo de $m$ y $n$ también es solución pues $N \equiv 0 (\mod m)$ y $N \equiv 0 (\mod n)$ .

Veamos que la solución es única módulo $N$ . Si tenemos $x$ y $y$ que son soluciones al sistema, entonces tenemos
$\begin{aligned} x & \equiv a \equiv y (\mod m) \\ x & \equiv b \equiv y (\mod n), \end{aligned}$

lo cual implica $m ∣ x - y$ y $n ∣ x - y$ . Como $N$ es el mínimo común múltiplo, $N ∣ x - y$ , de modo que $x \equiv y (\mod N)$ .

Terminamos esta sección con un teorema que recopila todo lo que hemos mostrado para dos ecuaciones lineales.

Teorema 2. Consideremos el sistema de ecuaciones
$\begin{aligned} a x & \equiv b (\mod m) \\ c x & \equiv d (\mod n) . \end{aligned}$

Si $MCD (a, m)$ no divide a $b$ o $MCD (c, n)$ no divide a $d$ , entonces el sistema no tiene solución. Si tenemos ambas divisibilidades, entonces el sistema original es equivalente al sistema
$\begin{aligned} x & \equiv e (\mod m^{'}) \\ x & \equiv f (\mod n^{'}), \end{aligned}$

donde $e$ y $f$ son las soluciones únicas a las reducciones de la primer y segunda congruencia respectivamente. Si $MCD (m^{'}, n^{'})$ no divide a $e - f$ , entonces el sistema original no tiene solución. Si sí, entonces el sistema original tiene una única solución módulo $mcm (m^{'}, n^{'})$ .

Ejemplo 2. Determina las soluciones al siguiente sistema lineal de ecuaciones:
$\begin{aligned} 4 x & \equiv 12 (\mod 24) \\ 10 x & \equiv 5 (\mod 75) . \end{aligned}$

Solución. Para la primera ecuación, notamos que $MCD (4, 24) = 4$ sí divide a $12$ así que la ecuación sí tiene solución, y su conjunto solución es el mismo que el de $x \equiv 3 (\mod 6)$ .

Para la segunda ecuación, notamos que $MCD (10, 75) = 5$ sí divide a $5$ así que la ecuación sí tiene solución, y su conjunto solución es el mismo que el de $2 x \equiv 1 (\mod 15)$ . La solución de esta ecuación es $x \equiv 8 (\mod 15)$ . De este modo, el sistema original es equivalente al sistema:

$\begin{aligned} x & \equiv 3 (\mod 6) \\ x & \equiv 8 (\mod 15) . \end{aligned}$

Tenemos que $MCD (6, 15) = 3$ . Pero $3$ no divide a $3 - 8 = - 5$ . Entonces este sistema no tiene solución, y por lo tanto el original tampoco.

$△$

Hagamos un ligero cambio en el sistema de ecuaciones.

Ejemplo 3. Determina las soluciones al siguiente sistema lineal de ecuaciones:
$\begin{aligned} 4 x & \equiv 20 (\mod 24) \\ 10 x & \equiv 5 (\mod 75) . \end{aligned}$

Solución. Para la primera ecuación, notamos que $MCD (4, 24) = 4$ sí divide a $20$ así que la ecuación sí tiene solución, y su conjunto solución es el mismo que el de $x \equiv 5 (\mod 6)$ .

Tenemos que $MCD (6, 15) = 3$ y que $3$ sí divide a $5 - 8 = - 3$ , de modo que sí hay solución. Para encontrarla, expresamos a $- 3$ como combinación lineal de $6$ y $15$ : $5 - 8 = - 3 = (- 3) \cdot 6 + 1 \cdot 15.$

De aquí, $x = 8 + 15 = 23$ es una solución, y por lo tanto el conjunto de soluciones queda descrito módulo $mcm (6, 15) = 30$ de manera única como $x \equiv 23 (\mod 30)$ .

$△$

El teorema chino del residuo

Varias de las ideas que usamos para un sistema de dos ecuaciones lineales las podemos reciclar para cuando queremos encontrar una $x$ que satisfaga simultáneamente el sistema de ecuaciones lineales en congruencias
$\begin{aligned} a_{1} x & \equiv b_{1} (\mod m_{1}) \\ a_{2} x & \equiv b_{2} (\mod m_{2}) \\ ⋮ \\ a_{n} x & \equiv b_{n} (\mod m_{n}) \end{aligned}$

Si este sistema tiene solución, entonces claramente:

Cada una de las ecuaciones debe tener solución y,
cada par de ellas debe tener solución.

Lo impresionante del siguiente teorema es que estas dos condiciones son las únicas que tenemos que verificar para que el sistema tenga solución. Y afortunadamente ya estudiamos cuándo dos ecuaciones lineales en congruencias tienen una solución simultánea.

Si cada una de las ecuaciones del sistema tiene solución, entonces es única, así que podemos remplazar cada ecuación por su solución y obtener un sistema de ecuaciones en donde todos los coeficientes de $x$ son $1$ (como le hicimos en el caso de dos ecuaciones). El siguiente resultado estudia estos sistemas.

Teorema 3. Sea $n \geq 2$ un entero, $b_{i}$ enteros para $i \in {1, \dots, n}$ y $m_{i}$ enteros positivos para $i \in {1, \dots, n}$ . El sistema de ecuaciones en congruencias
$\begin{aligned} x & \equiv b_{1} (\mod m_{1}) \\ x & \equiv b_{2} (\mod m_{2}) \\ ⋮ \\ x & \equiv b_{n} (\mod m_{n}) \end{aligned}$
tiene solución si y sólo si para cada par de índices $i$ y $j$ en ${1, 2, \dots, n}$ se tiene que la ecuación $i$ y la ecuación $j$ tienen solución, es decir, si y sólo si $MCD (m_{i}, m_{j}) ∣ b_{i} - b_{j}$ . En este caso, la solución es única módulo $mcd (m_{1}, \dots, m_{n})$ .

Demostración. Si el sistema completo tiene solución, entonces claramente cualquier par de ecuaciones tiene solución. Para demostrar la afirmación inversa, procederemos por inducción. Para $n = 2$ la afirmación es directa, pues justo la hipótesis es que ese par de ecuaciones tiene solución.

Supongamos entonces el resultado cierto para cuando tenemos $n$ ecuaciones y consideremos un sistema con $n + 1$ ecuaciones
$\begin{aligned} x & \equiv b_{1} (\mod m_{1}) \\ x & \equiv b_{2} (\mod m_{2}) \\ ⋮ \\ x & \equiv b_{n} (\mod m_{n}) \\ x & \equiv b_{n + 1} (\mod m_{n + 1}) . \end{aligned}$

Supongamos que cualquier par de ellas tienen solución. Tenemos que mostrar que todo el sistema tiene solución y que es única módulo $mcm (m_{1}, \dots, m_{n + 1})$ . Como cualquier par tienen solución, entonces cualquier par de las primeras $n$ tienen solución. Por hipótesis inductiva, entonces podemos reemplazar a las primeras ecuaciones por una ecuación módulo $N = mcm (m_{1}, \dots, m_{n})$ , que es única por la unicidad en la hipótesis inductiva. En otras palabras, existe un entero $c$ tal que el sistema de ecuaciones original es equivalente al sistema de ecuaciones
$\begin{aligned} x & \equiv c (\mod N) \\ x & \equiv b_{n + 1} (\mod m_{n + 1}) \end{aligned}$

Mostraremos ahora que este sistema tiene solución. Para esto, basta mostrar que $MCD (N, m_{n + 1})$ divide a $c - b_{n + 1}$ .

Como $c$ es solución del sistema para las primeras $n$ ecuaciones, tenemos que $c \equiv b_{i} (\mod m_{i})$ para toda $i = 1, \dots, n$ , es decir, $m_{i} ∣ c - b_{i}$ . Por transitividad, $MCD (m_{n + 1}, m_{i}) ∣ c - b_{i}$ .

Como cualquier par de ecuaciones de las originales tenía solución, tenemos que $MCD (m_{n + 1}, m_{i}) ∣ b_{i} - b_{n + 1}$ . De esta forma, $MCD (m_{n + 1}, m_{i}) ∣ - (c - b_{i}) - (b_{i} - b_{n + 1}) = b_{n + 1} - c .$

Con esto mostramos que cada $MCD (m_{n + 1}, m_{i})$ divide a $b_{n + 1} - c$ , de modo que el mínimo común múltiplo de estos números también divide a $b_{n + 1} - c$ . Pero el mínimo común múltiplo de estos números precisamente $MCD (N, m_{n + 1})$ .

En otras palabras, el sistema
$\begin{aligned} x & \equiv c (\mod N) \\ x & \equiv b_{n + 1} (\mod m_{n + 1}), \end{aligned}$

que es esquivalente al original, tiene una solución, y esta es única módulo $mcm (N, m_{n + 1}) = mcm (m_{1}, \dots, m_{n}, m_{n + 1}) .$

Esto es justo lo que queríamos para dar el paso inductivo.

Como corolario, obtenemos el teorema chino del residuo, que habla acerca de soluciones a sistemas de ecuaciones en los cuales los módulos que tomamos son primos relativos entre sí.

Teorema 4 (teorema chino del residuo). Sea $n \geq 2$ un entero, $b_{i}$ enteros para $i \in {1, 2, \dots, n}$ y $m_{i}$ enteros positivos para $i \in {1, \dots, n}$ . Supongamos además que cada par $m_{i}, m_{j}$ de enteros ( $i \neq j$ ) son primos relativos. Entonces el sistema lineal de congruencias
$\begin{aligned} x & \equiv b_{1} (\mod m_{1}) \\ x & \equiv b_{2} (\mod m_{2}) \\ ⋮ \\ x & \equiv b_{n} (\mod m_{n}) \end{aligned}$
tiene una y sólo una solución módulo $m_{1} m_{2} \dots m_{n}$ .

Demostración. Como cada pareja de módulos son primos relativos, tenemos que $MCD (m_{i}, m_{j}) = 1$ y entonces claramente cada par de ecuaciones tiene solución. Por el Teorema 3, el sistema tiene solución y esta es única módulo el mínimo común múltiplo de $m_{1}, \dots, m_{n}$ , que como son primos relativos dos a dos, es $m_{1} m_{2} \dots m_{n}$ .

La demostración del Teorema 3 también nos da un procedimiento para resolver de manera práctica los sistemas de ecuaciones lineales en congruencias:

Si los coeficientes de $x$ del sistema no son $1$ , entonces primero resolvemos todas las ecuaciones con coeficiente distinto de $1$ para transformarla en una del estilo de las del Teorema 3. Si alguna no se puede, entonces el sistema no tiene solución.
Una vez que el sistema está en la forma del Teorema 3, verificamos si cada par de ecuaciones tienen solución calculando los máximos comunes divisores de dos en dos y viendo que dividen a las restas respectivas. Si alguno de estos pares falla, entonces el sistema no tiene solución.
Si todos los pares cumplen la hipótesis, entonces resolvemos las primeras dos ecuaciones para remplazarlas por otra módulo su mínimo común múltiplo. Luego, usamos esa que obtuvimos y la tercera para remplazarlas por otra. Seguimos así hasta que sólo nos queden dos ecuaciones. La solución a esas será la solución al sistema original.

Ejemplo. Resolvamos el siguiente sistema de congruencias:

$\begin{aligned} x & \equiv 11 (\mod 5) \\ x & \equiv 5 (\mod 7) \\ x & \equiv 7 (\mod 11) \end{aligned}$

Solución. Los números $5$ , $7$ y $11$ son primos relativos por parejas, de modo que la solución existe y es única módulo $5 \cdot 7 \cdot 11 = 385$ . Para encontrarla, primero resolvemos las primeras dos ecuaciones. Estas corresponden al sistema
$\begin{aligned} x & \equiv 11 \equiv 1 (\mod 5) \\ x & \equiv 5 (\mod 7) \end{aligned}$

Para encontrar la solución, ponemos a $1 - 5 = - 4$ como combinación lineal de $5$ y $7$ , que tras explorar un poco, se puede hacer así: $1 - 5 = - 4 = 2 \cdot 5 + (- 2) \cdot 7$ . De este modo, la solución es $x \equiv 5 - 14 \equiv - 9 \equiv 26 (\mod 35)$ (este es un buen momento para substituir en las dos ecuaciones originales y ver que todo vaya bien).

Así, el sistema original es equivalente al sistema
$\begin{aligned} x & \equiv 26 (\mod 35) \\ x & \equiv 7 (\mod 11) \end{aligned}$

Ahora lo que tenemos que hacer es expresar a $26 - 7 = 19$ como combinación lineal de $35$ y $11$ . Es difícil encontrar una combinación «al tanteo», así que aquí es mejor usar el algoritmo de la división de Euclides:
$\begin{aligned} 35 & = 3 \cdot 11 + 2 \\ 11 & = 2 \cdot 5 + 1 \end{aligned}$

De aquí, $1 = 11 - 2 \cdot 5 = 11 - (35 - 3 \cdot 11) \cdot 5 = (- 5) \cdot 35 + 16 \cdot 11,$ por lo que $19 = (- 5 \cdot 19) \cdot 35 + (19 \cdot 16) \cdot 11 = (- 95) \cdot 35 + (304) \cdot 11.$

Así, la solución al sistema está dada por $x = 7 + 304 \cdot 11 = 3351 \equiv 271 (\mod 385)$ .

Más adelante…

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

Verifica que, en efecto, las soluciones que obtuvimos en el ejemplo después del Teorema 2 sí son soluciones de la ecuación original.
Cuando un sistema de dos ecuaciones en módulos $m$ y $n$ sí tiene solución, ¿cuántas soluciones módulo $m n$ tiene?
Usando $(\dots)$ para máximo común divisor y $[\dots]$ para mínimo común múltiplo, demuestra que para cualesquiera enteros $m_{1}, m_{2}, \dots, m_{n}$ se tiene que $([m_{1}, \dots, m_{n}], m_{n + 1}) = [(m_{1}, m_{n + 1}), \dots, (m_{n}, m_{n + 1})] .$
Verifica que las soluciones del último ejemplo en efecto satisfacen el sistema de ecuaciones inicial.
Demuestra que para cualquier entero $n \geq 1$ existen $n$ enteros consecutivos tal que la factorización en primos de cada uno de ellos usa al menos dos primos diferentes.

Entradas relacionadas

Ir a: Álgebra Superior II
Entrada anterior del curso: Ecuaciones en congruencias
Entrada siguiente del curso: Problemas de ecuaciones en congruencias y teorema chino del residuo

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»

Álgebra Superior II: Ejercicios de los teoremas de Fermat y de Wilson

Por Claudia Silva

3 respuestas

Introducción

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)

Más adelante…

Tarea moral

Entradas relacionadas

Ir a: Álgebra Superior II
Entrada anterior del curso: Teoremas de Fermat y de Wilson
Entrada siguiente del curso: Ecuaciones en congruencias

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»

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

Por Leonardo Ignacio Martínez Sandoval

3 respuestas

Introducción

En notas pasadas hemos platicado del algoritmo de la división, del máximo común divisor, del mínimo común múltiplo, de primos, del 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 (\mod n)$ .
Definir a $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 $Z_{n}$ que tienen inversos multiplicativos y cuándo $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 (\mod 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 (\mod 24)$ y $22 + 7 \equiv 5 (\mod 24)$ .
En «el mundo de las horas», si sumamos $24$ horas no pasa nada.

Definición del anillo $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 (\mod n) ⟺ n ∣ b - a .$

Proposición. Para todo entero positivo $n$ la relación en $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 $Z$ . Tenemos que $n$ divide a $0 = a - a$ , pues $n \cdot 0 = 0$ (dicho de otra forma, $0$ está en $n Z$ ). Así, $a \equiv a (\mod n)$ .

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

Finalmente, veamos que la relación es transitiva. Para ello, a partir de enteros $a$ , $b$ y $c$ tales que $a \equiv b (\mod n)$ y $b \equiv c (\mod n)$ tenemos que mostrar que $a \equiv c (\mod 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 ∣ (a - b) + (b - c) = a - c$ , que por definición quiere decir que $a \equiv c (\mod n)$ .

Ya que «ser congruente módulo $n$ » es una relación de equivalencia, entonces podemos dividir a todo $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 (\mod n)$ si y sólo si $a$ y $b$ dejan el mismo residuo al dividirse entre $n$ en el algoritmo de la división. En particular, para cada $a$ siempre existe un entero $r$ en ${0, 1, \dots, n - 1}$ tal que $a \equiv r (\mod n)$ .

Demostración. Usemos el algoritmo de la división para escribir $a = q n + r$ y $b = p n + 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, \dots, n - 1}$ .

Si $r = s$ , entonces $a - b = (q - p) n$ , así que $n ∣ a - b$ y así $a \equiv b (\mod n)$ . Si $a \equiv b (\mod n)$ , entonces $n ∣ a - b = (q - p) n + (r - s) .$ Como $n ∣ (q - p) n$ , entonces $n ∣ r - s$ . Sin embargo, usando que $r$ y $s$ están en ${0, 1, \dots, 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 (\mod n)$ .

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}, \dots, [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 $Z_{n}$ no es lo mismo que el ideal $n Z$ , y que hay que ser cuidadosos con la notación. De hecho, el ideal $n Z$ es uno de los elementos de $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, $[\dots, - 5, - 1, 3, 7, \dots]$ .

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} = [a b]_{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^{'} (\mod n)$ y $b \equiv b^{'} (\mod n)$ , entonces $a + b \equiv a^{'} + b^{'} (\mod n)$ y $a b \equiv a^{'} b^{'} (\mod n)$ .

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

Para el producto, de $n ∣ a - a^{'}$ podemos obtener $n ∣ (a - a^{'}) b = a b - a^{'} b$ y de $n ∣ b - b^{'}$ podemos obtener $n ∣ a^{'} (b - b^{'}) = a^{'} b - a^{'} b^{'} .$ Así, $n ∣ (a b - a^{'} b) + (a^{'} b - a^{'} b^{'}) = a b - a^{'} b^{'} .$ De aqui, $a b \equiv a^{'} b^{'} (\mod n)$ , la otra congruencia que queríamos.

El anillo de enteros módulo $n$ es precisamente $Z_{n}$ equipado con las operaciones de suma y producto que acabamos de definir.

Ejemplos de operaciones en $Z_{n}$

Estos son algunos ejemplos básicos de operaciones en $Z_{7}$ y en $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 $Z_{n}$ .

Inversos multiplicativos en $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} + [k n]_{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 $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} = [4 a]_{12}$ y por lo tanto que $4 a \equiv 1 (\mod 12)$ , es decir, que $12 ∣ 4 a - 1$ . Como $4 ∣ 12$ y $4 ∣ 4 a$ , tendríamos entonces que $4 ∣ (4 a - 1) - 4 a = - 1$ . Esto es una contradicción.

La siguiente proposición dice exactamente quienes son los elementos en $Z_{n}$ que tienen inversos multiplicativos en $Z_{n}$ .

Teorema. Sea $n$ un entero positivo. La clase $[a]_{n}$ de $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 $M C D (a, n)$ es igual a $1$ . Recordemos también que $M C D (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 = a p + n q$ . Así, $[a p]_{n} = [a p + n q]_{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.

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 $Z_{n}$ es un campo.

Proposición. Sea $n$ un entero. El conjunto $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}, \dots, [n - 1]_{n}$ . Por la proposición anterior, estos tienen inversos si y sólo si cada uno de los números $1, 2, \dots, 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, $Z_{n}$ es un campo si y sólo si $n$ es primo.

Más adelante…

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 Z$ es uno de los elementos de $Z_{n}$ .
Muestra que las operaciones de suma y producto en $Z_{n}$ en efecto satisfacen la definición de anillo conmutativo. Sugerencia: aprovecha que $Z$ es un anillo conmutativo con sus operaciones de suma y producto.
Muestra que $[1]_{n}$ es identidad para el producto en $Z_{n}$ .
Completa la prueba del teorema de inversos multiplicativos.

Entradas relacionadas

Ir a: Álgebra Superior II
Entrada anterior del curso: Problemas de divisibilidad y algoritmo de Euclides
Entrada siguiente del curso: Problemas de congruencias y $Z_{n}$

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»

El blog de Leo

Aprendiendo, creando y compartiendo matemáticas

Archivo de la etiqueta: teoría de números

Álgebra Superior II: Teorema chino del residuo

Introducción

Sistemas de dos ecuaciones lineales

El teorema chino del residuo

Más adelante…

Tarea moral

Entradas relacionadas

Agradecimientos

Álgebra Superior II: Ejercicios de los teoremas de Fermat y de Wilson

Introducción

Más adelante…

Tarea moral

Entradas relacionadas

Agradecimientos

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

Introducción

Ejemplo introductorio

Definición del anillo $Z_{n}$

Ejemplos de operaciones en $Z_{n}$

Inversos multiplicativos en $Z_{n}$

Más adelante…

Tarea moral

Entradas relacionadas

Agradecimientos

Introducción

Sistemas de dos ecuaciones lineales

El teorema chino del residuo

Más adelante…

Tarea moral

Entradas relacionadas

Agradecimientos

Introducción

Más adelante…

Tarea moral

Entradas relacionadas

Agradecimientos

Introducción

Ejemplo introductorio

Definición del anillo Zn

Ejemplos de operaciones en Zn

Inversos multiplicativos en Zn

Más adelante…

Tarea moral

Entradas relacionadas

Agradecimientos

Definición del anillo $Z_{n}$

Ejemplos de operaciones en $Z_{n}$

Inversos multiplicativos en $Z_{n}$