Congruencias y propiedades básicas#

Introducción#

En el capítulo del recordatorio de clases de equivalencia vimos en el Ejemplo 75 una relación que se cumple sobre el conjunto de los números enteros. En este capítulo la llamaremos la relación de congruencia. Y será definida con un símbolo inventado por el matemático Carl Friedrich Gauss. Además, veremos las propiedades fundamentales y ejemplos de dicha relación. El lenguaje de las congruencias hace posible trabajar con relaciones de divisibilidad de manera similar a como trabajamos con igualdades.

Definición de congruencias módulo m#

Definición 35 (Definición congruencias módulo \(m\))

Sea \(m\) un entero positivo. Decimos que un entero \(a\) es congruente con un entero \(b\) módulo \(m\) si \(m|(a-b)\).
Generalmente se usa el símbolo \(\equiv\) para denotar la congruencia entre dos números enteros.
Usaremos la siguiente notación \(a \equiv b \pmod{m}\) para decir que \(a\) es congruente con \(b\) módulo \(m\).
Y usaremos la notación \(a \not\equiv b \pmod{m}\) para decir que \(a\) no es congruente con \(b\) módulo \(m\).

Ejemplo 90

Ejemplos de números que son congruentes en ciertos módulos.

  • Ya que \(4|(25-1)\), entonces \(25 \equiv 1 \pmod{4}\).

  • Ya que \(6|(38-2)\), entonces \(38 \equiv 2 \pmod{6}\).

  • Ya que \(9|(76-4)\), entonces \(76 \equiv 4 \pmod{9}\).

Ejemplos de números que no son congruentes en ciertos módulos.

  • \(72 \not\equiv 4 \pmod{9}\), ya que \(9 \nmid (72-4)\).

  • \(36 \not\equiv 2 \pmod{6}\), ya que \(6 \nmid (36-2)\).

  • \(24 \not\equiv 1 \pmod{4}\), ya que \(4 \nmid (24-1)\).

Vamos a ver que la relación definida anteriormente en el Ejemplo 75 es equivalente a la Definición 35 en el siguiente teorema.

Teorema 27

\(a \equiv b \pmod{m}\) si y solo si \(a\) y \(b\) dejan el mismo residuo cuando son divididos entre \(m\).

Demostración. Notemos que la Definición 35 de congruencia, es equivalente a la relación del Ejemplo 75. Esto ya lo demostramos en la Proposición 24.

Ejemplo 91

Veamos algunos ejemplos que cumplen con el teorema anterior.

  • Como \(9 = 4\cdot 2 + 1\) y \(25 = 4\cdot 6 + 1\), entonces \(9 \equiv 25 \pmod{4}\).

  • Como \(8 = 5\cdot 1 + 3\) y \(43 = 5\cdot 8 + 3\), entonces \(8 \equiv 43 \pmod{5}\).

  • Como \(11 = 7\cdot 1 + 4\) y \(25 = 7\cdot 3 + 4\), entonces \(11 \equiv 25 \pmod{7}\).

Veamos que podemos expresar las congruencias con otra caracterización, la cual es la misma que la relación del Ejemplo 75

Teorema 28

\(a \equiv b \pmod{m}\) si y sólo si \(a = b + km\) para algún entero \(k\).

Demostración. Tenemos que demostrar las dos implicaciones.

  • Supongamos que \(a \equiv b \pmod{m}\).

Por hipótesis tenemos que \(m|(a-b)\), entonces \(a-b = km\) para algún entero \(k\). Por lo tanto tenemos que \(a = b + km\).

  • Ahora supongamos que \(a = b + km\) para algún entero \(k\).

Entonces tenemos que \(a-b = km\). lo cual quiere decir que \(m|(a-b)\), y por lo tanto por definición tenemos que \(a \equiv b \pmod{m}\). \(\square\)

Ejemplo 92

Veamos algunos ejemplos del teorema anterior.

  • Si tenemos que \(23 \equiv 3 \pmod{5}\), entonces \(23 = 3 + 4\cdot 5\).

  • Si tenemos que \(17 \equiv 5 \pmod{6}\), entonces \(17 = 5 + 2\cdot 6\).

  • Pero también podríamos tener que \(49 = -5 + 9\cdot 6\), es decir que \(49 \equiv -5 \pmod{6}\).

Propiedades de congruencias#

Lo primero que vamos a ver, es que la relación de congruencia es una relación de equivalencia. En otras palabras, cumple con las \(3\) propiedades de la Definición 28.

Teorema 29

