Teoría de números elemental: Aritmética modular

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 ∈ Z_m, tal que a + 0 (mod (m)) = a (mod (m))
• Elemento opuesto: Existe un elemento b ∈ Z_m, 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 ∈ Z_m, tal que a · 1 (mod (m)) = a (mod (m))
• Elemento inverso: Existe un elemento a^-1 ∈ Z_m para todo a ∈ Z_m 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))

(Más información en la Wikipedia)

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: X_n+1 = (a · X_n + 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, …

Autor: Fran |  Publicado el 29 de Septiembre de 2006
Categorías: Matemáticas discreta, Números enteros