Congruencia (aritmética superior)

La congruencia, en la aritmética superior o teoría de números, es una relación que nos permite comparar dos números enteros, mediante sus restos al dividirlos por un tercer número entero fijo. Este es diferente a cero y a uno. De preferencia es un número entero positivo.

Definición

Sea k un número natural. decimos que c y d son congruentes módulo k si su diferencia c-d es múltiplo de k. para denotar esto usamos la notación

c := d (mod k)

Por ejempo: 18 := 14 (mod 4); 44 := 24 (mod 5);

Evidentemente c:= d (mod k) s.s.s. existe s entero tal que c = d + sk

Teorema

c := d (mod k) si sólo si las divisiones de c y d por k proveen un mismo residuo

Para este caso, las divisiones de 31 y 47 por 4 dan el mismo residuo, por lo tanto 31 := 47 (mod 4)

Propiedades

1. La relación de congruencia es reflexiva: c := c (mod k).

2. La relación de congruencia es simétrica: c := d (mod k) → d := c (mod k)

3. La relación de congruencia es transitiva:

c := d (mod k) y d := e (mod k) → c := e (mod k)

4. si c := d (mod k) y e := f (mod k) entonces c + e := d + f (mod k), compatible con la suma

5. cuando c := d (mod k) y e := f (mod k) entonces c·e := d·f (mod k), compatible con el producto

6. si c := d (mod k) entonces si c×l := d×l (mod k) para cualquier l entero, no altera al multiplicar por un factor constante

7. supuesto c := d (mod k) entonces si c^p := d^p (mod k), aquí p es número natural. Compatible con la potenciación de exponente natural

8 cuando c := d (mod k) y Q(y) es un polinomio con coeficientes enteros , se deduce que Q(c) := Q(d)

Partición

Como la relación congruencia módulo k es reflexiva, simétrica y transitiva determina una partición en el conjunto Z de los enteros en k clases de equivalencia, de modo que

Cualquier número entero está en una clase y sólo una.

Si c := d (mod k) entonces c y d están en la misma clase de equivalencia

La unión de todas las k clases de equivalencia es igual al conjunto Z de todos los números enteros.

Denominación

las clases de equivalencia que determina una congruencia módulo k, se llaman las clases de restos módulo k

si consideramos la congruencia módulo 5, hay cinco clases de restos módulo 5: los que dan resto 0, 1, 2, 3 y 4

Por ejemplo en la clase de resto 1, módulo 5 están los enteros de la forma x = 5k+1

Empleo

• Para marcar las horas del día utilizamos los restos de división entre 24
• Al clasificar los enteros en pares e impares usamos los restos de división entre 2.
• En el estudio de los primos gaussianos nos interesan la congruencia módulo 4.

Fuentes

• Enzo Gentile: Aritmética elemental
• Ózhigova. ¿Qué es la teoría de números?

Consúltese además

• Divisibilidad
• Relación de equivalencia