7.4: Aritmética Modular

En esta sección, observamos una familia particular de relaciones de equivalencia sobre los enteros y exploramos la forma en que la aritmética interactúa con ellos.

Definición 7.76. Para cada uno\(n\in \mathbb{N}\), defina\(n\mathbb{Z}\) ser el conjunto de todos los enteros que son divisibles por\(n\). En la notación set-builder, tenemos\[n\mathbb{Z} := \{m \in \mathbb{Z} \mid m = nk \text{ for some } k \in \mathbb{Z}\}.\]

Por ejemplo,\(5\mathbb{Z} = \{ \ldots,-10,-5,0,5,10,\ldots\}\) y\(2\mathbb{Z}\) es el conjunto de enteros pares.

Problema 7.77. Considera los conjuntos\(3 \mathbb{Z}\),\(5 \mathbb{Z}\),\(15 \mathbb{Z}\), y\(20 \mathbb{Z}\).

1. Enumere al menos cinco elementos en cada uno de los conjuntos anteriores.
2. Observe que\(3 \mathbb{Z} \cap5 \mathbb{Z} = n\mathbb{Z}\) para algunos\(n\in \mathbb{N}\). ¿Qué es\(n\)? Describir\(15\mathbb{Z}\cap 20 \mathbb{Z}\) de manera similar.
3. Dibuja un diagrama de Venn que ilustre cómo los conjuntos\(3\mathbb{Z}\)\(5\mathbb{Z}\), y se\(15\mathbb{Z}\) cruzan.
4. Dibuja un diagrama de Venn que ilustre cómo los conjuntos\(5\mathbb{Z}\)\(15\mathbb{Z}\), y se\(20\mathbb{Z}\) cruzan.

Teorema 7.78. Vamos\(n\in \mathbb{N}\). Si\(a,b \in n\mathbb{Z}\), entonces\(-a\),\(a+b\), y también\(ab\) están en\(n\mathbb{Z}\).

Definición 7.79. Para cada uno\(n\in \mathbb{N}\), defina la relación\(\equiv_n\) en\(\mathbb{Z}\) vía\(a\equiv_n b\) si\(a-b \in n\mathbb{Z}\). Leemos\(a\equiv_n b\) como “\(a\)es congruente con\(b\) módulo”\(n\).

Tenga en cuenta que\(a-b \in n\mathbb{Z}\) si y sólo si\(n\) divide\(a-b\), lo que implica que\(a\equiv_n b\) si y sólo si\(n\) divide\(a-b\).

Ejemplo 7.80. Nos encontramos\(\equiv_5\) en el Problema 7.22 y descubrimos que había cinco grupos distintos de familiares. En particular, tenemos\[\begin{aligned} rel(0) & = \{\ldots, -10, -5, 0, 5, 10,\ldots\}\\ rel(1) & = \{\ldots, -9, -4, 1, 6, 11,\ldots\}\\ rel(2) & = \{\ldots, -8, -3, 2, 7, 12,\ldots\}\\ rel(3) & = \{\ldots, -7, -2, 3, 8, 13,\ldots\}\\ rel(4) & = \{\ldots, -6, -1, 4, 9, 14,\ldots\}.\end{aligned}\] Aviso que esta colección forma una partición de\(\mathbb{Z}\). Por Corolario 7.74, la relación\(\equiv_5\) debe ser una relación de equivalencia.

El ejemplo anterior generaliza como se esperaba. Puedes probar el siguiente teorema ya sea demostrando que\(\equiv_n\) es reflexivo, simétrico y transitorio o utilizando Corolario 7.74.

Teorema 7.81. Porque\(n\in \mathbb{N}\), la relación\(\equiv_n\) es una relación de equivalencia sobre\(\mathbb{Z}\).

Tenemos notación y terminología especiales para las clases de equivalencia que corresponden a\(\equiv_n\).

Definición 7.82. Para\(n\in \mathbb{N}\), vamos a\([a]_n\) denotar la clase de equivalencia de\(a\) con respecto a\(\equiv_n\) (ver Definiciones 7.17 y 7.44). La clase de equivalencia\([a]_n\) se llama la clase de congruencia (o residuo) de\(a\) módulo\(n\). Se denota la colección de todas las clases de equivalencia determinadas por\(\equiv_n\)\(\mathbb{Z}/n\mathbb{Z}\), que se lee “\(\mathbb{Z}\)módulo\(n\mathbb{Z}\)”.