La relación de congruencia cumple con las siguientes \(3\) propiedades.

  1. Es reflexiva, es decir que \(a \equiv a \pmod{m}\).

  2. Es simétrica, es decir que si \(a\equiv b \pmod{m}\), entonces \(b \equiv a \pmod{m}\).

  3. Es transitiva, es decir que si \(a\equiv b \pmod{m}\) y \(b\equiv c \pmod{m}\), entonces \(a\equiv c \pmod{m}\).

Demostración. La demostración de estas \(3\) propiedades ya las vimos en el Ejemplo 75.

Por lo tanto, con lo anterior ya tenemos que la relación de congruencia es una relación de equivalencia.

Como vimos en la Definición 30 de clases de equivalencia, ahora también podemos hablar de clases de congruencias módulo \(m\).

Definición 36 (Clases de congruencias módulo \(m\))

Dado que \(\equiv\) es una relación de equivalencia en el conjunto \(\mathbb{Z}\), al conjunto de elementos de \(\mathbb{Z}\) que son congruentes con \(a\) módulo \(m\) le llamamos la clase de congruencia de \(a\) módulo \(m\) y la denotamos por \([a]_m\). En otras palabras,

\[[a]_m = \{ b \in \mathbb{Z} \mid b \equiv a \pmod{m} \}.\]

Ejemplo 93

Si \(m\) es un entero positivo, tendríamos \(m\) diferentes clases de congruencias, ya que cada clase correspondería a uno de los \(m\) posibles residuos \(r = 0,1,2, \ldots , m-1\) cuando un entero \(a \in \mathbb{Z}\) es dividido por \(m\). En general tendríamos las siguientes diferentes clases.

\[\begin{align*} [0]_m &= \{ \ldots, -3m, -2m, -m, 0, m, 2m, 3m, \ldots \}, \\ & \\ [1]_m &= \{ \ldots, -3m + 1, -2m + 1, -m + 1, 1, m + 1, 2m + 1, 3m + 1, \ldots \}, \\ & \\ [2]_m &= \{ \ldots, -3m + 2, -2m + 2, -m + 2, 2, m + 2, 2m + 2, 3m + 2, \ldots \}, \\ \vdots \\ [m-1]_m &= \{ \ldots, -3m - 1,-2m -1 , -m - 1, -1, , m - 1, 2m -1, 3m - 1, \ldots \}. \\ \end{align*}\]

Por ejemplo si tomáramos \(m = 2\) tendríamos las siguientes dos clases de congruencias.

\[\begin{align*} [0]_2 &= \{ \ldots, -6, -4, -2, 0, 2, 4,6, \ldots \}, \\ & \\ [1]_2 &= \{ \ldots, -5, -3, -1, 1, 3, 5, \ldots \}. \\ \end{align*}\]

Como vimos en el Teorema 28, si tenemos que \(a \equiv r \pmod{m}\) podemos decir que \(a = r + mq\). Esto nos lleva a introducir la siguiente definición.

Definición 37 (Menor residuo no negativo modulo \(m\))

Si \(a \equiv r \pmod{m}\) y se cumple que \(0 \le r < m\) diremos que \(r\) es el menor residuo no negativo de \(a\) módulo \(m\).

Corolario 8

El entero \(r\) es el residuo cuando \(a\) es dividido por \(m\) si y sólo si \(a \equiv r \pmod{m}\), donde \(0 \le r < m\).

Demostración. Demostremos las dos implicaciones.

  • Supongamos que \(r\) es el residuo cuando \(a\) es dividido por \(m\).

Veamos que gracias al Teorema 3 tenemos que existe \(q\) tal que \(a = mq + r\) y además \( 0 \le r < m\). De lo anterior obtenemos que \(a - r = mq\), y por lo tanto podemos concluir que \(a \equiv r \pmod{m}\).

  • Ahora supongamos que se cumple que \(a \equiv r \pmod{m}\), donde \(0 \le r < m\).

Como \(a \equiv r \pmod{m}\) por definición tenemos que \(m|(a-r)\), es decir que existe un entero \(q\) tal que \(a - r =qm\), si despejamos \(a\) de la ecuación obtenemos que \(a = mq + r\), esto quiere decir que cuando \(a\) es dividido por \(m\) el residuo es \(r\), donde \(0\le r < m\). \(\square\)

Observación 14

El menor residuo no negativo es el que nos será de mucha ayuda en la siguiente sección ya que nos ayuda a simplificar los números respecto a su módulo, por ejemplo,

