Matematica Modular

CONGRUENCIAS

Se dice que dos enteros a y b son congruentes módulo m si la diferencia de a y b es divisible por m, y se emplea la notación: a b mod m. Esta definición equivale a decir que a y b dan el mismo resto al ser divididos por m.

Propiedades

i) Si dos números son congruentes con un tercero son congruentes entre sí.

ii) a 0 mod m quiere decir que a es múltiplo de m.

iii) Si a b y c d; entonces a + c b + d; a – c b – d y ac bd (todas mod m).

iv) a b mod m na nb mod m. Es decir, podemos multiplicar sin problemas en congruencias.

v) Si na nb mod m y n es primo con m; entonces a b mod m. Es decir, podemos dividir sin problemas en congruencias por números primos con el que indica la congruencia. Por ejemplo, 14 4 mod 5 7 2 mod 5 (por ser 2 primo con 5)

 Sin embargo, si el número por el que dividimos no es primo con el que indica la congruencia la propiedad anterior no es cierta.

Por ejemplo, 14 4 mod 10; pero sin embargo 7 y 2 no son congruentes entre sí, módulo 10 (al no ser 2 primo con 10).

Pero existe otra propiedad que permite dividir en este caso:

vi) Si na nb mod m y d es el mcd(n, m); entonces a b mod (m/d):

Así, 14 4 mod 10 7 2 mod 5

Otro ejemplo que puede ayudar a aclarar esta propiedad es el siguiente:

28 8 mod 10 7 2 mod(10/2) = mod 5 (al ser el mcd(4,10) = 2).

Otra forma de proceder, si hay problemas con esta propiedad, es pasando a ecuaciones diofánticas y utilizando la propiedad v: 28 8 mod 10 28 = 8 + 10y, que se puede simplificar entre 2, quedando: 14 = 4 + 5y 14 4 mod 5 y, por la propiedad v, entonces 7 2 mod 5.

vii) Si a b mod m an bn mod m. El recíproco no tiene por qué ser cierto.

Por ejemplo: 72 52 mod 3 y sin embargo 7 y 5 no son congruentes modulo3.

viii) Para calcular una potencia, an, módulo m, podemos poner un número congruente con la base, a, pero no del exponente.

...