[skip-to-content]

Sección 3.1 Definición y Propiedades Básicas

Definición 3.1.1.
Sean \(a,b \in \mathbb{Z}\) y \(n \in \mathbb{N}\text{.}\) Se dice que \(a\) es congruente a \(b\) módulo \(n\) si
\begin{equation*} a \equiv b \ (\text{mod } n) \Leftrightarrow n |(a-b)\text{.} \end{equation*}
Es decir, si existe un único \(t \in \mathbb{Z}\) tal que \(nt=a-b.\)
Note que \(6 \equiv -2\) (mod \(4\)), pues \(4 |8\text{.}\) Sin embargo, \(7 \not \equiv -4\) (mod \(3\)), pues \(3 \not\mid 11.\)

De la Definición 3.1.1, podemos notar que si \(b \le a\text{,}\) entonces ¡ \(b\) es el resto de la división entre \(a\) y \(n\text{!}\) Nuevamente Sage nos proporciona una herramienta para calcular el número entero \(b\) tal que \(a \equiv b\) (mod \(n\)).

Probaremos que si \(a\equiv b \ (\text{mod } n)\text{,}\) entonces \(a^{2}+b^{2}\equiv 2ab \ (\text{mod } n)\text{.}\)

Como \(a\equiv b \ (\text{mod } n)\text{;}\) existe un único entero \(t\text{,}\) tal que \(nt=(a-b)\text{.}\) Elevando al cuadrado, se consigue \(n(nt^{2})=(a^{2}+b^{2})-2ab\text{.}\) Esto implica \(a^{2}+b^{2}\equiv 2ab \ (\text{mod } n)\text{.}\)

El siguiente resultado será importante para introducir el conjunto \(\mathbb{Z}/n\mathbb{Z}\text{.}\)

1. Se sabe que \(n |0\) y \(0=a-a\text{.}\) Por lo tanto; \(n|(a-a)\text{,}\) que implica \(a\equiv a \ (\text{mod } n)\text{.}\)

2. Por hipótesis, se sabe que \(a\equiv b \ (\text{mod } n)\text{.}\) Esto implica que \(n |(a-b)\text{.}\) Por otro lado, si \(n|y\) entonces \(n|(-y)\) (con \(y \in \mathbb{Z}\)). Bajo esta consideración, \(n |(b-a)\text{;}\) lo que implica \(b\equiv a \ (\text{mod } n)\text{.}\)

3. Por hipótesis, se sabe que \(a\equiv b \ (\text{mod } n)\) y \(b\equiv c \ (\text{mod } n)\text{.}\) Por lo tanto, existen únicos \(k,t \in \mathbb{Z}\) tales que \(nk=a-b\) y \(nt=b-c\text{.}\) Sumando estas dos igualdades, se obtiene \(n(k+t)=a-c\text{.}\) Esto implica \(a\equiv c \ (\text{mod } n)\text{.}\)

Como \(2318\equiv 109 \ (\text{mod } 47)\) y \(109\equiv 15 \ (\text{mod } 47)\text{,}\) entonces \(2318\equiv 15 \ (\text{mod } 47)\text{.}\)

¿Se pueden sumar o multiplicar números que son congruentes en módulo \(n\text{?}\) La Proposición 3.1.6 tiene la respuesta.

Como \(a\equiv b\) (mod \(n\)) y \(c\equiv d\) (mod \(n\)), entonces existen únicos \(k,t \in \mathbb{Z}\) tales que \(nk=a-b\) y \(nt=c-d\text{.}\)

Como \(nk=a-b\text{,}\) podemos multiplicar por \(\lambda\) (entero). Así, \(n (\lambda k)= \lambda a- \lambda b\text{.}\) Esto implica \(\lambda a\equiv \lambda b \ (\text{mod } n).\)