\[\begin{align*} 34 &\equiv 1 \pmod{3}, \\ & \\ 23 &\equiv 3 \pmod{4}, \\ & \\ 58 &\equiv 7 \pmod{17}. \end{align*}\]

Operaciones en congruencias#

Dado que ya dimos la Definición 36 de clases de congruencias, lo que nos gustaría ahora es proporcionar algunas operaciones básicas entre las clases de congruencias.

Definición 38

Sea \(m\) un entero positivo. Si tomamos dos clases de congruencias cualesquiera módulo \(m\), definimos las operaciones sumas, diferencia y producto como sigue:

\[\begin{align*} [a]_m + [b]_m &= [a + b]_m, \\ & \\ [a]_m - [b]_m &= [a - b]_m, \\ & \\ [a]_m [b]_m &= [ab]_m. \end{align*}\]

Ejemplo 94

Supongamos que \(m = 7\), entonces tendríamos las siguientes clases \([0]_7, [1]_7, [2]_7, [3]_7, [4]_7, [5]_7, [6]_7\).

Si sumamos las siguientes clases tendremos que

\[[4]_7 + [6]_7 = [4 + 6]_7 = [10]_7 = [3]_7,\]
es decir que si tomamos cualquier representante de la clase \([4]_7\) y otro cualquiera de la clase \([6]_7\) el resultado será un representante de la clase \([3]_7\).

Tomemos por ejemplo lo siguientes representantes \([4]_7 = [18]_7\) y \([6]_7 = [20]_7\), entonces tendríamos lo siguiente

\[[4]_7 + [6]_7 = [18]_7 + [20]_7 = [18 + 20]_7 = [38]_7 = [3]_7.\]

Esto es cierto ya que \(38 = 7\cdot 5 + 3\).

Lo que nos gustaría probar es que estas tres operaciones están bien definidas, en el sentido de que el lado derecho de las tres igualdades definidas depende solamente de las clases \([a]_m\) y \([b]_m\) y no de los elementos \(a\) y \(b\) seleccionados de esas clases. Para ello vamos a ver que si \([a]_m = [a']_m\) y \([b]_m = [b']_m\), entonces \([a + b]_m = [a' + b']_m\), \([a - b]_m = [a' - b']_m\) y \([ab]_m = [a'b']_m\).

Lema 9

Dado \(m\) un entero positivo, si \([a]_m = [a']_m\) y \([b]_m = [b']_m\), entonces \([a + b]_m = [a' + b']_m\), \([a - b]_m = [a' - b']_m\) y \([ab]_m = [a'b']_m\).

Demostración. Notemos lo siguiente. Como \([a] = [a']\) y \([b] = [b']\) tenemos que \(a \equiv a' \pmod{m}\) y \(b \equiv b' \pmod{m}\), entonces debemos demostrar que \(a + b \equiv a' + b' \pmod{m}\), \(a - b \equiv a' - b' \pmod{m}\) y \(ab \equiv a'b' \pmod{m}\).

  • \([a + b]_m = [a' + b']_m\).

Si \(a \equiv a' \pmod{m}\) y \(b \equiv b' \pmod{m}\) entonces por el Teorema 28 se tiene que \(a = a' + km\) y \(b = b' + lm\) para algunos enteros \(k\) y \(l\). Luego, podemos sumar ambas ecuaciones y obtenemos que

\[a + b = a' + km + b' + lm = a' + b' + (k + l)m.\]

Por lo tanto, podemos concluir que \(a + b \equiv a' + b' \pmod{m}\) y, así, se cumple que \([a + b]_m = [a' + b']_m\).

  • \([a - b]_m = [a' - b']_m\).

Similarmente tenemos que \(a \equiv a' \pmod{m}\) y \(b \equiv b' \pmod{m}\). Entonces por el Teorema 28 se tiene que \(a = a' + km\) y \(b = b' + lm\) para algunos enteros \(k\) y \(l\). Luego podemos restar ambas ecuaciones y obtenemos que

\[a - b = a' + km - b' - lm = a' - b' + (k - l)m.\]

Por lo tanto, podemos concluir que \(a - b \equiv a' - b' \pmod{m}\) y, así, se cumple que \([a - b]_m = [a' - b']_m\).

  • \([ab]_m = [a'b']_m\).

Finalmente, tenemos que \(a \equiv a' \pmod{m}\) y \(b \equiv b' \pmod{m}\) entonces por el Teorema 28 se tiene que \(a = a' + km\) y \(b = b' + lm\) para algunos enteros \(k\) y \(l\). Luego podemos multiplicar ambas ecuaciones y obtenemos que

