The Euclidean Algorithm and Bezout’s Identity

Number Theory

In it’s simplest form Bezout’s Identity is a statement of the fact that the greatest common divisor of any two numbers can be written as a linear combination of them. Bezout’s Identity, the Euclidean Algorithm and the Chinese Remainder Theorem (a trick in number theory whereby a number is reconstructed given its remainder with respect to different bases) are core concepts in number theory and should be very familiar to any amateur mathematician. It’s hard to imagine how anyone could take thirteen pages in explaining the mechanics of how to calculate the coefficients of Bezout’s Identity, especially as we will not explore any techniques outside of the ordinary one’s of the Euclidean Algorithm.

But even though the technique is simple and effective, it does present just enough subtlety to warrant this exploration. And the development of the algorithms will give us different constructive proofs of Bezout’s Identity which are interesting in of themselves.

Theorem as Succinct Python Code: Bezout’s Identity

Let all variables be nonzero natural numbers. For a, b > d = gcd(a, b) there is a unique mapping (a, b) → (mm, nn), (m, n) with mm, m < a ÷ d and nn, n < b ÷ d such that

mm nn
ab
= d =
ab
m n

Expanding the determinants we can write this as

mm × b - nn × a = d = a × n - b × m

Proof by Python

def bezouts_mapping(a, b, /):
   if b != 0:
      q, r = divmod(a, b)
      (mm, nn), (m, n) =\
         bezouts_mapping(b, r)
      return \
         (q*m+n, n), (q*mm+nn, mm)
   else:
      return (1, -1), (0, 1)

∎

More