11.-Congruencias

En muchos problemas, la idea central para encontrar la solución es considerar los residuos de los números que se relacionan al dividirse entre otro número fijo. Esto nos llevara a desarrollar la noción de congruencias de números, la cual unifica y extiende muchos resultados desarrollados hasta ahora.
Congruencias
Definición. Sean a y b dos números enteros, y sea m un entero distinto de cero. Decimos que a es congruente a b módulo m si m divide a b-a. Esto lo escribimos como
a ≡ b (mod m) ⇔ m | b-a.
A grandes rasgos lo que decimos es que dos números a y b son congruentes (equivalentes, iguales) módulo m si ambos son de la forma mk +r con una misma r, esto es, si dejan el mismo residuo al dividirse por m . Para decir que a no es congruente a b modulo m escribimos

Ejemplos.
8 ≡ 23 (mod 5) puesto que 5 |(23-8)= 15 Notemos que tanto 23 y 5 son de la forma 5k +3.
36≡0 (Mod 12) puesto que 12 |(36-0)=36.
-22≡ 6 (mod 7) dado que 7|(6 –(-22))= 28.
Las ventajas de usar congruencias es que estas comparten muchas propiedades con la igualdad (de ahí que sea apropiado decir que los números son “congruentes”) ;
Si a,b,c,d,n son enteros y n ≠ 0 entonces :
I.-. a ≡ a (mod n)
II.- Si a ≡ b (mod n ) entonces b ≡ a (mod n)
III.- Si a ≡ b (mod n) y b ≡ c (mod n) entonces a ≡ c (mod n).
IV.-Si a ≡ b (mod n) entonces a +x ≡ b + x (mod n) para todo entero x
V.-Si a ≡ b (mod n) y c ≡d (mod n) entonces ( a +c)≡ (b +d) (mod n)
VI.- Si a ≡ b (mod n) entonces ax ≡ bx (mod n) para todo entero x
VII.-Si a ≡ b(mod n) y c ≡ b (mod n) entonces ac ≡ bd (mod n)
VIII.-Si a ≡ b (mod n) entonces a^x ≡b^x (mod n) para x ∈Z+
IX.- Si f(x) es un polinomio de coeficientes enteros, entonces a ≡b (mod n) implica que f (a) ≡ f(b) (mod n)
X.-Si a ≡b (mod n) y d |n entonces a ≡b (mod d).
XI.- Si a ≡b (mod m), a ≡b (mod n)y (m,n) = 1 entonces a ≡b (mod mn)
XII.-a ≡0 (mod n) si y solo si n| a.
El teorema anterior se prueba a partir de los teoremas de divisibilidad. Como ejemplo a ≡b (mod n) entonces a+x ≡ b+x (mod n).
Prueba a ≡b (mod n) quiere decir que n |(b-a). Pero b-a = b +x+a-x=(b+x) - (a+x) por lo que n |(b+x) –(a+x), lo que significa que a+x ≡b+x (mod n).
Hay sin, embargo, una propiedad que la igualdad no comparte con la congruencia. Si ax =bx , con x no igual a cero podemos decir que a =b , pero con las congruencias no. Por ejemplo 10×6 ≡ 4×6 (mod 4) pero
Es decir, no se permite cancelar factores en las congruencias. El siguiente teorema nos proporciona condiciones para poder efectuar tal operación.
Teorema 11.2 Sean a,b enteros. Entonces

II.-Si ax ≡ bx (mod n) y (n,x)=1 entonces a ≡ b(mod n ).
III.- a≡ b (mod n_k) para k =1,2,…r si y sólo si a≡ b (mod [n₁,n₂,...n_r]).
Prueba. Si ax ≡ bx (mod n) entonces bx-ax= nz para algún entero z. Entonces

Y por tanto


Pero
Por lo que

divide a b-a, es decir,
De este modo hemos probado que ax ≡ bx (mod n)implica
Ahora, supongamos que
Esto quiere decir que
De donde (b-a)(n,x)=nz, es decir ,n |(b-a)(n,x). Pero x es un múltiplo de (n,x) lo cual nos dice que n |(b-a)x. Se sigue que ax ≡ bx (mod n).Ya hemos probado el primer inciso, el segundo es una aplicaciòn directa del primero.Para probar el tercero, notemos que n_i| (b-a) nos dice que (b-a) es un múltiplo comùn de todas las n_i, por lo que [n₁,n₂,...n_r ] |b-a.Ya queda probado que a ≡b (mod n_k) (k=1...r) implica a≡ b(mod[n₁,n₂,...n_r])
Para el regreso , notemos que n_k es un divisor de [n₁,n₂,...n_r], por lo que a ≡ b (mod [n₁,n₂,...n_r )]implica a≡ b (mod p)
Un caso muy especial y útil del teorema anterior es el siguiente resultado:
Teorema 11.3 Sea p un número primo y t un número que no es divisible entre p. Si at ≡ bt (mod p) entonces a ≡b (mod p).
Para ilustrar el uso de congruencias al resolver problemas, demostraremos el siguiente teorema:
Teorema 11.4. Si a es impar, entonces a²-1 es divisible entre 8.
Prueba .Si a es impar, entonces alguna de las siguientes proposiciones es cierta.
a ≡ 1 (mod 8)
a ≡ 3 (mod 8)
a ≡ 5 (mod 8)
a ≡ 7 (mod 8)
Por otro lado 1² ≡ 1 (mod 8),3² ≡ 1 (mod 8),5²≡1 (mod 8), 7² ≡1 (mod 8) , por lo que en cualquier caso, a² ≡ 1 (mod 8), lo que es lo mismo que decir a²-1 es divisible entre 8.
Una prueba ligeramente distinta:
Prueba. Supongamos que a es impar es decir , a≡ 1 (mod 2). Entonces
a² ≡ 1² ≡1 (mod 2).
Por otro lado, si a²-1 no fuese divisible entre 8 tendríamos

Y como 2 8 esto implicaría que
Esto es una contradicción , por lo que concluimos que a²-1 debe ser divisible entre 8.
Los teoremas principales sobre divisibilidad pueden formularse con congruencias. El teorema 10.15 se enuncia:
Teorema 11.5 Si p es primo, ab ≡ 0 (mod p) y

entonces b ≡0 (mod p).
El teorema anterior es el análogo (para la igualdad) de la afirmación ab = 0 entonces a=0 o b =0 . Es importante recalcar que el módulo debe ser primo. Como ejercicio, encontrar un contraejemplo cuando el número no es primo.
El teorema que dice que si a = bq +r entonces (a,b) = (b,r) puede rescribirse como
Teorema 11.6 Si x ≡y (mod n) entonces (x,n) =(y,n)
Para terminar , es importante recalcar que aunque los resultados de congruencia se puedan rescribir como resultados de divisibilidad y viceversa, las congruencias generalmente permiten realizar pruebas más claras y concisas, además de que familiarizarse con ellas permite entender resultados más profundos y poderosos. Por esto es que se recomienda especialmente que en lo posible se intente usar congruencias en vez de divisibilidad para resolver los problemas.