\[\begin{align*} ab &= (a' + km) (b' + lm) \\ & \\ &= a'b' + a'lm + b'km + klm^2 \\ & \\ &= a'b' + (a'l + b'k + klm)m. \end{align*}\]

Por lo tanto, podemos concluir que \(ab \equiv a'b' \pmod{m}\) y, así, se cumple que \([ab]_m = [a'b']_m\). \(\square\)

Trabajar la notación de clases de congruencias es algo complicado. Es por eso que vamos a definir las operaciones para el símbolo \(\equiv\) de congruencias.

Primero veremos que al igual que en una ecuación común podemos sumar, restar o multiplicar ambos lados de ésta preservando la congruencia.

Teorema 30

Si \(a,b,c\) y \(m\) son enteros, en donde \(m > 0\), tal que \(a \equiv b \pmod{m}\), entonces se cumple lo siguiente

  1. \(a+c \equiv b+c \pmod{m}\),

  2. \(a-c \equiv b-c \pmod{m}\),

  3. \(ac \equiv bc \pmod{m}\).

Demostración. Por hipótesis tenemos que \(a \equiv b \pmod{m}\), esto quiere decir que \(a = b + km\) para algún entero \(k\). Utilizaremos esta ecuación para las \(3\) demostraciones.

  • Demostración de \(1\).

Sumando c en ambos lados de la ecuación \(a = b + km\) , obtenemos que \((a+c) = (b+c) + km\). Esto quiere decir que \(a+c \equiv b+c \pmod{m}\). \(\square\)

  • Demostración de \(2\).

En este caso vamos a restar \(c\) a ambos lados de la ecuación \(a = b + km\), teniendo que \((a-c) = (b-c) + km\). Esto quiere decir que \(a-c \equiv b-c \pmod{m}\). \(\square\)

  • Demostración de \(3\).

Ahora, vamos a multiplicar por \(c\) ambos lados de la ecuación \(a = b + km\), teniendo que \(ac = bc + kmc\). Esto quiere decir que \(ac - bc = kcm\) con \(kc\) un entero, lo cual significa que \(m|(ac-bc)\) y por lo tanto se cumple que \(ac \equiv bc \pmod{m}\). \(\square\)

Veamos que las congruencias pueden dividirse por ambos lados siempre y cuando se cumplan algunas condiciones extra.

Teorema 31

Si \(a,b,c\) y \(m\) son enteros tales que \(m > 0\), \((c,m) = d\) y \(ac \equiv bc \pmod{m}\), entonces \(a \equiv b \pmod{ \frac{m}{d}}\).

Demostración. Como \(ac \equiv bc \pmod{m}\), sabemos que \(m|(ac - bc) = c(a-b)\). Por definición existe un entero \(q\) para el cual se cumple que \(c(a-b) = qm\). Luego, si dividimos ambos lados entre \(d\) tendríamos que

\[ \frac{c}{d} (a-b) = q \frac{m}{d}.\]
Por la propiedad \(1\) de la Proposición 8 tenemos que \((\frac{c}{d}, \frac{m}{d}) = 1\), es decir que \(\frac{c}{d}\) y \(\frac{m}{d}\) son primos relativos. Entonces sucede que \(\frac{m}{d}|(a - b)\) y por lo tanto \(a \equiv b \pmod{\frac{m}{d}}\). \(\square\)

Veamos un caso particular del Teorema 31.

Corolario 9

Si \(a,b,c\) y \(m\) son enteros tales que \(m > 0\), \((c,m) = 1\) y \(ac \equiv bc \pmod{m}\), entonces \(a \equiv b \pmod{m}\).

Demostración. Por hipótesis sabemos que \(ac \equiv bc \pmod{m}\), en donde \((c,m) = 1\). Entonces por definición tenemos que \(m|(ac - bc) = c(a-b)\). Pero como \((c,m) = 1\), por el Corolario 2 sucede que \(m|(a-b)\) y por lo tanto \(a \equiv b \pmod{m}\). \(\square\)

Ahora veamos que podemos sumar, restar o multiplicar congruencias entre sí, siempre y cuando el módulo de estas sea el mismo.

Teorema 32

Si \(a,b,c,d\) y \(m\) son enteros tales que \(m > 0\), \(a \equiv b \pmod{m}\) y \(c \equiv d \pmod{m}\), entonces

  1. \(a+c \equiv b+d \pmod{m}\),

  2. \(a-c \equiv b-d \pmod{m}\),

  3. \(ac \equiv bd \pmod{m}\).

