Congruencias y propiedades básicas#

Introducción#

En el capítulo del recordatorio de clases de equivalencia vimos en el Example 76 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#

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

Example 92

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

Veamos que la relación definida anteriormente en el Example 76 es equivalente a la Definition 35 en el siguiente teorema.

Theorem 27

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

Proof. Notemos que la Definition 35 de congruencia, es equivalente a la relación del Example 76. Esto ya lo demostramos en la Proposition 24.

Example 93

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

Podemos expresar las congruencias con otra caracterización, que es una relación como la del Example 76.

Theorem 28

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

Proof. 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 \(a-b = km\). lo cual implica que \(m|(a-b)\), y por lo tanto por definición tenemos que \(a \equiv b \pmod{m}\). \(\square\)

Veamos algunos ejemplos del teorema anterior.

Example 94

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

  • 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 Definition 28.

Theorem 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}\).

Proof. La demostración de estas \(3\) propiedades ya las vimos en el Example 76.

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

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

Definition 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} \}.\]

Example 95

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 Theorem 28, si tenemos que \(a \equiv r \pmod{m}\) podemos decir que \(a = r + mq\). Esto nos lleva a introducir la siguiente definición.

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

Corollary 9

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

Proof. Demostremos las dos implicaciones.

  • Supongamos que \(r\) es el residuo mínimo de \(a\) al ser dividido por \(m\).

Veamos que gracias al Theorem 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\)

Remark 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 Definition 36 de clases de congruencias, ahora veremos las operaciones básicas entre las clases de congruencias.

Definition 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*}\]

Example 96

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 los 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 probaremos 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\).

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

Proof. 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 Theorem 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\).

De manera similar tenemos que \(a \equiv a' \pmod{m}\) y \(b \equiv b' \pmod{m}\). Entonces por el Theorem 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 Theorem 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 con 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.

Theorem 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}\).

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

Theorem 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}}\).

Proof. 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 Proposition 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 Theorem 31.

Corollary 10

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

Proof. 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 Corollary 3 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 éstas sea el mismo.

Theorem 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}\).

Proof. 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|\left[ (a - c) - (b - d) \right]\) 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\)

Example 97

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

Solución.

  • Si sumamos las congruencias obtenemos,

\[\begin{align*} 21 + 17 &\equiv -4 + 2 \pmod{5} \\ & \\ 38 &\equiv -2 \pmod{5}. \end{align*}\]

  • Si restamos las congruencias obtenemos,

\[\begin{align*} 21 - 17 &\equiv -4 - 2 \pmod{5} \\ & \\ 4 &\equiv -6 \pmod{5}. \end{align*}\]

  • Si multiplicamos las congruencias obtenemos,

\[\begin{align*} 21\cdot 17 &\equiv (-4)\cdot 2 \pmod{5} \\ & \\ 357 &\equiv -8 \pmod{5}. \end{align*}\]

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

Theorem 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}\).

Proof. 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, de la hipótesis \(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 Theorem 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\)

Example 98

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 Theorem 33 tendríamos que \(22^{47} \equiv 2^{47} \pmod{5}\).

Notemos 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, tendremos que,

\[\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 obtenemos 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\).

Example 99

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 Definition 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 Definition 38 dotamos para este conjunto las operaciones de suma y producto, pero 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 más adelante, será notar que en este conjunto algunos números tienen inverso multiplicativo. Lo que vamos a ver en esta sección es, bajo qué 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}\).

Definition 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}\).

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

Example 100

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

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

Proof. 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 Theorem 8 podemos concluir que \(a\) y \(m\) son primos relativos.

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

Por la Definition 9, sabemos que \((a,m) = 1\). Luego, por el Theorem 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 Theorem 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 Theorem 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}\).