Bezout's Identity

Created at: 2025-05-11

Definition

If a and b are positive integers, then there exist integers k and l such that: gcd(a, b) = ak + bl.

Examples

  gcd(12,20) = 4
  gcd(12,20) = 12k + 20l
  gcd(12,20) = 12*2 + 20*-1
  k = 2, l = -1

  gcd(12,20) = 4
  gcd(12,20) = 12k + 20l
  gcd(12,20) = 12*-3 + 20*2
  k = -3, l = 2

In fact there are infinite solutions. But only one suffices for the theorem.