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