Subversion Repositories Code-Repo

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
219 Kevin 1 
 
2 
def Extended_Euclidian(a, b):
3 
	''' Takes values a and b and returns a tuple (r,s,t) in the following format:
4 
		r = s * a + t * b where r is the GCD and s and t are the inverses of a and b '''
5 
	t_ = 0
6 
	t = 1
7 
	s_ = 1
8 
	s = 0
9 
	q = int(a/b)
10 
	r = a - q * b
11 
	print("%d\t= %d * %d + %d" % (a, q, b, r))
12 
	while r > 0:
13 
		temp = t_ - q * t
14 
		t_ = t
15 
		t = temp
16 
		temp = s_ - q * s
17 
		s_ = s
18 
		s = temp
19 
		a = b
20 
		b = r
21 
		q = int(a/b)
22 
		r = a - q * b
23 
		print("%d\t= %d * %d + %d" % (a, q, b, r))
24 
	r = b
25 
	return (r, s, t)
26 
 
27 
if __name__ == '__main__':
28 
	a = 99
29 
	b = 101
30 
	res = Extended_Euclidian(a, b)
31 
	print("%d = %d * %d + %d * %d" % (res[0], res[1], a, res[2], b))