#!/usr/local/bin/python
#
# euclid.py
#
# Program that does the Euclidian algorithm for determining the
# greatest common divisor of two integers.
#
# Chris Lawrence 9/8/96

import string

def do_euclid(a, b):
    # Returns (gcd, x, y) for a and b
    # x,y are an ordered pair such that a*x+b*y=gcd

    prevr, thisr = a, b
    prevx, thisx = 1, 0
    prevy, thisy = 0, 1
    
    while thisr > 0:
        thisq = int(prevr/thisr)
        nextr = prevr - thisq * thisr
        nextx = prevx - thisq * thisx
        nexty = prevy - thisq * thisy

        prevr, thisr = thisr, nextr
        prevx, thisx = thisx, nextx
        prevy, thisy = thisy, nexty

    return (prevr, prevx, prevy)

print "Euclid's algorithm to find the greatest common divisor of two integers"
print

a = input("Enter a: ")
b = input("Enter b: ")

(gcd, x, y) = do_euclid(a, b)

print "Greatest common divisor of %d and %d is %d." % (a, b, gcd)
print "x = %d, y = %d such that ax + by = (a,b)." % (x, y)