Line 8: | Line 8: | ||
else | else | ||
[c,d] = eeuclid(b, a % b) | [c,d] = eeuclid(b, a % b) | ||
− | return [ | + | return [d, c - d*(a/b)] |
Revision as of 20:14, 3 January 2011
This is the Extended Euclid algorithm we talked about last Thursday. Kind of cool, plug it into your favorite programming language.
def eeuclid(a,b)
if a % b = 0: return [0,1] else [c,d] = eeuclid(b, a % b) return [d, c - d*(a/b)]