Xref: utzoo sci.math:8993 comp.theory:114
Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!wuarchive!decwrl!shelby!neon!casley
From: casley@Neon.Stanford.EDU (Ross Casley)
Newsgroups: sci.math,comp.theory
Subject: Re: Integer gcd
Message-ID: <1989Dec15.012938.7414@Neon.Stanford.EDU>
Date: 15 Dec 89 01:29:38 GMT
References: <BJORNL.89Dec14200717@tarpon.tds.kth.se>
Sender: USENET News System <news@Neon.Stanford.EDU>
Organization: Computer Science Department, Stanford University
Lines: 19

In article <BJORNL.89Dec14200717@tarpon.tds.kth.se> bjornl@tds.kth.se (Bj|rn Lisper) writes:
>Consider two integers a,b. Let g=gcd(a,b). Then, there are integers x,y such
>that g=xa+yb. What is the best method to find some x, y satisfying this?

A simple method is to extend the standard Euclid's algorithm as described
in Knuth Volume I, at the top of page 14, and proven correct in the following
page or so.  The outline of the algorithm is this (assume a > b):

    x' := y := 1;  x := y' := 0; c := a; d := b
    loop
        Set q, r to quotient and remainder of c divided by d;
        if r = 0  then exit (the gcd is d, and d = x.a + y.b)
        c := d; d := r; 
        t := x'; x' := x; x := t-q.x; 
        t := y'; y' := y; y := t-q.y;
    endloop


-Ross Casley.