El algoritmo euclidiano, también conocido como división alterna, se utiliza para calcular el máximo común divisor de dos números enteros no negativos A y b. Hay dos campos de aplicación de gfa A: Matemáticas. y Computadoras. Fórmula de cálculo mcd(a, b) = mcd(b, a mod b).
El algoritmo euclidiano y el algoritmo euclidiano extendido se pueden implementar en una variedad de lenguajes de programación.
El algoritmo euclidiano se utiliza para encontrar el máximo común divisor de dos números enteros positivos. El antiguo matemático griego Euclides describió por primera vez este algoritmo en su obra "Elementos", por lo que recibió el nombre de algoritmo de Euclides.
El algoritmo euclidiano extendido se puede utilizar en campos como el cifrado RSA. ?
Si necesitas encontrar el máximo común divisor de dos enteros positivos 1997 y 615, utiliza el algoritmo euclidiano, de la siguiente manera:
1997 ÷ 615 = 3 (resto 152)
615 ÷ 152 = 4 (resto 7)
152 ÷ 7 = 21 (resto 5)
7 ÷ 5 = 1 (resto 2)
5 ÷ 2 = 2 (resto 1)
2 ÷ 1 = 2 (resto 0)
Hasta ahora, el máximo común divisor es 1.
Dividir repetidamente por el divisor y el resto. Cuando el resto es 0, tome el divisor de la fórmula actual como el máximo común divisor y obtenga el máximo común divisor de 1997 y 615.
La división conmutativa utiliza las siguientes propiedades para determinar el máximo común divisor de dos enteros positivos A y B:
Si R es el resto de a ÷ b, y R no es. 0, entonces
mcd(a, b) = mcd(b, r)
El máximo común divisor de a y sus múltiplos es a.
Otra forma de escribirlo es:
1. Sea r a/b, el resto (0≤r
Si r= 0, el algoritmo termina; la respuesta es b
Intercambio: Sea a←b, b←r, regrese al primer paso