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