Algoritmo de Euclides y Congruencias Modulares

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\), esto lo podemos escribir 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.


Observa que, si \(d = MCD(a,b) \), entonces \(a ≡ b \ (mod \ d) \), puesto que si \(d \) es divisor de \(a, b \), entonces \(d \) divide a su diferencia. También, si \(d \) divide a \(a-b \) y divide a uno de estos números, entonces \(d \) va a dividir al otro y por lo tanto va a ser un divisor común.


Si \( a ≡b \ (mod \ n) \) entonces \(n \) no 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 Euclidea.


Si escribes \(d \), el MCD de \(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 \). Unas \(n \) pueden ser divisores comunes de \(a \) y \(b \) pero hay otras \(n \) que no lo son. Para encontrarlas:

  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, i.e., \(a \% m = b \% m, \), pero diferentes de \(0 \), tenemos 2 números congruentes módulo \(n \), donde \(n \) NO es divisor común porque los residuos son diferentes de \(0 \).
Entonces \(n \) NO es el MCD y hemos encontrado el contraejemplo que buscábamos.


Para ver que con el procedimiento anterior unas \(n \) pueden ser divisores comunes de \(a, b \) y otras no, considera primero \(a = 8*3*5*7, b=2*3*5*7*19\). Puedes checar que \(MCD(a,b) = 2*3*5*7\), \( n = \frac{b-a}{d} = 3*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*3*5*7, b=2*7*7*11\). Puedes checar que \(MCD(a,b) = 2*7, n = (b-a)/d = 2*31\) y por lo tanto \(n \) no es divisor común de \(a, b \).


Nota 1, si tenemos una implicación \(a ⇒ b\), el converso de ésta es la implicación \(b ⇒ a\).

©