# Bézout's identity

 related topics {math, number, function}

In number theory, Bézout's identity or Bézout's lemma, named after Étienne Bézout, is a linear diophantine equation. It states that if a and b are nonzero integers with greatest common divisor d, then there exist integers x and y (called Bézout numbers or Bézout coefficients) such that

Additionally, d is the smallest positive integer for which there are integer solutions x and y for the preceding equation.

## Contents

### History

Étienne Bézout (1730–1783) proved this identity for polynomials. However, this statement for integers can be found already in the work of French mathematician Claude Gaspard Bachet de Méziriac (1581–1638).[1]

### Algorithm

The Bézout numbers x and y as above can be determined with the extended Euclidean algorithm. However, they are not unique. If one solution is given by (x, y), then there are infinitely many solutions. These are given by

### Example

The greatest common divisor of 12 and 42 is 6. Bézout's identity states that there must exist an integer solution for x and y in the following equation:

One of its solutions is x = −3 and y = 1: indeed, we have (−3)·12 + 1·42 = 6. Another solution is x = 4 and y = −1.

### Musical Intervals

Because musical intervals often correspond to ratios between frequencies of the form a/b, Bezout's Identity is particularly useful for finding the set of all intervals that approximate a given interval a/b. For example, let us attempt to find all intervals (ratios) that approximate the Pythagorean Major Third 81/64. With a = 81, b = 64 then gcd(a, b) = d = 1 and

Solving for x and y gives x = −15, y = 19. Since 81 = (4 x 19) + 5 and 64 = (4 x 15) + 4 , then the K'th ratio in this set will equal

This gives the set {5/4, 24/19, 43/34, 62/49, 81/64...}

In other words, all of the numerators are equivalent to 5 (Mod 19) while all of the denominators are equivalent to 4 (Mod 15). Of course, taking each of these ratios in decimal form shows that they are indeed approximate to 81/64 and to one another. Now, observe that as K increases, each of these ratios converge to y/x = 19/15 = 1.2666... which itself is an approximation to our original a/b = 81/64 = 1.265625. Therefore, let us repeat the process with 19/15 now as our new 'input' values, that is a = 19 and b = 15. We obtain x = 4 and y = −5. Taking

{19/15, 24/19, 29/23, 34/27, 39/31, 44/35,...}

Once again, as K increases all of these ratios approach y/x = 5/4 = 1.25. The appearance of 5/4 is hardly surprising since this is another common tuning for the major third interval, the Just Intonation Major Third.