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))

(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: 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, …
Print Friendly, PDF & Email