Extended Euclid's algorithm

Extended Euclid’s algorithm also computes $x,y\in \mathcal{Z}$ (integer coefficients) such that:

$$d=gcd(a,b)=(x\times a)+(y\times b)$$

The algorithm works as follows: $\text{Extended-Euclid}(a,b)$

• if $b=0$ then
  • return $(a,1,0)$
• else
  • $(d^{\prime },x^{\prime },y^{\prime })\leftarrow \text{Extended-Euclid}(b,a\text{ mod }b)$
  • $(d,x,y)\leftarrow (d^{\prime },y^{\prime },x^{\prime }-(\lfloor a/b\rfloor \times y^{\prime }))$
  • return $(d,x,y)$

Where $q=\lfloor a/b\rfloor$ is the quotient of the division (for $a=(q\times b)+r$).