Algoritmo de Euclides y Congruencias Modulares

Decimos que dos números enteros \(a\) y \(b\) son congruentes módulo \(m \) si \(m \) divide a su diferencia, \(a-b\), es decir \(m|(a-b)\). Nota: siempre tomamos a \(a\) como el mayor de los dos números, de manera que \(a-b\) sea un número positivo. Podemos escribirlo algebraicamente como \(a ≡ b (mod \) \( m) \). Escribimos \(a \% m \) para denotar al residuo que resulta de dividir \(a \) entre \(m\). En particular resulta que \(a ≡ b (mod \) \( m) \) si y solo si los residuos de las divisiones \( \frac{a}{m} \) y \( \frac{b}{m} \) coinciden, es decir \(a \% m=b \% m \).

Veamos un ejemplo: \(47\) y \(31\) son congruentes módulo \(8\) pues \(47-31=16\). Esto es, \(47≡31 (mod \) \(8) \) porque \(8\) divide a \(16\), que es la diferencia entre \(47\) y \(31\). Como puedes observar, en este caso \(a=47\), \(b=31\) y \(m=8\), y tenemos que los residuos de dividir \(47\) entre \(8\) y \(31\) entre \(8\) son iguales: \(a \% m=47 \% 8=7 \) y \(b \% m=31 \% 8=7 \), pues \(47=5(8)+7\) y \(31=3(8)+7\).

Observa que, si \(d = MCD(a,b) \), entonces \(a ≡ b \ (mod \ d) \), puesto que si \(d \) es divisor de \(a\) y de \(b \), entonces \(d \) divide a su diferencia. Y si \(d \) divide a \(a-b \) y divide a uno de estos números, entonces \(d \) divide al otro, y por lo tanto va a ser un divisor común. Entonces tenemos el siguiente teorema:

Si \(d = MCD(a,b) \) entonces \(a ≡ b \ (mod \ d) \)

Sin embargo el converso no es cierto: si \( a ≡b \ (mod \ n) \), \(n \) no necesariamente es un divisor común de \(a \) y de \(b \), para ver esto, basta encontrar un contraejemplo o utilizar el algoritmo de Euclides auxiliándonos con la Pizarra Euclídea (escena tres de la sección Desarrollo). Nota: si tenemos que una proposición \(p\) implica otra proposición \(q\), es decir \(p ⇒ q\), entonces su converso es la implicación \(q ⇒ p\).

En la tercera escena de la sección Desarrollo si escribes \(d \), el \(MCD(a,b) \), en el campo de texto \(n \), podrás verificar que \(a≡b \ (mod \ d) \). Sin embargo, si consideras divisores de \(a-b \) diferentes de \(d=MCD(a, b) \), puedes encontrar \(n \) tal que \(a≡b \ (mod \ n) \) donde \(n \) no es divisor común de \(a \) y \(b \). Hay algunos números \(n \) que pueden ser divisores comunes de \(a \) y \(b \), pero hay otros números \(n \) que no lo son. Para encontrar estas últimas, en la escena antes mecionada realiza lo siguiente:

1. Encuentra \(a,b \) tal que \(MCD(a,b) > 1\).
2. Escribe el \(MCD\) en el campo de texto \(d \). Empieza de nuevo si \((a-b)/d = 1 \).
3. Si \(n=(a-b)/d>1 \), escríbelo en el campo de texto \(d \).
4. Si los residuos \(a \% m\), \(b \% m, \) son iguales, es decir \(a \% m = b \% m \), pero diferentes de \(0 \), tenemos dos números congruentes módulo \(n \), y \(n \) no es un divisor común de \(a\) y \(b\) porque los residuos son diferentes de \(0 \).

Si pasa todo lo anterior, entonces \(n \) no es el \(MCD(a,b)\) y habremos encontrado el contraejemplo que buscábamos.

Veamos un ejemplo del procedimiento anterior en donde existen números \(n \) que pueden ser divisores comunes de \(a\) y de \(b \) y otros no. Considera los números \(a = 8\times 3\times 5\times 7\) y \(b=2\times 3\times 5\times 7\times 19\). Puedes verificar que \(MCD(a,b) = 2\times 3\times 5\times 7\), \( n = \frac{a-b}{d} = 3\times 5 \), así que \(n \) es, claramente, divisor común de \(a, b \). Sin embargo, el procedimiento anterior nos ayuda a encontrar \(n \) que no es divisor común. Considera \(a = 2\times 3\times 5\times 7, b=2\times 7\times 7\times 11\). Puedes checar que \(MCD(a,b) = 2\times 7, n = (b-a)/d = 2\times 31\) y por lo tanto \(n \) no es divisor común de \(a, b \).