The extended Euclidean algorithm augments the Euclidean algorithm for integers 
and 
so that, in addition to 
, it computes integers 
and 
satisfying Bézout's identity
 |
For 
,
start with 
and 
.
Let 
,
where 
denotes the floor function, and set
 |
When 
,
the algorithm returns 
together with 
and 
. For example, it gives 
together with 
.
The extended Euclidean algorithm is used to solve linear Diophantine equations and to compute multiplicative inverses modulo an integer.
