Extended Euclid Algorithom

http://translate.google.com/translate?act=url&depth=1&hl=en&ie=UTF8&prev=_t&rurl=translate.google.com&sl=auto&tl=en&twu=1&u=http://e-maxx.ru/algo/extended_euclid_algorithm


Implementation:--

int gcd ( int a, int b, int & x, int & y ) {
if ( a == 0 ) {
x = 0 ; y = 1 ;
return b ;
}
int x1, y1 ;
int d = gcd ( b % a, a, x1, y1 ) ;
x = y1 - ( b / a ) * x1 ;
y = x1 ;
return d ;
}