Bézout's Identity

Bézout's identity states that the greatest common divisor (GCD) of two integers, \( a \) and \( b \), can be expressed as a linear combination of \( a \) and \( b \) with integer coefficients \( j \) and \( k \): $$ \gcd(a,b) = d = aj + bk $$

Finding the Coefficients in Bézout's Identity

To determine the integer coefficients \( j \) and \( k \), we can use the Euclidean algorithm, which involves repeated division.

A Practical Example

Let's compute the GCD of 2016 and 35:

$$ a = 2016 \\ b = 35 $$

Using the Euclidean algorithm:

$$ 2016 = 35 \cdot 57 + 21
\\ 35 = 21 \cdot 1 + 14
\\ 21 = 14 \cdot 1 + 7
\\ 14 = 7 \cdot 2 + 0
$$

Note: The last term in each equation represents the remainder of the division.

The last nonzero remainder (7) is the greatest common divisor of 2016 and 35:

$$ \gcd(2016,35) = 7 $$

Now, to find the coefficients for Bézout’s identity, we start by assigning unit values to \( a \) and \( b \):

$$ a = (1,0) \\ b = (0,1) $$

Next, we express each remainder from the Euclidean algorithm in terms of the previous two values:

$$ r_1 = a + b(-q_1)
\\ r_2 = b + r_1(-q_2)
\\ r_3 = r_2 + r_1(-q_3)
\\ r_4 = r_3 + r_2(-q_4)
\vdots $$

After setting up the first equation, we progressively substitute values without recalculating them at each step.

$$ 21 = (1,0) + (0,1)(-57) = (1,-57) $$

$$ 14 = (0,1) + (1,-57)(-1) = (-1,58) $$

$$ 7 = (1,-57) + (-1,58)(-1) = (2,-115) $$

Since we’ve reached the final remainder, the last pair of values gives us the coefficients for Bézout’s identity:

$$ j = 2 \\ k = -115 $$

Thus, we can express the GCD as:

$$ \gcd(2016,35) = 7 = 2016 \cdot j + 35 \cdot k $$

$$ 2016 \cdot 2 + 35 \cdot (-115) $$

We have now written the greatest common divisor as a linear combination of 2016 and 35.

Verification: To confirm our result, let's compute the linear combination: $$ 2016 \cdot 2 + 35 \cdot (-115) \\ 4032 - 4025 = 7 $$

And that’s it!