# -*- coding: utf-8 -*-
"""
Created on Fri Nov 13 10:07:20 2015

@author: hstrey
"""

def gcd(a, b):
    """Calculate the Greatest Common Divisor of a and b.

    Unless b==0, the result will have the same sign as b (so that when
    b is divided by it, the result comes out positive).
    """
    while b:
        print "gcd(%d,%d)" % (a,b)
        a, b = b, a%b
    return a
    
def egcd(a, b):
    aa,bb=a,b # make a copy
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
        print a,b,"; %d = (%d*%d)+(%d*%d)" % (b,aa,x,bb,y)
    gcd = b
    return gcd, x, y


result=egcd(7,30)
print "result= ",result