| 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)]
