Name

number_extendedeuclid — Solves a linear Diophantine equation (Bezout identity).

Calling Sequence

   d = number_extendedeuclid ( a , b )
   [ d , x ] = number_extendedeuclid ( a , b )
   [ d , x , y ] = number_extendedeuclid ( a , b )
   
   

Parameters

a :

a 1x1 matrix of floating point integers, must be positive

b :

a 1x1 matrix of floating point integers, must be positive

d :

a 1x1 matrix of floating point integers

x :

a 1x1 matrix of floating point integers

y :

a 1x1 matrix of floating point integers

Description

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.

Examples

[ d , x , y ] = number_extendedeuclid ( 99 , 78 ) // [3 -11 14]
[ d , x , y ] = number_extendedeuclid ( 120 , 23 ) // [1 -9 47]

   

Bibliography

"Introduction to algorithms", Cormen, Leiserson, Rivest, Stein, 2nd edition

Authors

Copyright (C) 2009 - 2010 - DIGITEO - Michael Baudin