×

Extended Euclid’s algorithm via backward recurrence relations. (English) Zbl 1011.11003

After using Euclid’s algorithm to find \((a,b)\) one can either work forward from the pair \(a,b\) or backwards from the pair \((a,b),0\) to find \(x,y\) such that \(ax+by= (a,b)\). The author claims that working backwards is better for calculation by hand, and also pedagogically, but that working forwards is better for use with a computer.
Reviewer: H.J.Godwin (Egham)

MSC:

11A05 Multiplicative structure; Euclidean algorithm; greatest common divisors
PDFBibTeX XMLCite
Full Text: DOI