Aritmética Modular: Congruencias

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:

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

(Ejercicio!).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 a^r=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 que
17 = -3 (mod 20)
17²=(-3)²=9 (mod 20)
17³=(-3)³=-27=-7=13 (mod 20)
17⁴=(-3)⁴=9²=81=1 (mod 20)de forma que el orden de 17 módulo 20 es 4.

En 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 queTeorema (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 quea^f(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:  3⁶ = 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) =  8y, efectivamente, hay 8 números entre 0 y 30 primos con 30: 1, 7, 11, 13, 17, 19, 23, 29.
Además tenemos que

1⁸=1 (mod 30) ,  7⁸=5764801= 192160·30+1=1 (mod 30) ,
11⁸ = 214358881 = 7145296 · 30 +1 =1  (mod 30) ,
13⁸=815730720 = 27191024·30 + 1= 1 (mod 30) ,
17⁸=6975757440 = 232525248·30 + 1 = 1  (mod 30) ,
19⁸=16983563040 = 566118768·30+1=1 (mod 30),
23⁸=78310985280 = 2610366176·30+1=1 (mod 30),
29⁸=(-1)⁸ = 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 si
n=0 (mod 9)Las cifras decimales de n son los números n₀, n₁, ..., n_r entre 0 y 9 tales quen = n₀ + 10 · n₁ + ... + 10^r · n_rDado que10 = 1 (mod 9)tenemos que10^r = 1 (mod 9)y por lo tanton =  n₀ +  n₁ + ... +  n_r (mod 9)tal como queríamos ver.

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

• Calcular las dos ultimas cifras de 13¹⁶².
• Demostrar que un numero n es primo si y solo si (n-1)! =-1 (mod n).

Problema:
                                       p es primo  si y solo si (p-1)! = -1 (mod p)
Solución (de Gastón Andrés Freire de Buenos Aires)
Primera implicación
    · Si p = 2 el resultado es trivial y no hay nada que hacer.
    · Si p es un primo impar : Haré varios pasos muy sencillos.
   1)      2, 3, 4, ........, (p-2) son exáctamente (p-3) elementos inversibles (mod p) cuyos inversos no son sí mismo.
  Se puede probar que los únicos números 1 < a < p-1 tales que a·a = 1 (mod p) son, a saber 1 y (p-1).
   2)   OBSERVACIÓN: (p-3) es un número par.
   3)      Reordenamos los números    2,  3,  4,  5, ..........,  (p-2) en el siguiente orden
                      a₁ , b₁, a₂, b₂, ........., a_(p-3)/2, b_(p-3)/2
          con la propiedad de que para todo 1 < h < (p-3)/2:      a_h · b_h = 1 (mod p), y con todos ellos diferentes.
    Tenemos que
   2·3·4·5·........·(p-2) =  (a₁·b₁)·(a₂· b₂)· .........· (a_(p-3)/2 · b_(p-3)/2 ) = 1 (mod p)
    pues lo único que hice fue reordenar los factores del producto.
     4)   Entonces  (p-1)! = 1·(2·3·4·5·..........·p-2)·(p-1) = (p-1) (mod p)
            Como (p-1) es el (-1) modulo p, hemos probado entonces que:
          Si p es primo, entonces (p-1)! = -1 (mod p)
 Segunda implicación:
OBSERVACION: Usaré el simbolismo p \ h para decir que p divide a h.
   Supongamos que (p-1)! = -1 (mod p), es decir que p \ (p-1)!+1
   Si existiera un 1 < h < p tal que h \ p, como p \ (p-1)!+1, entonces   h \ (p-1)!+1
   Pero seguro que h \ (p-1)! (por ser 1<h<p-1). Por lo tanto h \ 1, que no puede ser.
   LUEGO: Si (p-1)! = -1 (mod p), entonces p es primo.


Teorema:
(n-1)!=-1 (mod n) si y solo si n es primo


Demostración (por Miguel Ángel Ochando, de Barcelona):

1. Si n es primo (n-1)!=-1 (mod n)

Sea n un número primoSean k, a, b números naturales tales que 0 < k, a, b < n

a) Como n es un número primo, todo k tiene inverso que se denota por k^-1, tal que k·k^-1=1 (mod n), y 0<k^-1<n .b) Dos números diferentes a y b no pueden tener el mismo inverso. Supóngase que lo tienen y lo denotamos por x: b.1) a·x=1 (mod n) b.2) b·x=1 (mod n) b.3) (a-b)·x=0 (mod n) O bien x=0 (mod n), o bien (a-b)=0 (mod n). x no puede ser 0 (mod n) porque a·x=a·0=0 (mod n) contradice (b.1) Si (a-b)=0 (mod n) entonces a=b, que contradice la premisa inicial de que a y b son números diferentes. c) k cumple que k^-1=k si y solo si k=1 o k=n-1 Supóngase que existe un k tal que k·k=1 (mod n) c.1) k²-1=0 (mod n) c.2) (k+1)·(k-1)=0 (mod n) Si (k+1)<n y (k-1)>0, (c.2) es imposible porque n no divide ni a (k+1) ni a (k-1). Por tanto (c.2) solo es posible si k+1=n o si k-1=0Como (n-1)!=1·2·3·...·(n-3)·(n-2)·(n-1)Por (a) y (b) se sabe que los factores de (n-1)! se pueden agrupar por parejas de manera que cada factor se encuentre al lado de su inverso, en total se formarían (n-3)/2parejas. Por (c) (n-1) y 1 se quedarían sin emparejar por ser ellos mismos su propio inverso. Por tanto:     

2. Si n no es primo y n>4, (n-1)!=0 (mod n)
p es un número primo n es un número natural no primo k, m son números naturales Existen dos posibilidades:
1. n se puede escribir como producto de m (1<m<n) potencias de números primos:
Cada potencia es un número natural menor que n y, como todas las potencias son diferentes entre si, resulta que todas ellas estan contenidas en el producto (n-1)!, y por tanto este producto es divisible entre n
2. n se puede escribir como una única potencia p^k de un número primo:

• Si k>2, n=p^k=p·p^(k-1)tanto p como p^(k-1) son números naturales menores que n y por tanto están incluidos en el producto factorial de (n-1) y en consecuencia los dos dividen a (n-1)!
• Si k=2 i p>2, n=p². Para que n divida a (n-1)! ha de cumplirse que p²>2·p, en este caso (n-1)! contendrà a p y a 2·p como factores y serà divisible por p². p²>2·p si i solo si p>2.
• Si k=2 y p=2. Entonces nos encontramos en el caso nº 3.

3. n=4, (4-1)!=3!=6=2 (mod 4)

Fuente: http://usuarios.multimania.es/teoriadenumeros/modular.html