Solves a linear Diophantine equation (Bezout identity).
d = number_extendedeuclid ( a , b ) [ d , x ] = number_extendedeuclid ( a , b ) [ d , x , y ] = number_extendedeuclid ( a , b )
a 1x1 matrix of floating point integers, must be positive
a 1x1 matrix of floating point integers, must be positive
a 1x1 matrix of floating point integers
a 1x1 matrix of floating point integers
a 1x1 matrix of floating point integers
Returns d, x and y such that d is the GCD of a and b and d = x*a + y*b.
Uses the extended Euclid's algorithm.
[ d , x , y ] = number_extendedeuclid ( 99 , 78 ) // [3 -11 14] [ d , x , y ] = number_extendedeuclid ( 120 , 23 ) // [1 -9 47]
"Introduction to algorithms", Cormen, Leiserson, Rivest, Stein, 2nd edition