Congruencia

8.8 Congruencias

8.8.1 Introducción

Si escribimos los números del 1 al 24 en filas de a cuatro de la forma siguiente:

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

17 18 19 20

21 22 23 24

Podemos observar las siguientes características:

a). La resta de dos números de una misma columna es divisible por 4.

b). Los números situados en cualquier columna dejan el mismo residuo al ser divididos por 4.

c). Estos residuos, resultantes al dividir cualquier número por cuatro son 0 o 1 o 2 o 3.

Una situación bastante similar se presenta si escribimos los mismos números en filas de a cinco, con la diferencia de que los residuos serían los obtenidos al dividir el número por 5.

La situación se torna más general si se colocan n enteros consecutivos formando filas de m elementos con m < n.

En el ejemplo anterior los números 11 y 19 tienen la propiedad de que la diferencia entre ellos es divisible por 4; como ello ocurre, se dice entonces que 11 es congruente con 19 módulo cuatro.

El ejemplo visto sirve para motivar la siguiente definición.

8.8.2 Definición. Sea n un entero positivo fijo. Dos enteros a y b se dice que son congruentes módulo n y se denota por:

a b mod n.

Si n divide a la diferencia a - b; es decir, si n|(a - b).

Ejemplo 45.

63 0 mod 3 porque 3| (63-0)

7 -1 mod 8 porque 8| (7-(-1))

27 2 mod 5 porque 5| (27-2)

Ejemplo 46.

La congruencia módulo 1 es siempre válida porque 1 es divisor de todos los números enteros.

8.8.3 Definición. Si n > 0 no divide a b menos c, se dice entonces que b y c son incongruentes módulo n y se escribe como b c mod n.

8.8.4 Teorema. Sean a y b enteros arbitrarios. Entonces a b mod n si y sólo si dejan el mismo residuo al ser divididos por n.

Demostración.

Suponga que a b mod n.

Luego n(a b), que quiere decir que a - b = kn para algún entero k.

Como b y n son enteros, por el algoritmo de la división b = qn + r para algún entero q, con 0 r < n. Es decir r es el residuo al dividir b por n.

Veamos que r es también el residuo cuando se divide a por n.

Como a - b = kn, luego a = kn + b o sea que a = kn + qn + r = (k+q)n + r. Es decir, a deja residuo r al ser dividido por n.



Suponga que a y b dejan el mismo residuo al ser divididos por n, es decir:

a = q1n + r.

b = q2n + r.

Restando se obtiene a - b = (q1 - q2)n, es decir, n(a  b).

8.8.5 Teorema. La relación de congruencia módulo n cumple las siguientes propiedades:

a). a a mod n. para todo entero a.

b). Sí a b mod n., entonces b a mod n, para todo par de enteros a y b.

c). Sí a b mod n y b c mod n, entonces a c mod n para toda terna de enteros a, b y c.

8.8.6 Teorema. a b mod n y c es un entero, entonces a+c b+c mod n.

Demostración

Sí a b mod n, entonces existe un entero k tal que a=b+kn.

Luego a + c = b + kn + c. esto es, (a+c) = (b+c) + kn. Y por la definición de la relación de congruencia a+c b+c mod n.

Ejemplo 47.

Como -5 16 mod 7 entonces -5+a 16+b mod 7 para a Z. En particular, si a=8, -5+8 = 16+8 mod 7, esto es 3 24 mod 7.

8.8.7 Teorema. Si a b mod n y c es un entero, entonces ac bc mod n.

Demostración Sí a b mod n, entonces existe un entero k tal que a=b+kn.

Luego ac=(b+kn)c. Esto es, ac=bc + (kc)n. Como kc es un entero, por la definición de relación de congruencia, tenemos ac bc mod n.

Ejemplo 48.

Como 12 3 mod 9, 12a 3a mod 9 para toda a Z.

En particular, sí a = 6, 12 x 6 3 x 6 mod 9, es decir, 72 18 mod 9.

8.8.8 Teorema. Sí a b mod n y c d mod n, entonces:

a+c b+d mod n.

ac db mod n.

Para ilustrar el teorema anterior, considere las congruencias

30 8 mod 11.

13 2 mod 11.

Según el teorema anterior

30+13 8+2 mod 11.

43 10 mod 11.

De otra parte

30x13 8x2 mod 11

390 16 mod 11.

Bajo la relación de congruencia módulo n, el conjunto de enteros es partido en n conjuntos distintos llamados clases de equivalencia.

Estas clases de equivalencia son llamadas a menudo clases residuales módulo n. Una clase residual módulo n consta de los enteros que son congruentes entre sí módulo n. Por ejemplo, bajo la relación de congruencia módulo

...