Tema 5: Aritmetica Modular I
Aritmetica Modular
Division Entera y Congruencias
El teorema de la division afirma que, dado un numero natural \(m\): Para cada entero \(a\) existe un unico cociente \(q\) y un unico resto \(0 \le r < m\) tales que:
\(a = qm + r\)
El resto \(r\) mide cuanto le falta (o le sobra) a \(m\) para ser divisor de \(a\).
Nos fijamos que \(r = 0, 1, \cdots m - 1\). Es decir, hay \(m\) posibles valores de resto para cualquier \(a\).
Fijado \(m\), podemos calcular \(r\). Distintos \(a\) tendran el mismo \(r\).
Por ejemplo, si tomamos \(m = 2\):
- Para \(a = 5, a = 2 \cdot 2 + \textbf{1}\)
- Para \(a = 6, a = 3 \cdot 2 + \textbf{0}\)
- Para \(a = 7, a = 3 \cdot 2 + \textbf{1}}\)
Fijado \(m\) podemos clasificar todos los \(a\) segun el resto \(r\).
Clases de Equivalencia
Fijamos \(m \in \mathbb{N}\). Decimos que \(a, b \in \mathbb{Z}\) son congruentes modulo \(m\) y lo escribiremos como:
\(a \equiv b \mod(m)\)
si
\(a = q_1m + r, b = q_2m + r\)
Para \(q_1\) y \(q_2\) enteros y \(0 \le r < m\).
Esto significa que \(a\) y \(b\) son congruentes si tienen el mismo resto.
Una definicion equivalente, \(a \equiv b \mod(m) \Leftrightarrow (a - b) = \alpha m\)
Esta relacion entre \(a\) y \(b\) es un caso particular de la relacion de equivalencia. Se cumplen las siguientes propiedades:
- Reflexiva: \(a \equiv a \mod(m)\) (cada numero es congruente consigo mismo).
- Simetrica: Si \(a \equiv b \mod(m)\), entonces\(b \equiv a \mod(m)\).
- Transitiva: Si \(a \equiv b \mod(m)\) y \(b \equiv c \mod(m)\), entonces \(a \equiv c \mod(m)\)
Fijado \(m\) y \(a \equiv q \cdot m + r\), se define la clase de equivalencia de \(a\) con respecto a la relacion de congruencia modulo \(m\) como:
\([a]_m = \{x \in \mathbb{Z} : x \equiv a \mod(m)\} = \{ x \in \mathbb{Z} : x = mk + r, k \in \mathbb{Z}\}\)
Una clase de equivalencia no es mas que la formalizacion de “agrupar los numeros segun el resto \(r\)”.
Con el ejemplo anterior \(\mod(2)\), la clase de 0 son todos los numeros pares mientras que la clase del 1 son todos los numeros impares:
\([8]_2 = [16]_2 = [0]_2\)
Podemos considerar representantes de cada clase. Los canonicos son aquellos que son menores que \(m: [0]_m, [1]_m,\cdots,[m-1]_m\).
Definimos el conjunto de los representantes:
\(\mathbb{Z}_m = \{[0]_m, [1]_m, \cdots, [m - 1]_m\}\)
Para \(m = 5\), por ejemplo:
\(\mathbb{Z}_5 = \{[0]_5, [1]_5, [2]_5, [3]_5, [4]_5\}\)
\([0]_5 \rightarrow 0 = 0 \cdot 5 + \textbf{0}\)
\([1]_5 \rightarrow 1 = 0 \cdot 5 + \textbf{1}\)
\([2]_5 \rightarrow 2 = 0 \cdot 5 + \textbf{2}\)
\([3]_5 \rightarrow 3 = 0 \cdot 5 + \textbf{3}\)
\([4]_5 \rightarrow 4 = 0 \cdot 5 + \textbf{4}\)
Si \(r = 5\) podemos ponerlo en cero:
\(10 = 1 \cdot 5 + 5 = 2 \cdot 5 + 0\)
Podemos generar las clases canonicas:
\([0]_5 = \{0 + 5 \cdot k, k \in \mathbb{Z}\}\)
\([1]_5 = \{1 + 5 \cdot k, k \in \mathbb{Z}\}\)
\([2]_5 = \{2 + 5 \cdot k, k \in \mathbb{Z}\}\)
etcetera
Aritmetica Modular
Podemos sumar y multiplicar en \(\mathbb{Z}_m\).
Suma ATTACH
Definimos \([a]_m + [b]_m = [a + b]_m\). Por ejemplo:
\([2]_5 + [6]_5 = [2 + 5]_5 = [3]_5\) obtenemos su forma canonica. \(6 + 2 = 8 - 5 = 3\), obtenemos su residuo.
\([89]_5 + [3]_5 = [92]_5 = [2]_5\)
\([2]_5 = [1]_5 + [1]_5\)
Tabla de sumar de \(\mathbb{Z}_4\):
Producto ATTACH
Definimos \([a]_m \cdot [b]_m = [a \cdot b]_m\). Por ejemplo:
\([10]_5 \cdot [2]_5 = [20]_5 = [0]_5\)
\([4]_5 \cdot [4]_5 = [16]_5 = [1]_5\)
Tabla de producto de \(\mathbb{Z}_4\):
Division
Si definimos un producto, tambien podemos usar la division:
\([4]_5 = \frac{[1]_5}{[4]_5}\)
Cuerpos Finitos
Si \([a] \in \mathbb{Z}_m\) decimos que es invertible, si existe \([a]^{-1}\) tal que \([a] \cdot [a]^{-1} = [1]\).
\(a\) es invertible (modulo \(m\)), si y solo si:
\(\text{mcd}(a, m) = 1\)
Denotamos por \(\mathbb{Z}^*_m\) al conjunto de elementos invertibles de \(Z_m\).
Si \(m = p\) un numero primo \(p, \mathbb{Z^*_p} = \mathbb{Z}_p \backslash \{[0]\}\).
Por ejemplo, el inverso de \([6]\) en \(\mathbb{Z}_{17}\):
Pequeno Teorema de Fermat
Si \(p\) primo y \(\text{mcd}(a, p) = 1\), entonces:
\(a^{p - 1} \equiv q (\mod(p))\)
En particular: \(a^p \equiv a (\mod(p))\).
