Clases de Congruencia

Teoría

Una clase de congruencia (o clase de residuo) módulo $n$ es el conjunto de todos los enteros que son congruentes a un entero específico $a$ módulo $n$. En aritmética modular, puedes decir que dos enteros $a$ y $b$ son congruentes módulo $n$, y lo escribes como $a \equiv b \pmod n$, si su diferencia $a-b$ es divisible entre $n$. Esta relación divide al conjunto infinito de los enteros $\mathbb{Z}$ en exactamente $n$ conjuntos ajenos, llamados clases de congruencia. Por ejemplo, módulo 3, los enteros se dividen en tres clases: los números que dejan un residuo de 0 (múltiplos de 3), los números que dejan un residuo de 1 y los números que dejan un residuo de 2.

Este concepto es fundamental en teoría de números porque te permite tratar conjuntos infinitos de números como si fueran un solo objeto matemático. En lugar de hacer aritmética con enteros arbitrariamente grandes, haces aritmética con estas clases (que muchas veces representas con su miembro no negativo más pequeño, o sea, el residuo). Esto crea la estructura algebraica $\mathbb{Z}n$ (los enteros módulo $n$). Si quieres determinar el último dígito de una potencia gigante como $7^{2023}$, en realidad estás trabajando con la clase de congruencia de $7^{2023}$ en $\mathbb{Z}{10}$.

El poder de las clases de congruencia está en que la suma y la multiplicación están "bien definidas" en estos conjuntos. Esto significa que si tomas cualquier elemento de la clase $A$ y lo sumas con cualquier elemento de la clase $B$, el resultado siempre va a caer en la misma clase resultante $C$. Esta consistencia te permite resolver ecuaciones diofánticas, establecer reglas de divisibilidad y analizar comportamientos cíclicos en sucesiones sin preocuparte por el tamaño específico de los números involucrados.

Fórmulas Clave

Definición de una Clase de Congruencia La clase de congruencia de un entero $a$ módulo $n$, la denotas como $[a]_n$ o simplemente $[a]$, y es el conjunto: $$ [a]_n = { x \in \mathbb{Z} \mid x \equiv a \pmod n } = { a + kn \mid k \in \mathbb{Z} } $$

El Conjunto de los Enteros Módulo $n$ El conjunto de todas las clases de congruencia módulo $n$ lo denotas por $\mathbb{Z}_n$ (o $\mathbb{Z}/n\mathbb{Z}$): $$ \mathbb{Z}_n = { [0], [1], [2], \dots, [n-1] } $$ Este conjunto forma un sistema completo de residuos, lo que significa que cada entero pertenece exactamente a una de estas clases.

Operaciones de Aritmética Modular Las operaciones aritméticas en las clases de congruencia las defines usando enteros representantes. Para las clases $[a]$ y $[b]$ en $\mathbb{Z}n$: $$ [a] + [b] = [a + b] $$ $$ [a] - [b] = [a - b] $$ $$ [a] \cdot [b] = [a \cdot b] $$ $$ [a]^k = [a^k] \quad \text{para } k \in \mathbb{Z}{\ge 0} $$

Propiedad de Partición Las clases de congruencia parten a los enteros: $$ \bigcup_{r=0}^{n-1} [r]_n = \mathbb{Z} \quad \text{y} \quad [a]_n \cap [b]_n = \emptyset \iff a \not\equiv b \pmod n $$

Demostración

Teorema: La congruencia módulo $n$ es una relación de equivalencia.

Demostración: Para demostrar que la congruencia módulo $n$ define clases de congruencia válidas (conjuntos que parten a los enteros), tienes que mostrar que la relación $\equiv$ es una relación de equivalencia. Una relación de equivalencia debe cumplir tres propiedades: Reflexividad, Simetría y Transitividad.

Recuerda la definición: $a \equiv b \pmod n$ si y solo si $n \mid (a - b)$.

1. Reflexividad Tienes que mostrar que $a \equiv a \pmod n$ para cualquier entero $a$. Considera la diferencia $a - a = 0$. Como $n$ divide a 0 (ya que $0 = n \cdot 0$), tienes que $n \mid (a - a)$. Por lo tanto, $a \equiv a \pmod n$.

2. Simetría Tienes que mostrar que si $a \equiv b \pmod n$, entonces $b \equiv a \pmod n$. Supón que $a \equiv b \pmod n$. Por definición, $n \mid (a - b)$. Esto implica que existe un entero $k$ tal que $a - b = nk$. Si multiplicas por $-1$, obtienes $-(a - b) = -nk$, lo cual se simplifica a $b - a = n(-k)$. Como $-k$ es un entero, $n$ divide a $b - a$. Por lo tanto, $b \equiv a \pmod n$.

3. Transitividad Tienes que mostrar que si $a \equiv b \pmod n$ y $b \equiv c \pmod n$, entonces $a \equiv c \pmod n$. Supón que $a \equiv b \pmod n$ y $b \equiv c \pmod n$. Por definición:

1. $a - b = nk$ para algún $k \in \mathbb{Z}$.
2. $b - c = nj$ para algún $j \in \mathbb{Z}$. Quieres encontrar la relación entre $a$ y $c$. Suma las dos ecuaciones: $$ (a - b) + (b - c) = nk + nj $$ $$ a - c = n(k + j) $$ Como $k$ y $j$ son enteros, $k+j$ es un entero. Así que $n$ divide a $a - c$. Por lo tanto, $a \equiv c \pmod n$.

Conclusión Como la relación cumple con reflexividad, simetría y transitividad, la congruencia módulo $n$ es una relación de equivalencia. Por consecuencia, las clases de equivalencia (clases de congruencia) definidas por esta relación forman una partición del conjunto de los enteros $\mathbb{Z}$. $\square$