Xref: utzoo sci.math:8998 comp.theory:115
Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!sunic!sics.se!sics!bjornl
From: bjornl@tds.kth.se (Bj|rn Lisper)
Newsgroups: sci.math,comp.theory
Subject: Re: Integer gcd
Message-ID: <BJORNL.89Dec15093250@tarpon.tds.kth.se>
Date: 15 Dec 89 08:32:50 GMT
References: <BJORNL.89Dec14200717@tarpon.tds.kth.se>
Sender: news@sics.se
Organization: The Royal Inst. of Technology (KTH), Stockholm, Sweden.
Lines: 14
In-Reply-To: bjornl@tds.kth.se's message of 14 Dec 89 20:07:17

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