bezout's identity
proposition 6 (Bezout's identity). The greatest common divisor can always be expressed as a linear combination of the two integers. In other words, given two integers \( a \) and \( b \), there exist integers \( x \) and \( y \) such that \( ax + by = \gcd(a, b) \).
The proof of this is constructive and most easily understood through a few examples.
example 1
For example, if \( a = 322 \) and \( b = 70 \), Bezout's identity implies that \( 322x + 70y = 14 \) for some integers \( x \) and \( y \). Such integers might be found by brute force. In this case, a brute force search might arrive at the solution \( (x, y) = (2, 9) \). However, the Euclidean algorithm provides an efficient way to find a solution.
The first division yields \( 322 = 70(4) + 42 \) with a quotient of \( q_0 = 4 \) and a remainder of \( r_0 = 42 \). Solving for \( r_0 \) gives \( 42 = 322  70(4) \). In particular, we have shown that the remainder \( r_0 \) can be expressed as a linear combination of \( 322 \) and \( 70 \), namely \( r_0 = 322(1) + 70(4) \).
The second division yields \( 70 = 42(1) + 28 \) with a quotient of \( q_1 = 1 \) and a remainder of \( r_1 = 28 \). Solving for \( r_1 \) gives \( 28 = 70  42(1) \). The linear combination for \( r_0 = 42 \) may be substituted here and simplified to \( 28 = 322 + 70(5) \). Therefore, the remainder \( r_1 = 322(1) + 70(5) \) is also a linear combination of the original two integers.
The third division gives \( 42 = 28(1) + 14 \) with a quotient of \( q_2 = 1 \) and a remainder of \( r_2 = 28 \). The linear combinations for \( r_0 = 42 \) and \( r_1 = 28 \) may be substituted into this expression. Then solving for the new remainder, it will simplify to \( 14 = 322(2) + 70(9) \), which is the solution to Bezout's identity that was listed above.
These computations are summarized in the table below. In each of the first three rows, the last column is how to express each remainder \( r \) as a linear combination of the original \( a = 322 \) and \( b = 70 \), namely, \( r = 322x + 70y \). The last row verifies that the algorithm has terminated, ie, that the gcd of \( 322 \) and \( 70 \) is the secondtolast remainder \( 14 \).
\( a' \)  \( b' \)  \( r \)  \( q \)  \( (x, y) \) 

\( 322 \)  \( 70 \)  \( 42 \)  \( 4 \)  \( (1, 4) \) 
\( 70 \)  \( 42 \)  \( 28 \)  \( 1 \)  \( (1, 5) \) 
\( 42 \)  \( 28 \)  \( 14 \)  \( 1 \)  \( (2, 9) \) 
\( 28 \)  \( 14 \)  \( 0 \)  \( 2 \) 
We would like a programatic way to compute the \( (x, y) \) pairs as we go. Suppose that on some row we have \( a' = b'q + r \) and that we have already calculated that \( a' = 322 x_0 + 70 y_0 \) and \( b' = 322 x_1 + 70 y_1 \). We can substitute these expressions into the division algorithm equation to get \[ 322 x_0 + 70 y_0 = (322 x_1 + 70 y_1)q + r. \] Solving for \( r \) and rearranging, we get \[ r = 322 (x_0  x_1 q) + 70(y_0  y_1 q). \]
This is great news, because we can compute the the next \( (x, y) \)
pair from the previous two pairs. The recursive relation for both \( x \)
and \( y \) can be expressed as
\[ u_2 = u_0  u_1 \cdot q. \]
In other words, the next_value = previous_value  current_value * quotient
.
To see this in action, we observe first that \( a = a(1) + b(0) \) and \( b = a(0) + b(1) \), so the initial values for the \( (x, y) \) pairs are \( (1, 0) \) and \( (0, 1) \).
The first quotient is \( q = 4 \), so the first \( (x, y) \) pair is \[ (1, 0)  (0, 1) \cdot 4 = (1  0, 0  4) = (1, 4). \] (Note that we used vector addition and scalar multiplication to express this succinctly.) The second quotient is \( q = 1 \), so the second pair is \[ (0, 1)  (1, 4) \cdot 1 = (0  1, 1 + 4) = (1, 5). \] The third quotient is \( q = 1 \), so the third pair is \[ (1, 4)  (1, 5) \cdot 1 = (1 + 1, 4  5) = (2, 9). \] Since the following remainder is \( 0 \), the algorithm terminates.
example 2
Here is another example to illustrate this process. Suppose we want to find a solution to \( 5831 x + 482 y = \gcd(5831, 482) \). We seed our table with the initial \( (x, y) \) pairs and with \( a \) and \( b \) as the first "remainders".
\( a' \)  \( b' \)  \( r \)  \( q \)  \( (x, y) \) 

\( 5831 \)  \( (1, 0) \)  
\( 482 \)  \( (0, 1) \) 
The division of \( 5381 \) by \( 482 \) yields \( 5831 = 482(12) + 47 \). Since the quotient is \( q = 12 \), we calculate the next \( (x, y) \) pair to be \[ (1, 0)  (0, 1) \cdot 12 = (1  0, 0  12) = (1, 12) \] and we fill in the new row on the table.
\( a' \)  \( b' \)  \( r \)  \( q \)  \( (x, y) \) 

\( 5831 \)  \( (1, 0) \)  
\( 482 \)  \( (0, 1) \)  
\( 5831 \)  \( 482 \)  \(47 \)  \( 12 \)  \( (1, 12) \) 
The division of \( 482 \) by \( 47 \) yields \( 482 = 47(10) + 12 \). Since the quotient is \( q = 10 \), we calculate the next \( (x, y) \) pair to be \[ (0, 1)  (1, 12) \cdot 10 = (0  10, 1 + 120) = (10, 121) \] and we fill in the new row on the table.
\( a' \)  \( b' \)  \( r \)  \( q \)  \( (x, y) \) 

\( 5831 \)  \( (1, 0) \)  
\( 482 \)  \( (0, 1) \)  
\( 5831 \)  \( 482 \)  \(47 \)  \( 12 \)  \( (1, 12) \) 
\( 482 \)  \( 47 \)  \(12 \)  \( 10 \)  \( (10, 121) \) 
The division of \( 47 \) by \( 12 \) yields \( 47 = 12(3) + 11 \). With a quotient of \( q = 3 \), the next \( (x, y) \) pair is \[ (1, 12)  (10, 121) \cdot 3 = (1 + 30, 12  363) = (31, 375) \] and we fill in the new row on the table.
\( a' \)  \( b' \)  \( r \)  \( q \)  \( (x, y) \) 

\( 5831 \)  \( (1, 0) \)  
\( 482 \)  \( (0, 1) \)  
\( 5831 \)  \( 482 \)  \(47 \)  \( 12 \)  \( (1, 12) \) 
\( 482 \)  \( 47 \)  \(12 \)  \( 10 \)  \( (10, 121) \) 
\( 47 \)  \( 12 \)  \(11 \)  \( 3 \)  \( (31, 375) \) 
The division of \( 12 \) by \( 11 \) yields \( 12 = 11(1) + 1 \). With a quotient of \( q = 1 \), the next pair is \[ (10, 121)  (31, 375) \cdot 1 = (10  31, 121 + 375) = (41, 496) \] and we fill in the new row.
\( a' \)  \( b' \)  \( r \)  \( q \)  \( (x, y) \) 

\( 5831 \)  \( (1, 0) \)  
\( 482 \)  \( (0, 1) \)  
\( 5831 \)  \( 482 \)  \(47 \)  \( 12 \)  \( (1, 12) \) 
\( 482 \)  \( 47 \)  \(12 \)  \( 10 \)  \( (10, 121) \) 
\( 47 \)  \( 12 \)  \(11 \)  \( 3 \)  \( (31, 375) \) 
\( 12 \)  \( 11 \)  \(1 \)  \( 1 \)  \( (41, 496) \) 
The final division of \( 11 \) by \( 1 \) yields \( 11 = 1(11) + 0 \). With a remainder of \( 0 \), the algorithm has terminated. The greatest common divisor is \( \gcd(5831, 482) = 1 \) and \( (41, 496) \) is a solution to \( 5831 x + 482 y = 1 \).
in code
The examples above can be generalized into a constructive proof of Bezout's identity  the proof is an algorithm to produce a solution.
Bezout algorithm for positive integers. Given positive integers
a
andb
, we want to find integersx
andy
such thata * x + b * y == gcd(a, b)
. Initially setprev = [1, 0]
andcurr = [0, 1]
.
 If
b == 0
, returnprev
. Calculate
q, r = div_rem(a, b)
. Calculate
x = prev[0]  curr[0] * q
andy = prev[1]  curr[1] * q
. Replace
a, b
withb, r
. Replace
prev, curr
withcurr, [x, y]
. Return to Step 1.
The algorithm needs to be adjusted slightly for zero or negative values. Run
the algorithm described for various combinations of positive, negative, and
zero values, checking whether each resulting pair x, y
actually satisfies
a * x + b * y == gcd(a, b)
.
While exploring zero/negative values, there are 3 cases to consider:
 when the algorithm returns immediately, ie, when the original
b
is zero.  when the algorithm returns after one iteration, ie, when the first remainder
r
is zero.  when the algorithm returns after two or more iterations.
We seeded the algorithm initially with prev = [1, 0]
and curr = [0, 1]
.
We did this in order to express a
and b
in terms of themselves, ie,
a == 1 * a + 0 * b
and b == 0 * a + 1 * b
. With two or more iterations,
the division algorithm guarantees that the remainder is positive, so the
calculated pair at that point gives a positive number a * x + b * y
.
However, if the algorithm terminates during the first or second iteration, we
would return either [1, 0]
or [0, 1]
, in which case we may end up with
a * x + b * y
as a negative value, which would be incorrect since the
greatest common divisor is always positive.
To account for this, we may need to negate the values of prev
in Step 1
before returning. Consider these two examples.

Let
a = 10
andb = 0
. Sinceb == 0
, we return the originalprev = [1, 0]
immediately. Notice that1 * 10 + 0 * 0 == 10
whilegcd(10, 0) == 10
. In this case, we need to return the originalprev
but with negated values, ie,[1, 0]
. 
Let
a = 10
andb = 5
. Sinceb != 0
, we calculateq = 2
andr = 0
. When we return to Step 1, we havenew_b = r == 0
, so we returnnew_prev = curr == [0, 1]
. Notice that0 * 10 + 1 * 5 = 5
whilegcd(10, 5) == 5
. In this case, we need to return thenew_prev
but with negated values, ie,[0, 1]
.
The conclusion is that Step 1 requires the following adjustment:
 If
b == 0
, returnprev
ifa > 0
, otherwise returnprev
with negated values.
exercise. Write a
bezout
function that takes integer inputs(a, b)
and produces integers(x, y)
such thata * x + b * y = gcd(a, b)
.
Testing this function is very simple: regardless of the inputs, Bezout's identity must be satisfied. Make sure you include test inputs for the special cases discussed above.
def test_bezout
test_inputs.each do (a, b)
x, y = bezout(a, b)
assert_equal gcd(a, b), a * x + b * y
end
end
def test_bezout_explicit
assert_nil bezout(0, 0)
end