ARITMÉTICA MODULAR
Con las congruencias podemos establecer un conjunto de operaciones aritméticas, como:
Siendo a, b, c, d ∈ Z y m ∈ N, tales que a ≡ b (mod (m)) y c ≡ d (mod (m)). Entonces,
a + c ≡ b + d (mod (m))
a · c ≡ b · c (mod (m))
(Recordemos que el signo ≡ significa “congruente con” y no es lo mismo que el signo = que
significa “igual a”)
A partir de esto, podemos definir las propiedades aritméticas para las sumas de congruencias:
Propiedad asociativa: a + (b + c) (mod (m)) = (a + b) + c (mod (m))
Elemento neutro: Existe un elemento 0 ∈ Zm, tal que a + 0 (mod (m)) = a (mod (m))
Elemento opuesto: Existe un elemento b ∈ Zm, tal que a + b = 0 (recordemos que 0 es el
elemento neutro de la suma)
Propiedad conmutativa: a + b (mod (m)) = b + a (mod (m))
También podemos definir las propiedades aritméticas para el producto de congruencias:
Propiedad cancelativa: a · c ≡ b · c (mod (m)) y MCD (m, c) = 1, entonces a ≡ b (mod
(m))
Propiedad asociativa: a · (b · c) (mod (m)) = (a · b) · c (mod (m))
Elemento neutro: Existe un elemento 1 ∈ Zm, tal que a · 1 (mod (m)) = a (mod (m))
Elemento inverso: Existe un elemento a-1 ∈ Zm para todo a ∈ Zm con MCD (a, m) = 1, tal
que a · a-1 = 1 (recordemos que 1 es el elemento neutro del producto)
Además de todas estas propiedades también se cumple la propiedad distributiva: a · (b + c)
(mod (m)) = (a · b) + (a · c) (mod (m))
Para acabar, os voy a dar unos ejemplos de usos de las congruencias:
En el DNI: La letra de tu NIF se realiza del siguiente modo: Número DNI (mod 23) y el
resultado se pasa a una tabla que relaciona números con letras.
En la generación de números seudoaleatorios: Los números aleatorios que genera
cualquier ordenador se calculan usando una sucesión basada en congruencias: Xn+1 = (a ·
Xn + c) (mod (m))
En criptografía: De este tema os hablaré dentro de poco, por ahora saber que las
congruencias son la base de toda la criptografía moderna: RSA, El Gamal, …
Calcular aritmética modular?
Hola, estoy haciendo un trabajo de investigacion de fin de curso y me enfrento al problema del calculo
aritmetico modular. Tengo ua función C=70^7(mod 187) y no consigo calcularla. Utilizo la calculadora HP
48gII pero no se como incluir dicha función, me indica un error de sintaxi. Alguien me podría ayudar, no
importa que sea a mano.
Saludos!
PD. No quiero el resultado, sinó que me ayuden a saber calcularlo
Detalles adicionales
Pero si escribo 70^2 el numero es bastante grande. No existe ninguna manera de calcular el resto?
RESPUESTA
70^7 mod 187 = 60
ANALISIS
Si denotamos con [x] la clase residual de x mod 187, podemos escribir:
[70^7] = [70 × 70^6] = [70] × [70^2]^3
pero [70^2] = [4900] = [38] porque 4900 = 26×187 + 38, entonces
[70^7] = [70] × [38]^3 = [70] × [38^3] = [70] × [54872] = [70] × [81]
porque 54872 = 293×187 + 81, entonces
[70^7] = [70×81] = [5670] = [60]
porque 5670 = 30×187 + 60, quedando así demostrado.
La gran ventaja de la aritmética modular es que tiene las siguientes propiedades:
[a+b] = [a] + [b]
[ab] = [a][b]
y de ellas se hacen todas las reducciones posibles para no trabajar con números demasiado grandes
como es 70^7.
Espero esta visión te haya sido de utilidad.
NOTA: Para calcular el resto usando una calculadora, debes conocer el cociente, por ejemplo, si quieres
conocer el residuo de 70^2 cuando divides entre 187 haz lo siguiente:
70^2 = 70×70 = 4900
4900 / 187 = 26.2032... esto significa que el cociente es 26, por lo tanto el resto lo obtienes haciendo
4900 - 26×187 = 38
es decir, lo que obtuviste con este procedimiento sencillo fueron el cociente y el residuo que define el
algoritmo de la división:
4900 = 26×187 + 38
Otra forma de calcular el resto de 70^2 es usando las clases residuales:
[70^2] = [ (5×14)^2 ] = [5^2 × 14^2] = [25] [196]
pero [196] = [196-187] = [9], por lo tanto
[70^2] = [25] [9] = [25×9] = [225] = [225-187] = [38].
Thor
70 a la 7 y luego le sacas el modulo a ese resultado, sino es partir el nuemerador para que no
quede tan grande el resultado, digamos 70 a la 5 * 70 a la 2 y a esa segunda parte le sacas el
mod 187.
Jano
Lo más directo es elevar 70 a 7, 70^7= 8.235.430.000.000 y luego hallas el resto de dividir por
187, que es 60.
Hay casos en que la aritmética modular permite simplificaciones (por ejemplo si el múdulo fuera
con respecto a una cantidad menor que 70 en lugar de 187, entonces bastaría con elevar a 7 el
módulo de 70 por esa cantidad). Pero aquí no es posible por ser 187 mayor que 70 y estar
elevado 70 a un número impar.
Un truco para hallar un resto con la calculadora. Al dividir te resulta un número decimal.
Multiplicas la parte entera por el divisor (187) y restas el resultado del dividendo, también con la
propia calculadora. Así te ahorras trabajo manual.
Recuerda: el resultado es 60.
Kneissel
70^2 (mod 187) = 4900 (mod 187) = 38 (mod 187)
70^7 (mod 187) = (70^2)·(70^2)·(70^2)·70 (mod 187) = 38·38·38·70 (mod 187) = 1444·2660
(mod 187) = 135·42 (mod 187) = 5670 (mod 187) = 60 (mod 187)
Otra forma mas sencilla de hacerlo es mediante el pequeño teorema de Fermat. Un saludo