Ejemplo 7.83. Vamos a calcular\([2]_7\). Rastreando las definiciones, vemos que\[\begin{aligned} m \in [2]_7 & ⇐⇒ m \equiv_7 2\\ & ⇐⇒ m-2\in 7\mathbb{Z}\\ & ⇐⇒ m-2 = 7k \text{ for some $k\in \mathbb{Z}$}\\ & ⇐⇒ m = 7k+2 \text{ for some $k\in \mathbb{Z}$}.\end{aligned}\] Dado que los múltiplos de\(7\) son\(7\mathbb{Z} = \{\ldots,-14,-7,0,7,14,\ldots\}\), podemos encontrar\([2]_7\) agregando\(2\) a cada elemento de\(7\mathbb{Z}\) para obtener\([2]_7 = \{\ldots,-12,-5,2,9,16,\ldots\}\).

Problema 7.84. Para cada una de las siguientes clases de congruencia, encuentra cinco elementos en el conjunto de tal manera que al menos uno sea mayor que\(70\) y uno sea menor que\(70\).

1. \([4]_7\)
2. \([-3]_7\)
3. \([7]_7\)

Problema 7.85. Describir\([0]_3\)\([1]_3\),\([2]_3\),\([4]_3\), y\([-2]_3\) como listas de elementos como en el Ejemplo 7.83. ¿En cuántas clases de congruencia distintas hay\(\mathbb{Z}/3\mathbb{Z}\)? El teorema 7.43 podría ser útil.

Considera usar el Teorema 7.42 para probar el siguiente teorema.

Teorema 7.86. Para\(n\in \mathbb{N}\) y\(a,b\in \mathbb{Z}\),\([a]_n = [b]_n\) si y sólo si\(n\) divide\(a-b\).

Corolario 7.87. Para\(n\in \mathbb{N}\) y\(a\in \mathbb{Z}\),\([a]_n = [0]_n\) si y sólo si\(n\) divide\(a\).

El siguiente resultado proporciona una caracterización útil para cuando dos clases de congruencia son iguales. El algoritmo de división será útil a la hora de probar este teorema.

Teorema 7.88. Para\(n\in \mathbb{N}\) y\(a,b\in \mathbb{Z}\),\([a]_n = [b]_n\) si y sólo si\(a\) y\(b\) tener el mismo resto cuando se divide por\(n\).

Al probar la Parte (a) del siguiente teorema, hacer uso del Teorema 7.86. Para la Parte b), tenga en cuenta que\(a_1b_1-a_2b_2 = a_1b_1 -a_2b_1 + a_2b_1-a_2b_2\).

Teorema 7.89. Dejar\(n\in \mathbb{N}\) y dejar\(a_1,a_2,b_1,b_2 \in \mathbb{Z}\). Si\([a_1]_n = [a_2]_n\) y\([b_1]_n = [b_2]_n\), entonces

1. \([a_1+b_1]_n = [a_2+b_2]_n\), y
2. \([a_1\cdot b_1]_n = [a_2\cdot b_2]_n\).

El teorema anterior nos permite definir suma y multiplicación en\(\mathbb{Z}/n\mathbb{Z}\).

Definición 7.90. Vamos\(n\in \mathbb{N}\). Definimos la suma y producto de las clases de congruencia en\(\mathbb{Z}/n\mathbb{Z}\) vía\[[a]_n + [b]_n:= [a+b]_n \quad \text{and} \quad [a]_n \cdot [b]_n:= [a\cdot b]_n.\]

Ejemplo 7.91. Por Definición 7.90,\([2]_7+[6]_7 = [2+6]_7 = [8]_7\). Por Teorema 7.86,\([8]_7 = [1]_7\), y así\([2]_7+[6]_7 = [1]_7\). De igual manera,\([2]_7\cdot[6]_7 = [2\cdot6]_7 = [12]_7 = [5]_7\).

La suma y multiplicación para\(\mathbb{Z}/n\mathbb{Z}\) tiene muchas propiedades familiares y algunas no tan familiares. Por ejemplo, las clases de suma y multiplicación de congruencia son tanto asociativas como conmutativas. Sin embargo, es posible para\([a]_n\cdot[b]_n = [0]_n\) incluso cuando\([a]_n \neq [0]_n\) y\([b]_n \neq [0]_n\).

Teorema 7.92. Si\(n\in \mathbb{N}\), entonces la adición en\(\mathbb{Z}/n\mathbb{Z}\) es conmutativa y asociativa. Es decir, para todos\([a]_n, [b]_n, [c]_n \in \mathbb{Z}/n\mathbb{Z}\), tenemos

1. \([a]_n + [b]_n = [b]_n + [a]_n\), y
2. [modular agregar assoc]\(([a]_n + [b]_n) + [c]_n = [a]_n + ([b]_n + [c]_n)\).

Teorema 7.93. Si\(n\in \mathbb{N}\), entonces la multiplicación en\(\mathbb{Z}/n\mathbb{Z}\) es conmutativa y asociativa. Es decir, para todos\([a]_n, [b]_n, [c]_n \in \mathbb{Z}/n\mathbb{Z}\), tenemos

