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:
- Encuentra \(a,b \) tal que \(MCD(a,b) > 1\).
- Escribe el MCD en el campo de texto \(d \). Empieza de nuevo si \((a-b)/d = 1 \).
- Si \(n=(a-b)/d>1 \), escríbelo en el campo de texto \(d \).
- 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 \).
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\).
Créditos
Escena original
Diseño del contenido | Gustavo Magallanes Guijón |
Diseño funcional | Gustavo Magallanes Guijón |
Programación | Gustavo Magallanes Guijón |
Diseño gráfico | Ricardo López Gómez |
Coordinación | Leticia Montserrat Vargas Rocha |
Adaptación
Diseño funcional | Julio Arnoldo Prado Saavedra Victor Manuel Amezcua y Raz |
Programación | Julio Arnoldo Prado Saavedra Victor Manuel Amezcua y Raz |
Diseño gráfico | Francisco Varela Fuentes |
Coordinación | Leticia Montserrat Vargas Rocha |
Los contenidos de esta unidad didáctica interactiva están bajo una licencia Creative Commons Reconocimiento-NoComercial-CompartirIgual.
La unidad didáctica fue creada con Arquímedes, una herramienta de código abierto.
La unidad didáctica contiene escenas elaboradas con Descartes, una herramienta de código abierto.
LITE - UnADM 2014