k_lab3

print("0 < B <= A")
a=int(input("A: "))
b=int(input("B: "))
g=1
print("НОД({0}:{1})=".format(a, b))
while(a%2==0 and b%2==0):
    a//=2
    b//=2
    g*=2
    print("={0}*НОД({1}:{2})=".format(g, a, b))
while(a!=0):
    if(a%2==0):
        a//=2
    if(b%2==0):
        b//=2
    if(a>=b):
        a-=b
    else:
        b-=a
    print("={0}*НОД({1}:{2})=".format(g, a, b))
print("={0}".format(g*b))