Contenido principal
Curso: Ciencias de la computación > Unidad 2
Lección 5: Aritmética modular- ¿Qué es la aritmética modular?
- Operador módulo
- Desafío de módulo
- Congruencia módulo
- Relación de congruencia
- Relaciones de equivalencia
- El teorema del cociente y del residuo
- Suma y resta modular
- Suma modular
- Desafío de módulo (suma y resta)
- Multiplicación modular
- Multiplicación modular
- Exponenciación modular
- Exponenciación modular rápida
- Exponenciación modular rápida
- Inversos modulares
- El algoritmo de Euclides
© 2024 Khan AcademyTérminos de usoPolítica de privacidadAviso de cookies
El algoritmo de Euclides
Recuerda que el máximo común divisor (MCD) de dos enteros A y B es el entero más grande que divide tanto a A como a B.
El algoritmo de Euclides es una técnica para encontrar rápidamente el MCD de dos enteros.
El algoritmo
El algoritmo de Euclides para encontrar MCD(A,B) es como sigue:
- Si A = 0 entonces MCD(A,B)=B, ya que el MCD(0,B)=B, y podemos detenernos.
- Si B = 0 entonces MCD(A,B)=A, ya que el MCD(A,0)=A, y podemos detenernos.
- Escribe A en la forma cociente y residuo (A = B ⋅Q + R).
- Encuentra MCD(B,R) al usar el algoritmo de Euclides, ya que MCD(A,B) = MCD(B,R).
Ejemplo:
Encuentra el MCD de 270 y 192.
- A=270, B=192.
- A ≠0
- B ≠ 0
- Usa división larga para encontrar que 270/192 = 1 con un residuo de 78. Podemos escribir esto como: 270 = 192 * 1 + 78
- Encuentra MCD(192,78), ya que MCD(270,192)=MCD(192,78).
A=192, B=78.
- A ≠0
- B ≠ 0
- Usa división larga para encontrar que 192/78 = 2 con un residuo de 36. Podemos escribir esto como:
- 192 = 78 * 2 + 36
- Encuentra MCD(78,36), ya que MCD(192,78)=MCD(78,36).
A=78, B=36.
- A ≠0
- B ≠ 0
- Usa división larga para encontrar que 78/36 = 2 con un residuo de 6. Podemos escribir esto como:
- 78 = 36 * 2 + 6
- Encuentra MCD(36,6), ya que MCD(78,36)=MCD(36,6).
A=36, B=6.
- A ≠0
- B ≠ 0
- Usa división larga para encontrar que 36/6 = 6 con un residuo de 0. Podemos escribir esto como:
- 36 = 6 * 6 + 0
- Encuentra MCD(6,0), ya que MCD(36,6)=MCD(6,0).
A=6, B=0.
- A ≠0
- B =0, MCD(6,0)=6.
Así que hemos mostrado:
MCD(270,192) = MCD(192,78) = MCD(78,36) = MCD(36,6) = MCD(6,0) = 6.
MCD(270,192) = 6.
Entender el algoritmo de Euclides
Si examinamos el algoritmo de Euclides podemos ver que hace uso de las siguientes propiedades:
- MCD(A,0) = A.
- MCD(0,B) = B.
- Si A = B⋅Q + R y B≠0, entonces MCD(A,B) = MCD(B,R) , donde Q es un entero y R es un entero entre 0 y B-1.
Las primeras dos propiedades nos permiten encontrar el MCD si cualquiera de los dos números es 0. La tercera propiedad nos permite tomar un problema más grande y más difícil de resolver, y reducirlo a un problema más pequeño y más fácil de resolver.
El algoritmo de Euclides hace uso de estas propiedades al reducir rápidamente el problema en problemas más y más fáciles, al usar la tercera propiedad, hasta que se resuelve fácilmente mediante el uso una de las primeras dos propiedades.
Podemos entender por qué funcionan estas propiedades al demostrarlas.
Podemos demostrar que MCD(A,0)=A como sigue:
- El entero más grande que puede dividir uniformemente a A es A.
- Todos los enteros dividen uniformemente a 0, puesto que para cualquier número entero, C, podemos escribir C ⋅ 0 = 0. Así que podemos concluir que A debe dividir uniformemente a 0.
- El número más grande que divide tanto a A como a 0 es A.
La demostración para MCD(0, B)=B es similar. (Misma demostración, pero reemplazamos A con B).
Para demostrar que MCD(A,B)=MCD(B,R) lo primero que tenemos que mostrar es que MCD(A,B)=MCD(B,A-B).
Supón que tenemos tres enteros A, B y C tales que A-B=C.
Demostración de que MCD(A,B) divide uniformemente a C
El MCD(A,B), por definición, divide uniformemente a A. Como resultado, A debe ser algún múltiplo de MCD(A,B). Es decir, X⋅MCD(A,B)=A, donde X es algún número entero.
El MCD(A,B), por definición, divide uniformemente a B. Como resultado, B debe ser algún múltiplo de MCD(A,B). Es decir, Y⋅MCD(A,B)=B, donde Y es algún número entero.
A-B=C nos da:
- X⋅MCD(A,B) - Y⋅MCD(A,B) = C
- (X - Y)⋅MCD(A,B) = C
Así que podemos ver que MCD(A,B) divide uniformemente a C.
Una ilustración de esta demostración se muestra en la parte izquierda de la siguiente figura:
Demostración de que MCD(B,C) divide uniformemente a A
El MCD(B,C), por definición, divide uniformemente a B. Como resultado, B debe ser algún múltiplo de MCD(B,C). Es decir, M⋅MCD(B,C)=B, donde M es algún número entero.
El MCD(B,C), por definición, divide uniformemente a C. Como resultado, C debe ser algún múltiplo de MCD(B,C). Es decir, N⋅MCD(B,C)=C, donde N es algún número entero.
A-B=C nos da:
- B+C=A.
- M⋅MCD(B,C) + N⋅MCD(B,C) = A
- (M + N) ⋅ GCD(B,C) = A
Así que podemos ver que MCD(B,C) divide uniformemente a A.
Una ilustración de esta demostración se muestra en la siguiente figura:
Demostración de que MCD(A,B)=MCD(A,A-B)
- MCD(A,B) por definición, divide uniformemente a B.
- Ya demostramos que MCD(A,B) divide uniformemente a C.
- Como el MCD(A,B) divide uniformemente tanto a B como a C, es un divisor común de B y de C.
MCD(A,B) debe ser menor que o igual a MCD(B,C), porque MCD(B,C) es el “máximo” común divisor de B y de C.
- MCD(B,C) por definición, divide uniformemente a B.
- Ya demostramos que MCD(B,C) divide uniformemente a A.
- Como el MCD(B,C) divide uniformemente tanto a A como a B, es un divisor común de A y de B.
MCD(B,C) debe ser menor que o igual a, MCD(A,B), porque MCD(A,B) es el “máximo” común divisor de A y de B.
Dado que MCD(A,B)≤MCD(B,C) y MCD(B,C)≤MCD(A,B) podemos concluir que:
MCD(A,B)=MCD(B,C).
Que es equivalente a:
MCD(A,B)=MCD(B,A-B).
Una ilustración de esta demostración se muestra en la parte derecha de la siguiente figura.
Demostración de que MCD(A,B) = MCD(B,R)
Ya demostramos que MCD(A,B)=MCD(B,A-B).
El orden de los términos no importa, así que podemos decir que MCD(A,B)=MCD(A-B,B).
Podemos aplicar repetidamente MCD(A,B)=MCD(A-B,B) para obtener:
MCD(A,B)=MCD(A-B,B)=MCD(A-2B,B)=MCD(A-3B,B)=...=MCD(A-Q⋅B,B).
Pero A= B⋅Q + R, así que A-Q⋅B=R.
Por lo tanto MCD(A,B)=MCD(R,B).
El orden de los términos no importa, así que:
MCD(A,B)=MCD(B,R).
¿Quieres unirte a la conversación?
no entendi ni meridas(3 votos)
Si te interesa este tema, puedes empezar a aprender teoría de números que es de donde sale el algoritmo de euclides. Cuando estaba interesado en olimpiadas, estudie con el libro de teoria de números de Maria Luisa Perez, donde aborda este tema y tambien su demostración formal.(4 votos)
Interesante Ejemplo: "A las5:31, ¿cómo es la Luna lo suficientemente grande como para bloquear el Sol? ¿No es el Sol mucho más grande que la Luna?(1 voto)
5:31