Las congruencias fueron introducidas formalmente por K. F. Gauss en su obra Disquisitiones Arithmeticae para estudiar problemas aritméticos relacionados con la divisibilidad, aunque posteriormente se han aplicado a muchos de los problemas de la teoría de números.Sean a y b números enteros y m>0 un número natural. Diremos que a y b son congruentes modulo m si m divide a a-b, y lo designaremos como
a=b (mod m). Por ejemplo, los números que son congruentes a 0 módulo m son exactamente los múltiplos de m. La congruencia es una relación de equivalencia, puesto que verifica las propiedades reflexiva
a=a (mod m), simétricaa=b (mod m) si y solo si b=a (mod m), y transitivaa=b (mod m) y b=c (mod m), entonces a=c (mod m), como se puede comprobar fácilmente.Así podemos agrupar los números enteros en familias disjuntas formadas por los números que son congruentes módulo m; obtenemos exactamente m familias, llamadas las clases de congruencia de m: son las familias de números congruentes con i módulo m variando i entre 0 y m-1.
Por ejemplo, las clases de congruencia módulo 2 son exactamente dos familias, la de los números pares y la de los números impares.
De la misma forma, hay exactamente 3 clases de congruencia módulo 3, formados por los números múltiplos de 3, los números múltiplos de 3 mas 1 y los números múltiplos de 3 mas 2 (o menos 1).Designaremos por Z/mZ (zeta módulo m) las clases de congruencia módulo m; tenemos así, por ejemplo, que
Z/3Z={ 0, 1, 2 }.
Las propiedades más importantes de las congruencias es que respetan la suma y la multiplicación de números enteros:(Ejercicio!).
- Si a=b (mod m) y c=d (mod m), entonces a+c=b+d (mod m)
- Si a=b (mod m) y c=d (mod m), entonces ac=bd (mod m)
Por lo tanto podemos definir una suma y un producto en el conjunto Z/mZ, de forma que obtenemos un anillo: un conjunto con una operación suma que es un grupo conmutativo, una operación producto que es asociativa, con elemento neutro (el 1) y conmutativa, y que cumple la propiedad distributiva.
El primer problema importante a resolver es saber cuales números tienen inverso respecto al producto módulo m y cuales no. Vamos a ver un ejemplo:
Supongamos m=6. Tenemos así que todo número entero es congruente a uno de los números siguientes: 0, 1, 2, 3, 4 y 5. Observemos que 2·3=6=0 (mod 6) y que 3·4 = 12 =0 (mod 6). Por otra parte 5·5=25=24+1=6·4+1=1 (mod 6). Tenemos así que 5 tiene inverso 5 módulo 6 (observando que 5 = -1 (mod 6) esta claro), y en cambio 2, 3 y 4 no tienen inverso módulo 6.
El conjunto de invertibles módulo 6 es así {1,5} y el de no invertibles {0,2,3,4}; estos últimos son exactamente los que tienen algún factor común con 6 y los invertibles los que son primos con 6.En general tenemos
Proposición: El conjunto de elementos de Z/mZ que tienen inverso por la multiplicación corresponde exactamente al conjunto de clases de congruencia de números que son primos con m.
Por ejemplo, para m=10 tenemos que los invertibles módulo 10 son {1, 3, 7, 9}; el inverso de
1 es 1, el inverso de 3 es 7 (ya que 3·7=21=1 (mod 10) ) y el inverso de 9 es 9.No es difícil ver que si a es un elemento invertible módulo m, siempre existe un número natural r tal que ar=1 (mod m); el mínimo número natural r que verifica esta propiedad se llama el orden de a módulo m.
Por ejemplo, si m= 20, y a=17, si tiene queEn efecto, dado que el conjunto de elementos invertibles módulo m forma un grupo respecto la multiplicación, si denotamos por f(n) el número de elementos de este conjunto, entonces podemos tomar r=f(n). Tenemos que17 = -3 (mod 20) de forma que el orden de 17 módulo 20 es 4.
172=(-3)2=9 (mod 20)
173=(-3)3=-27=-7=13 (mod 20)
174=(-3)4=92=81=1 (mod 20)Teorema (Fermat-Euler) Si m>0 es un número natural, sea f(n) es la cantidad de números naturales entre 0 y m que son primos con m:
f(n):={ 0<a<n | a es primo con m }. Entonces para todo número entero a primo con m se tiene queaf(n)=1 (mod m). Por ejemplo tenemos que si p es un número primo f(p)=p-1, ya que todos los números entre 1 y p-1 son primos con p.
Ejemplo: 36 = 729 = 7 · 104 + 1 = 1 (mod 7)En general se tiene queTeorema: Sea m un número natural. Entonces
f(m)= m · P {p primo que divide a m} (1-1/p). Por ejemplo,
f(30)= 30 · (1-1/2) (1-1/3) (1-1/5) = 15 · (1-1/3) · (1-1/5) = 10 · (1-1/5) = 8
y, efectivamente, hay 8 números entre 0 y 30 primos con 30: 1, 7, 11, 13, 17, 19, 23, 29.
Además tenemos que
18=1 (mod 30) , 78=5764801= 192160·30+1=1 (mod 30) ,
118 = 214358881 = 7145296 · 30 +1 =1 (mod 30) ,
138=815730720 = 27191024·30 + 1= 1 (mod 30) ,
178=6975757440 = 232525248·30 + 1 = 1 (mod 30) ,
198=16983563040 = 566118768·30+1=1 (mod 30),
238=78310985280 = 2610366176·30+1=1 (mod 30),
298=(-1)8 = 1 (mod 30),Finalmente tenemos una propiedad muy importante de la función f(n).
Propiedad: Si n y m son dos números enteros primos entre si, entonces f(n·m)=f(n)·f(m).
Por ejemplo, si queremos calcular f(35), dado que 35=7·5, tenemos que
f(35)=f(7)·f(5)=6·4=24
(recordando que f(p)=p-1 si p es un número primo).
Vamos a ver alguna aplicación rápida de las congruencias. Por ejemplo, vamos a demostrar que un número es divisible por 9 si y solo si la suma de sus cifras decimales es divisible entre 9.
Recordemos primero que un número n es divisible entre 9 si y solo siPara finalizar, os propongo un par de ejercicios para resolver usando los resultados anteriores. El primero no es difícil (tenéis que usar el teorema de Fermat-Euler). El segundo es mucho más difícil. Si me mandáis una solución y me gusta la pondré en esta pagina.n=0 (mod 9) Las cifras decimales de n son los números n0, n1, ..., nr entre 0 y 9 tales quen = n0 + 10 · n1 + ... + 10r · nr Dado que10 = 1 (mod 9) tenemos que10r = 1 (mod 9) y por lo tanton = n0 + n1 + ... + nr (mod 9) tal como queríamos ver.
- Calcular las dos ultimas cifras de 13162.
- Demostrar que un numero n es primo si y solo si (n-1)! =-1 (mod n).
