Congruencias

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

En 1801 Gauss publicó su famoso libro Disquisiciones Aritméticas.  En la sección dedicada a la teoría de números introdujo el término congruencias para resolver problemas de divisibilidad.

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

En sentido contrario dos números a y b se dicen incongruentes respecto a un tercero n, llamado módulo, si los restos de la división de a/n y b/n son distintos.

Evidentemente los restos posibles de la división por n es el conjunto formado por los números desde el cero hasta n-1.

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

Operaciones con congruencias

Sea a == b (mod n) y c == d (mod n). Sea k un numero entero.

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

a + c == b + d (mod n)
a - c == b - d (mod n)

Si a una congruencia le sumamos un número k NO se mantiene la congruencia: a + k =/= b + k (mod n)

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

a . c == b . d (mod n)

De esta propiedad se deriva am == bm (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.

Si a una congruencia la multiplicamos por un número k NO se mantiene la congruencia: a . k =/= b . k (mod n)

La división, NO mantiene la congruencia: a / c =/= b / d (mod n)

Si a una congruencia la dividimos por un número SÓLO mantiene la congruencia cuando k y n son primos entre si: a/k == b/k (mod n). SÓLO CUANDO K Y N SON PRIMOS ENTRE SÍ.

Exponenciación de dos congruencias respecto del mismo módulo , obtiene otra congruencia respecto del mismo módulo.

ac == bd (mod n)
 

Propiedades

Si a y b son congruentes respecto a varios módulos n1, n2,... entonces a y b son congruentes respecto al mínimo común múltiplo.

Si a y b son congruentes respecto a n entonces a y b también son congruentes respecto a todos los divisores de n.

Si a y b son congruentes respecto a n y k divide a a, b y n, entonces a/k == b/k (mod n/k).

Si a y b son congruentes respecto a n y k es primo con n, entonces a/k == b/k (mod n).

Si a == b (mod n) y el mcd (k, n) = d, entonces a/k == b/k (mod n/d).

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

Congruencias con nombre propio

Congruencia de Fermat: es la que vimos antes. ap-1 == 1 (mod p). Siendo p primo.
Congruencia de Euler: es una generalización de la congruencia anterior. af(n) == 1 (mod n). Siendo f(n) la función de Euler.
Congruencia de Wilson: (p-1)! + 1 == 0 (mod p). Siendo p primo.