gcd.py

import math

def my_gcd(a, b, verbose=False):
    if a < b:
        a, b = b, a
    #initialization m -> μ, l = λ, m_1 means μ₋₁ (\u03BC\u208b\u2081)
    #i = 0
    r_1 = a
    r0 = b
    l_1 = 1
    m_1 = 0
    l0 = 0
    m0 = 1
    #computation
    while(a * l0 + b * m0 == r0):
        q = r_1 // r0
        if(verbose):
            print(f'r_1 = {r_1}, r0 = {r0}')
            print(f'l_1 = {l_1}, l0 = {l0}')
            print(f'm_1 = {m_1}, m0 = {m0}')
            print(f'q = {q}\n----------')
        l_tmp = l0
        l0 = l_1 - q * l0
        l_1 = l_tmp
        m_tmp = m0
        m0 = m_1 - q * m0
        m_1 = m_tmp
        r_tmp = r0
        r0 = r_1 % r0
        if r0 == 0:
            return (l_1, m_1, a * l_1 + b * m_1)
        r_1 = r_tmp

a = int(input('a = '), 10)
b = int(input('b = '), 10)
v = input('verbose? y/N: ')
verbose = False
if v == 'y':
    verbose = True
l, m, gcd = my_gcd(a, b, verbose)
real_gcd = math.gcd(a, b)
print(f'λ = {l}, μ = {m}, gcd({a}, {b}) = {gcd}, real gcd is {real_gcd}')