Demostración. Ya que \(a \equiv b \pmod{m}\) y \(c \equiv d \pmod{m}\), sabemos que \(m|(a-b)\) y \(m|(c-d)\), en otras palabras existen enteros \(r\) y \(s\) tales que \(rm = a-b\) y \(sm = c-d\).

  • Demostración \(1\).

Notemos que, si sumamos las ecuaciones \(rm = a-b\) y \(sm = c-d\) obtenemos lo siguiente

\[(r + s)m = rm + sm = (a - b) + (c - d) = (a + c) - (b + d),\]

lo cual quiere decir que \(m|[(a + c) - (b + d)]\) y por lo tanto \(a+c \equiv b+d \pmod{m}\). \(\square\)

  • Demostración de \(2\).

De manera análoga, si restamos las ecuaciones \(rm = a-b\) y \(sm = c-d\) obtenemos

\[(r - s)m = rm - sm = (a - b) - (c - d) = (a - c) - (b - d),\]
lo cual quiere decir que \(m|[(a - c) - (b - d)]\) y por lo tanto \(a-c \equiv b-d \pmod{m}\). \(\square\)

  • Demostración de \(3\).

Vamos a ver si la expresión \(ac - bd\) es dividida por \(m\), entonces tenemos lo siguiente

\[ac - bd = ac - bc + bc - bd = c(a - b) + b(c - d) = crm + bsm = (cr + bs)m,\]
lo cual quiere decir que \(m|ac - bd\) y por lo tanto \(ac \equiv bd \pmod{m}\). \(\square\)

Ejemplo 95

Aplica las operaciones de suma, resta y multiplicación a las siguientes congruencias, \(21 \equiv -4 \pmod{5}\) y \(16 \equiv 1 \pmod{5}\).

Solución.

  • Si sumamos las congruencias obtenemos,

\[\begin{align*} 21 + 16 &\equiv -4 + 1 \pmod{5} \\ & \\ 37 &\equiv -3 \pmod{5}. \end{align*}\]

  • Si restamos las congruencias obtenemos,

\[\begin{align*} 21 - 16 &\equiv -4 - 1 \pmod{5} \\ & \\ 5 &\equiv -5 \pmod{5}. \end{align*}\]

  • Si multiplicamos las congruencias obtenemos,

\[\begin{align*} 21\cdot 16 &\equiv (-4)\cdot 1 \pmod{5} \\ & \\ 336 &\equiv -4 \pmod{5}. \end{align*}\]

Por último veamos cómo se comportan las congruencias con las potencias.

Teorema 33

Si \(a,b,k\) y \(m\) son enteros tales que \(k>0 , m>0\) y \(a \equiv b \pmod{m}\), entonces \(a^k \equiv b^k \pmod{m}\).

Demostración. Vamos a proceder por inducción.
Sea \(P(n)\) la proposición que afirma que para el entero positivo \(n\) se cumple que, si \(a,b\) y \(m\) son enteros tales que \(m>0\) y \(a \equiv b\pmod{m}\), entonces \(a^n \equiv b^n\pmod{m}\).

Base inductiva. Para \(n = 1\), tendremos que

\[\begin{align*} a^n &\equiv b^n \pmod{m} \\ & \\ a^1 &\equiv b^1 \pmod{m} \\ & \\ a &\equiv b \pmod{m}. \\ \end{align*}\]

Por lo tanto, \(P(1)\) es verdadera.

Hipótesis inductiva. Supongamos \(P(k)\) es verdadera para algún entero positivo \(k\), es decir que si \(a,b,k\) y \(m\) son enteros tales que \(k>0 , m>0\) y \(a \equiv b\pmod{m}\), entonces \(a^k \equiv b^k\pmod{m}\).

Paso inductivo. Vamos a demostrar que \(P(k)\) implica \(P(k+1)\).

Por hipótesis tenemos que, \(a \equiv b \pmod{m}\) y por la hipótesis inductiva tenemos que, \(a^k \equiv b^k\pmod{m}\). Por el inciso \(3\) del Teorema 32, podemos multiplicar las congruencias anteriores obteniendo que,

\[\begin{align*} aa^k &\equiv bb^k\pmod{m} \\ & \\ a^{k+1} &\equiv b^{k+1}\pmod{m}. \end{align*}\]

Entonces si \(P(k)\) es verdadera \(P(k+1)\) también lo es. Por lo tanto, por el principio de inducción \(P(n)\) es verdadera para todo entero \(n>0\). \(\square\)

