def euclide(a,b):
    if b > a:
        a,b = b,a

    r = -1
    while r !=0 :
        q = a // b
        r = a % b
        print('{:3} = {:2} x {:2} + {}' . format(a,q,b,r))
        a = b
        b = r