Congruencias

Fecha de primera versión: 11-03-01
Fecha de última actualización: 11-03-01

Los números a los que nos referimos en esta página son números enteros.

Se dice que dos números  a y b son congruentes respecto a un tercero, n, llamado módulo si los restos de la división de a/n y b/n son iguales.

Hay varias notaciones para representar las congruencias. Una de ellas es:
a = = b (mod n)

De la definición de congruencia se deriva la siguiente propiedad:

Si a y b son congruentes módulo n, la diferencia entre a y b es un múltiplo de n.

La demostración es muy sencilla:
a - b = kn.

a = k1n + r1
b = k2n + r2

Restando, a - b = n(k1 -  k2) = nk
Recíprocamente, si la diferencia de dos números es múltiplo de un tercero, dichos números son congruentes respecto del tercero.

Si a = = b (mod n) y b = = c (mod n), a = = c (mod n).

Demostración: Sean los restos de las divisiones de a, b y c entre n r1, r2 y r3.

Si r1 = r2 y r2= r3 entonces r1 = r3 o lo que es lo mismo a = = c (mod n).

Clase de restos

Al conjunto de los números que, al ser divididos por n dan el mismo resto, r, se le llama clase de resto r módulo n, y se representa por C(r).

Evidentemente cada clase de resto es una progresión aritmética de razón n. 

Adición de congruencias

Sumando dos congruencias respecto del mismo módulo, se obtiene otra congruencia respecto del mismo módulo.

Multiplicación de congruencias

Multiplicando dos congruencias respecto del mismo módulo, se obtiene otra congruencia respecto del mismo módulo.

De esto se deriva que a = = b (mod n), an = = bn (mod n)

Esta propiedad es muy importante, pues muchos problemas hacen uso de esta propiedad.

Demostrar que 64328 = = 1 (mod 9) . si lo ponemos de esta forma 64328 = = 1328 (mod 9) lo veremos más claro. Entonces 64 = = 1 (mod 9), porque el resto del cociente 64/9 es 1.

División de congruencias

El cociente de una congruencia respecto a un módulo n, por otro número m, sólo da otra congruencia cuando m y n son primos entre si.

Pequeño teorema de Fermat

El pequeño teorema de Fermat dice que si p es primo y a es un entero ap = a (mod p). Dicho en palabras claras: El resto de dividir ap entre p y el resto de dividir a entre p son iguales.  

Dividiendo ap = a (mod p) por a nos queda ap-1 = 1 (mod p), que es la forma que se utiliza para probar si un número es primo.

Este teorema también se llama teorema de Euler-Fermat, se utiliza en problemas de este tipo:

Calcular el resto de dividir 31895243 entre 13.

De la aplicación del teorema deducimos que 3112=1 (mod 13).

895243 = 74603 * 12 + 7.

31895243 = 31(74603*12 +7)= (3112)74603 * 317

Recordemos que queremos calcular el resto de dividir este número entre 13. El resto será el producto de los restos de los dos factores.

Como el resto de dividir 3112 entre 13 es 1, el resto del primer factor será 1, por lo tanto el resto de (3112)74603 * 317 será el resto de 317 . Vamos a calcular el resto de dividir 317 entre 13.

Como 31 = 13*2 + 5, 57 tendrá el mismo resto que 317 al dividirlo por 13.

Vamos a calcular el resto de dividir 57 entre 13. Como 7 = 4 + 2 + 1, 57 = 54*52*5

El resto de 5/13 es 5

El resto de 52/13 es 12 (o -1)

El resto de 54/13 es 1

El resto de 54*52*5 será 1*12*5 = 1*(-1)*5 = -5 = 8