Teoría de números elemental: Congruencias

Después de mi parón por los examenes de Septiembre, aquí vuelvo para dar la puntilla definitiva a mi serie de posts sobre la teoría de números elemental. Así que aquí viene quizá lo más importante (en mi opinión) de la teoría de números elemental, las congruencias.

¿Qué es una congruencia?

Es una relación de equivalencia (no me quiero meter a explicar que es una relación de equivalencia, por eso os pongo el enlace) que cumple la siguiente propiedad:

Sean a, b ∈ Z, m ∈ N, entonces “a” y “b” son congruentes si:

a mod (m) = b mod (m) ó b – a = K·m (siendo K ∈ Z)

Cuando dos números son congruentes se denota de la siguiente manera:

a ≡ b (mod (m))

Definimos “mod” como la operación módulo, que es el resto de la división euclídea de dos números:

r = a mod (m) a = m·q + r

(Más información en Wikipedia)

Conjuntos cocientes

Como las congruencias son relaciones de equivalencia, se pueden definir para cada elemento del conjunto en el que se da la relación, las clases de equivalencia.

La clase de equivalencia de cualquier elemento “a” perteneciente al conjunto “A”, se define como el conjunto:

[a] = {b ∈ A : aRb} (donde R es la relación de equivalencia)

Aplicando esto a los números enteros y a las congruencias, tenemos que:

a ≡ b (mod (m)) en Z tiene como clases de equivalencia a:

[o] = {…., -2·m, -m, 0, m, 2·m, ….}
[1] = {…., 1-2·m, 1-m, 1, 1+m, 1+2m, ….}
….
[m-1] = {…., -1-m, -1, m-1, 2·m-1, 3·m-1, ….}

(Más información en Wikipedia)

Sabiendo ya que son las clases de equivalencia, podemos pasar a explicar qué son los conjuntos cocientes. El conjunto cociente de A por R, se denota A/R, es el conjunto cuyos elementos son las clases de equivalencia por R de los elementos de A, es decir:

A/R = {[a] : a ∈ A}

Aplicando esto a los números enteros y a las congruencias, tenemos que:

Siendo a ≡ b (mod (m)) y sus clases de equivalencia [0], [1], …, [m-1], su conjunto cociente es:

Z_m = {[0], [1], …, [m-1]} [Para los números enteros y las congruencias se denota Z_m en lugar de Z/(mod (m))]

(Más información en Wikipedia)

—

Aunque no quería meterme demasiado en el tema de las relaciones de equivalencia, he tenido que explicar que son las clases de equivalencia y conjuntos cocientes sin haber explicado antes nada de relaciones de equivalencia ni de relaciones binarias, lo he hecho lo más sencillo posible y orientado a las congruencias en lugar de a cualquier relación, así que espero que lo entendáis bien, de todos modos ahí tenéis los comentarios para exponer vuestras dudas.