**Bezout's Identity**

**ax + by =d**

Bezout's identity or Bezout's lemma is a theorem that states
that if a and
b are two nonzero integers and
d is the gcd(a,b), then there
exist integers x,y such that ax + by =d |

x,y are called Bezout Coefficients for (a,b). They are not unique. |

Among various pairs of Bezout Coefficients, exactly 2 pairs
satisfy |x| < b/d and
|y| < a/d . These are called minimal
pairs. This is based on a property of Euclidean division. |

Once a pair is found, other pairs can be generated by the
formula x2= x+(kb/d) and y2= y-(ka/d) |