1. \([a]_n \cdot [b]_n = [b]_n \cdot [a]_n\), y
2. [assoc mult modular]\(([a]_n \cdot [b]_n) \cdot [c]_n = [a]_n \cdot ([b]_n \cdot [c]_n)\).

Una consecuencia de los Teoremas 7.92 (b) y 7.93 (b) es que no se necesitan paréntesis al sumar o multiplicar clases de congruencia. El siguiente teorema se desprende de la Definición 7.90 junto con los Teoremas 7.92 (b) y 7.93 (b) y la inducción sobre\(k\).

Teorema 7.94. Vamos\(n\in \mathbb{N}\). Para todos\(k\in \mathbb{N}\), si\([a_1]_n,[a_2]_n,\ldots, [a_k]_n \in \mathbb{Z}/n\mathbb{Z}\), entonces

1. \([a_1]_n+[a_2]_n+\cdots+ [a_k]_n = [a_1 + a_2 +\cdots+ a_k]_n\), y
2. \([a_1]_n [a_2]_n \cdots [a_k]_n = [a_1 a_2 \cdots a_k]_n\).

El siguiente resultado es un caso especial del Teorema 7.94 (b).

Corolario 7.95. Vamos\(n\in \mathbb{N}\). Si\(a\in\mathbb{Z}\) y\(k\in \mathbb{N}\), entonces\(([a]_n)^k = [a^k]_n\)

Ejemplo 7.96. Vamos a calcular\([8^{179}]_7\). Vemos que\[\begin{aligned} _7 & = ([8]_7)^{179} & (\text{Corollary 7.95})\\ & = ([1]_7)^{179} & (\text{Theorem 7.86})\\ & = [1^{179}]_7 & (\text{Corollary 7.95})\\ & = [1]_7.\end{aligned}\]

Para la Parte (a) en el siguiente problema, use el hecho de que\([6]_7 = [-1]_7\). Para la Parte (b), use el hecho de que\([2^3]_7 = [1]_7\).

Problema 7.97. Para cada una de las siguientes, encuentra un número\(a\) con\(0\le a \le 6\) tal que la cantidad dada sea igual a\([a]_7\).

1. \([6^{179}]_7\)
2. \([2^{300}]_7\)
3. \([2^{301} +5]_7\)

Problema 7.98. Encontrar\(a\) y\(b\) tal que\([a]_6\cdot[b]_6 = [0]_6\) pero\([a]_6 \neq [0]_6\) y\([b]_6 \neq [0]_6\).

Teorema 7.99. Si\(n\in \mathbb{N}\) tal eso no\(n\) es primo, entonces existe\([a]_n, [b]_n \in \mathbb{Z}/n\mathbb{Z}\) tal que\([a]_n\cdot[b]_n = [0]_n\) mientras\([a]_n \neq [0]_n\) y\([b]_n \neq [0]_n\).

Teorema 7.100. Observe que no\(2x = 1\) tiene solución en\(\mathbb{Z}\). Demostrar que\([2]_7[x]_7 = [1]_7\) sí tiene una solución con\(x\) in\(\mathbb{Z}\). ¿Y qué pasa\([14]_7[x]_7 = [1]_7\)?

Teorema 7.101. Hacer uso del Teorema 7.94, Corolario 7.95, y Teorema 7.86 para probar el siguiente teorema.

Si\(m\in \mathbb{N}\) tal que\[m=a_k10^k + a_{k-1}10^{k-1} + \cdots + a_110 + a_0,\] donde\(a_k, a_{k-1}, \ldots, a_1, a_0\in \{0,1,\ldots, 9\}\) (es decir,\(a_k, a_{k-1}, \ldots, a_1, a_0\) son los dígitos de\(m\)), entonces\[[m]_3 = [a_k + a_{k-1} + \cdots + a_1 + a_0]_3.\]

Probablemente reconozcas el siguiente resultado. Su prueba se desprende rápidamente del Corolario 7.87 junto con el teorema anterior.

Teorema 7.102. Un entero es divisible por\(3\) si y solo si la suma de sus dígitos es divisible por\(3\).

Revisemos el Teorema 7.21, que originalmente probamos por inducción.

Problema 7.103. Utilice Corolario 7.87 para probar que para todos los enteros\(n \ge 0\),\(3^{2n}-1\) es divisible por\(8\). Usted tendrá que manejar el caso involucrando\(n=0\) por separado.

Cerramos este capítulo con un problema divertido.

Problema 7.104. Probar o proporcionar un contraejemplo: Ningún entero\(n\) existe tal que\(4n+3\) sea un cuadrado perfecto.