2.5: Aritmética Modular
- Page ID
- 118522
Definimos una relación de equivalencia que nos ayudará a obtener conocimientos en la teoría de números. DEFINICIÓN. Divide,\(a \mid b\) Let\(a\) y\(b\) ser enteros. Entonces\(a\) divide\(b\), escrito\(a \mid b\), si hay\(c \in \mathbb{Z}\) tal que\[a \cdot c=b .\] DEFINICIÓN. Congruencia,\(x \equiv y \bmod n, \equiv_{n}\) Let\(x, y, n \in \mathbb{Z}\) y\(n>1\). Entonces\[x \equiv y \bmod n\] (o\(x \equiv_{n} y\)) si\[n \mid(x-y) .\] La relación\(\equiv_{n}\) on\(\mathbb{Z}\) se llama congruencia\(\bmod n\).
Congruencia mod\(n\) es una relación de equivalencia en\(\mathbb{Z}\).
Demostrar Teorema 2.25.
Las clases de equivalencia de la relación\(\equiv_{n}\) se denominan clases de congruencia, clases de residuo o clases de resto\(\bmod n\). El conjunto de clases de congruencia\(\bmod n\) puede ser escrito\(\mathbb{Z}_{n}\) o\(\mathbb{Z} / n \mathbb{Z}\).
Por supuesto\(\mathbb{Z}_{n}\) que es una partición de\(\mathbb{Z}\). Cuando\(n=2\), las clases de residuo se llaman los números pares e impares. Muchos de los hechos que conoces sobre números pares e impares se generalizan si piensas en ellos como clases de residuos. ¿Para qué sirven las clases de residuos\(n=3\)?
Lo dejamos como ejercicio (Ejercicio 2.6) para probar que dos enteros están en la misma clase de resto\(\bmod n\) siempre que tengan el mismo resto cuando se dividan por\(n\).
Notación. [a] Fijar un número natural\(n \geq 2\). Deja entrar a un\(\mathbb{Z}\). Representamos la clase de equivalencia de a con respecto a la relación\(\equiv_{n}\) por\([a]\).
Proposición 2.26. Si\(a \equiv r \bmod n\) y\(b \equiv s \bmod n\), entonces\[\text { (i) } \quad a+b \equiv r+s \bmod n\] y\[\text { (ii) } a b \equiv r s \quad \bmod n .\] Prueba. (i) Supongamos que\(a \equiv r \bmod n\) y\(b \equiv s \bmod n\). Entonces\(n \mid(a-r)\) y\(n \mid(b-s)\). \[n \mid(a+b-(r+s))\]Por lo tanto\[a+b \equiv r+s \quad \bmod n\] demostrando (i).
Para probar (ii), tenga en cuenta que existen\(i, j \in \mathbb{Z}\) tales que\[a=n i+r\] y\[b=n j+s\] Entonces\[a b=n^{2} j i+r n j+s n i+r s=n(n j i+r j+s i)+r s\] Por lo tanto\[n \mid(a b-r s)\] y\[a b \equiv r s \quad \bmod n\] De ahí las operaciones algebraicas que\(\mathbb{Z}_{n}\) “hereda” de \(\mathbb{Z}\)están bien definidos. Es decir, podemos definir\(+\) y seguir\(\cdot\)\(\mathbb{Z}_{n}\) por\[[a]+[b]=[a+b]\] y\[[a] \cdot[b]=[a \cdot b]\] En matemáticas, cuando preguntas si algo está “bien definido”, te refieres a que en algún lugar de la definición se hizo una elección, y quieres saber si una elección diferente habría resultado en el mismo resultado final. Por ejemplo, vamos\(X_{1}=\{-2,2\}\) y vamos\(X_{2}=\{-1,2\}\). Definir\(y_{1}\) por: “Elige\(x\)\(X_{1}\) y deja”\(y_{1}=x^{2}\). Definir\(y_{2}\) por: “Elige\(x\)\(X_{2}\) y deja”\(y_{2}=x^{2}\). Entonces\(y_{1}\) está bien definido, y es el número 4; pero no\(y_{2}\) está bien definido, ya que diferentes elecciones de\(x\) dan lugar a diferentes números.
En (2.27) y (2.28), los lados de la derecha dependen a priori de una elección particular de elementos de las clases de equivalencia\([a]\) y\([b]\). Pero la Proposición\(2.26\) asegura que la suma y el producto así definidos sean independientes de la elección de los representantes de las clases de equivalencia.
\(Z_{2}\)Además y multiplicación se definen de la siguiente manera:
(1)\([0]+[0]=[0]\)
(2)\([0]+[1]=[1]+[0]=[1]\)
(3)\([1]+[1]=[0]\)
(4)\([0] \cdot[0]=[0] \cdot[1]=[1] \cdot[0]=[0]\)
(5)\([1] \cdot[1]=[1]\).
Observe que si lee\([0]\) como “par” y [1] como “impar”, estas son reglas que aprendió hace mucho tiempo.
Al trabajar con aritmética modular podemos elegir los representantes de las clases de resto que mejor se adapten a nuestras necesidades. Por ejemplo,\[79 \cdot 23 \equiv 2 \cdot 2 \equiv 4 \bmod 7 .\] en otras palabras\[[79 \cdot 23]=[79] \cdot[23]=[2] \cdot[2]=[4] .\] EJEMPLO 2.30. Tal vez recuerde de su exposición temprana a las tablas de multiplicación que la multiplicación por nueve resultó en un producto cuyos dígitos sumaron a nueve. Esto generaliza muy bien con la aritmética modular. Específicamente, si\(a_{n} \in\ulcorner 10\urcorner\) para\(0 \leq n \leq N\) entonces\[\sum_{n=0}^{N} a_{n} 10^{n} \equiv \sum_{n=0}^{N} a_{n} \bmod 9 .\] El resto de cualquier entero dividido por 9 es igual al resto de la suma de los dígitos de ese entero cuando se divide por 9. Comprobante. La observación clave es que\[10 \equiv 1 \bmod 9 .\] Por lo tanto\[\begin{array}{lll} 10^{2} \equiv 1 \cdot 1 \equiv 1 & \bmod 9 \\ 10^{3} \equiv 1 \cdot 1 \cdot 1 \equiv 1 & \bmod 9, \end{array}\] y así sucesivamente para cualquier potencia de 10:\[10^{n} \equiv 1 \bmod 9 \text { for all } n \in \mathbb{N} \text {. }\] (Esta inducción a todos los poderes de 10 es sencilla, pero para demostrarlo formalmente necesitaremos la noción de inducción matemática del Capítulo 4). Por lo tanto en el lado izquierdo de (2.31), trabajando mod 9, podemos sustituir todas las potencias de 10 por 1, y esto nos da el lado derecho.
La observación de que el residuo de un número mod 9 es el mismo que el de la suma de los dígitos se puede utilizar en una técnica llamada “casting out nueves” para verificar la aritmética.
Por ejemplo, considere la siguiente suma (incorrecta). El número en la penúltima columna es la suma de los dígitos, y el número en la última columna es la suma repetida de los dígitos hasta alcanzar un número entre 0 y 9.
1588 22 4
+1805 14 5
3493 19 1
Si la suma se hubiera realizado correctamente, el resto mod 9 de la suma equivaldría a la suma de los restos; así sabemos que se cometió un error.
¿Cuál es el último dígito de\(7^{7}\)?
Queremos saber\(7^{7} \bmod 10\). Tenga en cuenta que, módulo\(10,7^{0} \equiv 1,7^{1} \equiv\)\(7,7^{2} \equiv 9,7^{3} \equiv 3,7^{4} \equiv 1\). Entonces\(7^{7}=7^{4} 7^{3} \equiv 1 \cdot 3 \equiv 3\), y así 3 es el último dígito de\(7^{7}\). EJEMPLO 2.34. ¿Cuál es el último dígito de\(7^{7^{7}}\)?
Por el Ejemplo 2.33, vemos que los residuos de\(7^{n} \bmod 10\) repetición ellos mismos cada vez\(n\) aumenta en 4. Por lo tanto si\(m \equiv n \bmod 4\), entonces\(7^{m} \equiv 7^{n} \bmod 10\).
¿Qué es\(7^{7} \bmod 4\)? Bueno\(7^{1} \equiv 3 \bmod 4,7^{2} \equiv 1 \bmod 4\), entonces\(7^{7} \equiv\)\(\left(7^{2}\right)^{3} \cdot 7 \equiv 3 \bmod 4\). Por lo tanto\[7^{7^{7}} \equiv 7^{3} \equiv 3 \quad \bmod 10 .\]