#!/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)