Xref: utzoo sci.math:8987 comp.theory:109
Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!uunet!mcsun!sunic!sics.se!sics!bjornl
From: bjornl@tds.kth.se (Bj|rn Lisper)
Newsgroups: sci.math,comp.theory
Subject: Integer gcd
Message-ID: <BJORNL.89Dec14200717@tarpon.tds.kth.se>
Date: 14 Dec 89 19:07:17 GMT
Sender: news@sics.se
Organization: The Royal Inst. of Technology (KTH), Stockholm, Sweden.
Lines: 14

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)