Ejemplo 96

Encuentra el residuo cuando \(22^{47}\) es dividido por \(5\).

Solución.

Primero vamos a reducir la base a su residuo mínimo módulo \(5\), es decir usaremos que \(22 \equiv 2 \pmod{5}\). Entonces por el Teorema 33 tendríamos que \(22^{47} \equiv 2^{47} \pmod{5}\).

Ahora nos fijamos en lo siguiente,

\[\begin{align*} 2^1 \equiv 2 \pmod{5}, \\ & \\ 2^2 \equiv 4 \pmod{5}, \\ & \\ 2^3 \equiv 3 \pmod{5}, \\ & \\ 2^4 \equiv 1 \pmod{5}. \\ \end{align*}\]

Ahora, notemos lo siguiente,

\[\begin{align*} 2^{47} &= 2^{4\cdot 11 + 3} \\ & \\ &= (2^{4 \cdot 11}) \cdot 2^3 \\ & \\ &= (2^4)^{11} \cdot 2^3 \\ & \\ &\equiv (1)^{11} \cdot 3 \pmod{5} \\ & \\ &\equiv 3 \pmod{5}. \end{align*}\]

Entonces tenemos que \(2^{47} \equiv 3 \pmod{5}\).

Por lo tanto \(22^{47} \equiv 3 \pmod{5}\) lo cual quiere decir que el residuo al dividir \(22^{47}\) entre \(5\) es \(3\).

Ejemplo 97

Para ilustrar las congruencias con un ejemplo de la vida cotidiana, pensemos en los días de la semana. Son \(7\) días de la semana. Podríamos representarlos mediante congruencias. Supongamos que cada día de la semana tiene su numeración, es decir

\[\begin{align*} \text{Lunes} = 0, \\ & \\ \text{Martes} = 1, \\ & \\ \text{Miércoles} = 2, \\ & \\ \text{Jueves} = 3, \\ & \\ \text{Viernes} = 4, \\ & \\ \text{Sábado} = 5, \\ & \\ \text{Domingo} = 6. \\ \end{align*}\]

En este caso, estaríamos trabajando con congruencias módulo \(7\).
Supongamos que hoy es \(\text{Martes}\) que le toca el número \(1\), y queremos saber lo siguiente:

  • ¿Qué día será dentro de \(17\) días?

Tendríamos que hacer la operación \(1 + 17 = 18 \equiv 4 \pmod{7}\). Es decir que dentro de \(17\) días será \(\text{Viernes}\).

  • ¿Qué día fue hace \(17\) días?

Tendríamos que hacer la operación \(1 - 17 = -16 \equiv 5 \pmod{7}\). Es decir que hace \(17\) días fue \(\text{Sábado}\).

Inversos para el producto en congruencias#

Como consecuencia de la Definición 36 podemos construir el conjunto \(\mathbb{Z}_m\), el cual contiene todas las clases de congruencias módulo \(m\), es decir

\[\mathbb{Z}_m = \{[0]_m,[1]_m,[2]_m,[3]_m, \ldots , [m-1]_m \}.\]

En la Definición 38 dotamos a este conjunto de las operaciones de suma y producto, y además cuenta con un elemento neutro aditivo que sería \([0]_n\) y un elemento neutro multiplicativo que sería \([1]_n\).

Para terminar esta sección lo que nos va a interesar y será útil mas adelante, es notar que este conjunto algunos números tienen inverso multiplicativo. Lo que vamos a ver en esta sección es, bajo que condiciones se cumple que para el entero \(a\in \mathbb{Z}_m\) con \(m > 0\), existe \(b\in \mathbb{Z}_m\) tal que \(ab \equiv 1 \pmod{m}\).

Definición 39 (Inverso)

Se dice que \(a \in \mathbb{Z}_m\) es invertible si existe un \(b \in \mathbb{Z}_m\) llamado inverso tal que se cumple lo siguiente \(ab \equiv 1 \pmod{m}\).
El inverso de \(a\) puede ser denotado como \(a^{-1}\), y tendríamos la expresión \(aa^{-1} \equiv 1 \pmod{m}\).

Definición 40 (Inverso de sí mismo)

Decimos que \(a \in \mathbb{Z}_m\) es inverso de sí mismo si se cumple que \(a^2 \equiv 1 \pmod{m}\), es decir que \(a^{-1} = a\).

Ejemplo 98

