O
Old Wolf
Old said:He may be thinking of the 'reverse Euclidean algorithm', ie.
once you have determined that g = gcd(a,b) via the Euclidean
algorithm, you can then backtrack through the steps to find
x,y such that g = ax + by.
OT, but interesting: note that this lets us solve any
equation such as:
23x = 1 (mod 240)
where the 23 and the 240 are coprime (because if two
numbers are coprime then 1 is their g.c.d.).
This has an application in public key cryptography, where
once you have picked a public key 'e', the private key
'd' is specified by:
ed = 1 (mod phi(n))
(and 'e' was chosen such that e and phi(n) are coprime).