Algoritmo de Euclides (Extra)

En esta entrada mostraremos la implementación del Algoritmo Euclides en el lenguaje Python de una manera muy sencilla.
Generalmente este algoritmo de utiliza para obtener el máximo común divisor de ciertos numeros, que a su vez puede ser parte de la simplificación de fracciones o parte de una sucesión de divisiones continuas, o en un ejercicio para conocer los inversos modulares de ciertos números.

Hay 2 formas de obtener el MCD (máximo común divisor) o GCD (greatest comun divisor):
-> Implementar el algoritmo (programar todos los pasos)
-> Usar la librería incluida en python

Aquí esta el código para la primera opción, es muy básico pero cumple con la finalidad.

def extended_gcd (a, b):
    x, ant_x = 0, 1
    y, ant_y = 1, 0
 
    while b:
        cociente = a // b
        a, b = b, a % b
        x, ant_x = ant_x - cociente*x, x
        y, ant_y = ant_y - cociente*y, y
 
    return (ant_x, ant_y, a)

def main():
  a = input()
  b = input()
  print extended_gcd(a, b)
 
main()

Y una captura de esto corriendo:

Aquí esta la segunda opción, donde solo se importa la librería y se le pasan los dos números de los cuales se quiere conocer el mcd

from fractions import gcd
  
def main():
 a = input()
 b = input()
 print "gcd(", a,", ", b,") = ", gcd(a, b)

main()

Y una captura:

_______________________________________________________________________________
Referencias
Extended_Euclidean_Algorithm
Division_Algorithm
Docs_Python _Library/fractions.gcd()