欧几里得算法

eculid.py

# Euclid Algorithm

def gcd(m, n):
	while n != 0:
		t = m
		m = n
		n = t % n
	return m

# 
def extend_euclid(m, n):
	x1 = 1
	x2 = 0
	y1 = 0
	y2 = 1
	while n != 0:
		t = m
		m = n
		q = t/n
		n = t % n
		t1 = x1
		t2 = y1
		x1 = x2
		y1 = y2
		x2 = t1 - q*x2
		y2 = t2 - q*y2
	
	return [m, x1, y1]