Bezout’s Identity

Bézout’s identity — Let a and b be integers with greatest common divisor d. Then there exist integers x and y such that ax + by = d. Moreover, the integers of the form az + bt are exactly the multiples of d.
Here the greatest common divisor of 0 and 0 is taken to be 0. The integers x and y are called Bézout coefficients for (ab); they are not unique. A pair of Bézout coefficients can be computed by the extended Euclidean algorithm

Let d = gcd(a, b). We will show that:

  1. ;
  2. m is a common divisor of a and b.