Veamos algunos ejemplos, para averiguar si podemos encontrar el inverso.

  • Si tenemos \(\mathbb{Z}_6 = \{ [0]_6,[1]_6,[2]_6,[3]_6, [4]_6,[5]_6 \}\). ¿El número \(4\) y \(5\) tendrán inverso multiplicativo en \(\mathbb{Z}_6\)?

Veamos todos los posibles casos.

\[\begin{align*} 4 \cdot 0 = 0 \equiv 0 \pmod{6}, \\ & \\ 4 \cdot 1 = 4 \equiv 4 \pmod{6}, \\ & \\ 4 \cdot 2 = 8 \equiv 2 \pmod{6}, \\ & \\ 4 \cdot 3 = 12 \equiv 0 \pmod{6}, \\ & \\ 4 \cdot 4 = 16 \equiv 4 \pmod{6}, \\ & \\ 4 \cdot 5 = 20 \equiv 2 \pmod{6}. \\ \end{align*}\]

Notemos que sólo hace falta multiplicar residuos mínimos de cada clase de congruencia para verificar si alguno es inverso de \(4\). Podemos notar que en \(\mathbb{Z}_6\) el número \(4\) no tiene inverso multiplicativo.

Ahora, comprobemos si el número \(5\) tiene inverso multiplicativo en \(\mathbb{Z}_6\).

\[\begin{align*} 5 \cdot 0 = 0 \equiv 0 \pmod{6}, \\ & \\ 5 \cdot 1 = 5 \equiv 5 \pmod{6}, \\ & \\ 5 \cdot 2 = 10 \equiv 4 \pmod{6}, \\ & \\ 5 \cdot 3 = 15 \equiv 3 \pmod{6}, \\ & \\ 5 \cdot 4 = 20 \equiv 2 \pmod{6}, \\ & \\ 5 \cdot 5 = 25 \equiv 1 \pmod{6}. \\ \end{align*}\]

En este caso podemos observar que el inverso multiplicativo de \(5\) es \(5\).

Teorema 34

Sean \(a\) y \(m\) enteros. Se tiene que \(a\) tiene inverso multiplicativo módulo \(m\) si y sólo si \(a\) y \(m\) son primos relativos.

Demostración. Vamos a demostrar las dos implicaciones.

  • Supongamos que \(a\) tiene inverso multiplicativo módulo \(m\).

Es decir, tenemos por hipótesis que para algún entero \(b\) se tiene que, \(ab \equiv 1 \pmod{m}\), es decir que \(m|(ab - 1)\). Luego podemos reescribir lo anterior como \(ab - 1 = mk\) para algún entero \(k\). Con esto llegamos a que \(ab + (-k)m = 1\), en donde \(b\) y \(-k\) son enteros. Luego por el Teorema 8 podemos concluir que \(a\) y \(m\) son primos relativos.

  • Ahora supongamos que \(a\) y \(m\) son primos relativos.

Por la Definición 9, sabemos que \((a,m) = 1\). Luego, por el Teorema 8 tenemos que existen \(\alpha\) y \(\beta\) enteros tales que \(a \alpha + m \beta = 1\), reacomodando la ecuación tenemos que \((a \alpha - 1) = (-\beta)m\). Con lo anterior podemos concluir que \(m|(a\alpha - 1)\). Por lo tanto, \(a\alpha \equiv 1 \pmod{m}\). \(\square\)

Código para calcular el inverso multiplicativo módulo \(m\)#

Vamos a crear una función que calcule el inverso de un entero \(a\) módulo \(m\). La idea detrás del código está en el Teorema 34.
Para que un entero \(a\) tenga inverso módulo \(m\), necesitamos que \((a,m) = 1\). Luego, podemos expresar al máximo común divisor como una combinación lineal \(a\alpha + m\beta = 1\), lo cual nos llevó a concluir que \(a\alpha \equiv 1 \pmod{m}\). En otras palabras, si calculamos la combinación lineal el inverso del entero \(a\) será el valor de \(\alpha\).

Vamos a utilizar el código creado en la sección del algoritmo extendido de Euclides. Con este código obtenemos los coeficientes \(\alpha, \beta\) y \(d = (a,m)\) de la combinación lineal \(a\alpha + m\beta = d\).

def euclides_extendido_ciclos(a,b):
    s=[1,0]
    t=[0,1]
    while b!=0:
        q=a//b
        r=a%b
        nuevo_s=s[-2]-q*s[-1]
        nuevo_t=t[-2]-q*t[-1]
        s.append(nuevo_s)
        t.append(nuevo_t)
        a,b=b,r
    return s[-2],t[-2],a

El siguiente código nos dirá el inverso multiplicativo de un entero \(a\) módulo \(m\).

