Xref: utzoo sci.math:9004 comp.theory:116 Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!uunet!philmtl!philabs!linus!bs From: bs@linus.UUCP (Robert D. Silverman) Newsgroups: sci.math,comp.theory Subject: Re: Integer gcd Message-ID: <83195@linus.UUCP> Date: 14 Dec 89 21:16:18 GMT References: Reply-To: bs@gauss.UUCP (Robert D. Silverman) Organization: The MITRE Corporation, Bedford MA Lines: 15 In article 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 Internet: bs@linus.mitre.org; UUCP: {decvax,philabs}!linus!bs Mitre Corporation, Bedford, MA 01730