bjornl@tds.kth.se (Bj|rn Lisper) (12/15/89)
I hope this is not trivial...anyway: 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? Apparently, we can write a=ga' and b=gb'. Then, the above reduces to 1=xa'+yb'. Since 0=n(b'a'-a'b'), for any n, it follows that if x,y is a solution, then na'+x, -nb'+y is also a solution for any n. Thus, there must be a solution for which 0 <= x < a' (or 0 <= y < b'). Therefore, one could simply search the smallest of these intervals, say for x, to find an x such that y=(1-xa')/b' is an integer. But this is no fun if both a' and b' are large. Is there a faster method? Bjorn Lisper (bjornl@tds.kth.se)
bs@linus.UUCP (Robert D. Silverman) (12/15/89)
In article <BJORNL.89Dec14200717@tarpon.tds.kth.se> bjornl@tds.kth.se (Bj|rn Lisper) writes: >I hope this is not trivial...anyway: > >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? There is a very way way that runs in time O(log(max(a,b))). It is known as the Euclidean algorithm. It is very well known. Consult almost any book on algorithms. Knuth Vol 2 has an excellent exposition. -- Bob Silverman #include <std.disclaimer> Internet: bs@linus.mitre.org; UUCP: {decvax,philabs}!linus!bs Mitre Corporation, Bedford, MA 01730
casley@Neon.Stanford.EDU (Ross Casley) (12/15/89)
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.
bjornl@tds.kth.se (Bj|rn Lisper) (12/15/89)
In article <BJORNL.89Dec14200717@tarpon.tds.kth.se> bjornl@tds.kth.se (Bj|rn Lisper, i.e. me) writes: %I hope this is not trivial...anyway: It was. %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? As a number of people have pointed out to me, the Euclidean algorithm can be extended to compute x, y. Thanks to all who answered. I'll check my classics better next time before I inquire about something. Bjorn Lisper