def inverso_modn(a,m):  
    alfa,beta,d = euclides_extendido_ciclos(a,m)    
    if d == 1:
        print(f"El inverso de {a} es {alfa}, es decir que, {a}x{alfa} ≡ 1 (mod{m})")
    else:  
        print(f"({a},{m}) es diferente de 1, entonces {a} no tiene inverso módulo {m}")

inverso_modn(182,311)

El inverso de 182 es 135, es decir que, 182x135 ≡ 1 (mod311)

inverso_modn(17,21)

El inverso de 17 es 5, es decir que, 17x5 ≡ 1 (mod21)

inverso_modn(8,16)

(8,16) es diferente de 1, entonces 8 no tiene inverso módulo 16

inverso_modn(21,7)

(21,7) es diferente de 1, entonces 21 no tiene inverso módulo 7

Explicación del código#

Veamos cómo funciona el código creado en esta sección.

def inverso_modn(a,m):  
    alfa,beta,d = euclides_extendido_ciclos(a,m)    
    if d == 1:
        print(f"El inverso de {a} es {alfa}, es decir que, {a}x{alfa} ≡ 1 (mod{m})")
    else:  
        print(f"({a},{m}) es diferente de 1, entonces {a} no tiene inverso módulo {m}")

  1. Definimos una función llamada «inverso_modn» la cual recibe como argumentos dos enteros positivos: \(a\) que es el número del cual queremos encontrar el inverso y \(m\) el módulo. Por el Teorema 34, sabemos que \(a\) tiene inverso si \((a,m) = 1\). Ocupamos la función «euclides_extendido_ciclos», la cual calcula el valor de las variables «alfa», «beta» y «d» que son los coeficientes de la combinación lineal \(a\alpha + m\beta = 1\).

def inverso_modn(a,m):  
    alfa,beta,d = euclides_extendido_ciclos(a,m)

  1. Luego creamos un condicional if en el cual verificamos si se cumple la condición de que \(d = 1\). Si esto es verdadero el código nos imprime en la consola, que el inverso de \(a\) es «alfa» y la congruencia \(a\alpha \equiv 1\pmod{m}\).

    if d == 1:
        print(f"El inverso de {a} es {alfa}, es decir que, {a}x{alfa} ≡ 1 (mod{m})")

  1. En caso de que el valor de la variable «d» sea diferente de \(1\) el código pasa el condicional else y se imprime en la consola que \((a,m)\) es diferente de \(1\) y por lo tanto \(a\) no tiene inverso módulo \(m\).

    else:  
        print(f"({a},{m}) es diferente de 1, entonces {a} no tiene inverso módulo {m}")

Ejercicios de práctica#

  1. Demuestra los siguientes incisos.

    • Dos números enteros pares arbitrarios \(a\) y \(b\) son congruentes módulo \(2\).

    • Dos números impares arbitrarios \(a\) y \(b\) son congruentes módulo \(2\).

    • Si tenemos un número entero par \(a\) y otro número entero impar \(b\), no son congruentes módulo \(2\).

  2. Demuestra que si \(p\) es un número primo positivo y \(ab \equiv 0 \pmod{p}\), entonces \(a \equiv 0 \pmod{p}\) o \(b \equiv 0 \pmod{p}\).

  3. Para cada enunciado, prueba su veracidad mediante una demostración. Si el enunciado es falso, da un contraejemplo.

    • Si \(a \equiv b \pmod{m}\) y \(a \equiv b\pmod{n}\), entonces \(a \equiv b \pmod{m + n}\).

    • Si \(a\equiv b\pmod{m}\) y \(a\equiv b\pmod{n}\), entonces \(a\equiv b\pmod{mn}\).

    • Sea \(p\) un número primos. Si \(ac\equiv bc\pmod{p}\) y \(p\not\mid c\), entonces \(a\equiv b\pmod{p}\).

  4. Encuentra el residuo en las siguientes exponenciaciones.

    • Cuando \(2^{97}\) es dividido por \(13\).

    • Cuando \(4^{117}\) es dividido por \(15\).

    • Cuando \(19^{1976}\) es dividido por \(23\).

  5. Sea \(m\) un entero positivo, y sean \(a\) y \(b\) enteros primos relativos con \(m\). Si \(x\) y \(y\) son enteros tales que \(a^x \equiv b^x \pmod{m}\) y \(a^y \equiv b^y \pmod{m}\), demuestra que \(a^{(x,y)} \equiv b^{(x,y)} \pmod{m}\).