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.

Full article ▸

related documents
Heaviside step function
Intersection (set theory)
Magma (algebra)
NP-hard
Separated sets
CLU (programming language)
Twin prime conjecture
Euler's criterion
Topological ring
Goldbach's weak conjecture
Decision problem
Partial fractions in integration
Kernel (category theory)
Regular space
Real line
Whittaker–Shannon interpolation formula
Ordered field
C*-algebra
Syntactic sugar
Regular language
Graded algebra
T1 space
Lipschitz continuity
Stirling number
Dyadic rational
Greedy algorithm
Cayley's theorem
Complement (set theory)
Logical disjunction
Divisor