Subversion Repositories Code-Repo

def Extended_Euclidian(a, b):
        ''' Takes values a and b and returns a tuple (r,s,t) in the following format:
                r = s * a + t * b where r is the GCD and s and t are the inverses of a and b '''
        t_ = 0
        t = 1
        s_ = 1
        s = 0
        q = int(a/b)
        r = a - q * b
        print("%d\t= %d * %d + %d" % (a, q, b, r))
        while r > 0:
                temp = t_ - q * t
                t_ = t
                t = temp
                temp = s_ - q * s
                s_ = s
                s = temp
                a = b
                b = r
                q = int(a/b)
                r = a - q * b
                print("%d\t= %d * %d + %d" % (a, q, b, r))
        r = b
        return (r, s, t)

if __name__ == '__main__':
        a = 99
        b = 101
        res = Extended_Euclidian(a, b)
        print("%d = %d * %d + %d * %d" % (res[0], res[1], a, res[2], b))