Euclid and Bézout

Bézout's identity and theorem

Euclid's algorithm gives the GCD. Running it backwards gives much more: an expression of the GCD as a combination of the two starting numbers.

Bézout's identity

For all integers a and b, there exist integers u and v such that
a u + b v = GCD(a , b)

The coefficients u and v are called Bézout coefficients. They are not unique.

1071 × (-3) + 462 × 7 = -3213 + 3234 = 21 = GCD(1071 , 462)   ✔

Finding them: the extended Euclidean algorithm

Work back up the successive divisions, expressing each remainder from the two previous lines.

Downward (Euclid):

   1071 = 2 × 462 + 147      ->    147 = 1071 - 2×462
    462 = 3 × 147 +  21      ->     21 = 462 - 3×147
    147 = 7 ×  21 +   0

Upward:

   21 = 462 - 3 × 147
      = 462 - 3 × (1071 - 2 × 462)
      = 462 - 3 × 1071 + 6 × 462
      = 7 × 462 - 3 × 1071

   ->  u = -3   and   v = 7

Checking is immediate and should be systematic: -3 × 1071 + 7 × 462 = -3213 + 3234 = 21 ✔.

Bézout's theorem

This is the most useful special case, and it is an equivalence:

a and b are COPRIME   <=>   there exist u, v with  a u + b v = 1

The forward direction follows from the identity. The converse is just as simple: if au + bv = 1, any common divisor of a and b divides 1, hence equals 1.

5 × 2 + 3 × (-3) = 10 - 9 = 1      ->  5 and 3 are coprime

This equivalence is precious: it turns a divisibility property — awkward to manipulate — into an algebraic equality that can be carried into other computations.

The major application: the modular inverse

If a and n are coprime, Bézout provides u and v with:

a u + n v = 1        hence        a u ≡ 1  (mod n)

In other words, u is the inverse of a modulo n. This is the computation that allows "division" in modular arithmetic, and it is exactly what RSA does to build the decryption key from the encryption key.

inverse of 5 modulo 3:  5 × 2 ≡ 10 ≡ 1 (mod 3)   ->  the inverse is 2

The extended Euclidean algorithm is therefore far more than a school curiosity: it is the routine your browser runs on every secure connection.

Summary

Bézout's identity: there always exist u, v with au + bv = GCD(a , b).
They are obtained by running Euclid's algorithm backwards.
The coefficients are not unique.
Bézout's theorem: a and b coprime ⟺ au + bv = 1 has a solution.
The equivalence turns divisibility into an algebraic equality.
Application: computing the modular inverse, at the heart of RSA.

Bézout's identity and theorem