Por otro lado, sumando \(nk=a-b\) y \(nt=c-d\text{,}\) se obtiene \(n(k+t)=(a+c)-(b+d)\text{.}\) Esto implica \(a+c\equiv b+d \ (\text{mod } n)\text{.}\)

Multiplicando por \(c\text{,}\) la expresión \(nk=a-b\text{;}\) se consigue \(nkc=ac-bc\text{.}\) Si se multiplica por \(b\text{,}\) la expresión \(nt=c-d\text{;}\) se consigue \(ntb=cb-db\text{.}\) Al sumar estas cantidades, se logra \(n(kc+tb)=ac-bd\text{.}\) Esto implica \(ac\equiv bd \ (\text{mod } n)\text{.}\)

La demostración de esta proposición se realizará por Inducción. Considere la función proposicional
\begin{equation*} p(k): a^{k}\equiv b^{k} \ (\text{mod } n), \end{equation*}

con \(k,n \in \mathbb{N}\) y \(a,b \in \mathbb{Z}\text{.}\)

\(p(1)\) es verdadero; pues por hipótesis, \(a\equiv b\) (mod \(n\)).

Considere la hipótesis de inducción \(p(k): a^{k}\equiv b^{k} \ (\text{mod } n)\text{.}\) Por demostrar \(p(k+1): a^{k+1}\equiv b^{k+1} \ (\text{mod } n)\) es verdadero. En efecto

\begin{equation*} a^{k+1}\equiv a^{k}\cdot a \equiv b^{k}\cdot a \equiv b^{k}\cdot b \equiv b^{k+1}\ (\text{mod } n)\text{,} \end{equation*}
por hipótesis de inducción y transitividad de la congruencia. Por lo tanto, \(p(k) \Rightarrow p(k+1)\text{.}\)

Por Principio de Inducción, se verifica que si \(a\equiv b\) (mod \(n\)) entonces \(a^{k}\equiv b^{k} \ (\text{mod } n)\) para todo \(k\in \mathbb{N}.\)

Se probará que \(2^{18342} \equiv 1\ (\text{mod } 7)\text{.}\)

Se sabe que \(2^{3} \equiv 1\ (\text{mod } 7)\) y \(18342=6114\cdot 3\text{.}\) Por lo tanto

\begin{equation*} 2^{3} \equiv 1\ (\text{mod } 7)\Rightarrow 2^{18342} \equiv 1\ (\text{mod } 7)\text{.} \end{equation*}

Por hipótesis, se sabe que \(m | n\text{.}\) Además, \(a \equiv b\) (mod \(n\)) implica \(n |(a-b)\text{.}\) Por transitividad de la divisibilidad (si \(a | b\) y \(b | c\) entonces \(a | c\)), se concluye que \(m|(a-b)\text{.}\) Por lo tanto, \(a\equiv b\) (mod \(m\)).

¿Si \(6\cdot 3 \equiv 2 \cdot 3\) (mod 6) entonces \(3 \equiv 2\) (mod 6)? Falso, pues \(6 \not\mid 1.\) No es directo cancelar un factor común si estamos trabajando con congruencias. Por consiguiente, será importante considerar las Proposiciones 3.1.10, 3.1.11 y 3.1.12.

Como \(ac\equiv bc\) (mod \(n\)), entonces \(n| c(a-b)\text{.}\) Adicionalmente, \((c,n)=1\) (es decir, \(n \not\mid \ c\)) entonces \(n| (a-b)\text{.}\) Por lo tanto, \(a\equiv b \ (\text{mod } n).\)

Como \(ac\equiv bc\) (mod \(p\)), entonces \(p| c(a-b)\text{.}\) Como \(p\) es primo, por Lema de Euclides; \(p|c\) \(\lor\) \(p|c\text{.}\) Sin embargo; \(p \not\mid \ c\text{,}\) por lo que \(p| (a-b)\text{.}\) Esto implica que \(a\equiv b \ (\text{mod } p).\)

La Proposición 3.1.12 nos muestra un resultado más general para la ley de cancelación en congruencias.

Se asumirá que \(ac\equiv bc\) (mod \(n\)). Por lo tanto, \(n| c(a-b)\text{.}\) Por propiedad de divisibilidad, \(\dfrac{n}{d}| \dfrac{c}{d}(a-b)\text{.}\) Note que \(\dfrac{n}{d}, \dfrac{c}{d} \in \mathbb{Z}\text{,}\) pues \((c,n)=d\) implica \(\left( \dfrac{c}{d},\dfrac{n}{d}\right)=1.\) De esto último, se consigue que \(\dfrac{n}{d} \not\mid \dfrac{c}{d}\text{.}\) Por lo tanto, \(\dfrac{n}{d}|(a-b)\text{.}\) Entonces \(a\equiv b \ \left(\text{mod } \dfrac{n}{d}\right).\)

Nuestra hipótesis es \(a\equiv b \ \left(\text{mod } \dfrac{n}{d}\right) \text{.}\) Por lo tanto, \(\dfrac{n}{d}|(a-b)\text{.}\) Por propiedad de divisibilidad, \(n|d(a-b)\text{.}\) Adicionalmente, ya que \((c,n)=d\) entonces \(d| c\text{.}\) Esto implica que \(d(a-b)| c(a-b)\text{.}\) Por transitividad de la divisibilidad, \(n|c(a-b)\text{.}\) Por lo tanto, \(ac\equiv bc\) (mod \(n\)).

¿Y si queremos trabajar con exponenciación modular? Por ejemplo, determinar el resto al dividir \(64435^{33343}\) por \(108\text{.}\)

Esto puede resultar complejo. Sin embargo, disponemos nuevamente de Sage.

Calcularemos el resto de la división entre \(6^{14}\) y \(13\text{.}\)

Notemos que \(6^{2}\equiv -3\) (mod \(13\)). Por lo tanto \(6^{4}\equiv (-3)^{2}=9\equiv -4\text{.}\) Esto implica \(6^{8}\equiv (-4)^{2}=16\equiv 3\) (mod \(13\)). Por consiguiente

\begin{equation*} 6^{14}\equiv 6^{8}\cdot 6^{4}\cdot 6^{2}\equiv (-3)\cdot (-4)\cdot 3\equiv 36 \equiv 10 \ (\text{mod } 13). \end{equation*}

Por lo tanto, el resto de la división entre \(6^{14}\) y \(13\) es \(10\text{.}\)

Calcularemos el dígito de las unidades de \(3^{999}\text{.}\)

Este problema equivale a encontrar un número entero \(z\) (con \(0 \le z \le 9\)), tal que \(z \equiv 3^{999} \ (\text{mod } 10)\text{.}\)

Note que \(3^{2} \equiv -1\ (\text{mod } 10)\) y \(999=2\cdot 499+1\text{.}\) Por lo tanto, \(3^{998} \equiv (-1)^{499}\equiv -1\ (\text{mod } 10)\text{.}\) Multiplicando por \(3\text{,}\) se consigue

\begin{equation*} 3^{999} \equiv -3 \equiv 7\ (\text{mod } 10). \end{equation*}

Por lo tanto, el dígito de las unidades de \(3^{999}\) es \(7\text{.}\)

¿Cómo calcular los últimos dos dígitos de \(3^{999}\text{?}\) Basta encontrar un número entero \(z\) (con \(1 \le z \le 99\)), tal que \(z \equiv 3^{999} \ (\text{mod } 100)\text{.}\) ¿Nota algún patrón en relación a los módulos?

Pruebe que \(10^{100000}+2793\equiv 4\) (mod \(7\)).
Observación 3.1.16.
Sean \(a,b \in \mathbb{Z}\) y \(n\in \mathbb{N}\text{.}\) Entonces \(a \equiv b\) (mod \(n\)) si y sólo si \(a\) y \(b\) tienen el mismo resto al ser divididos por \(n\text{.}\)