6.28.9  Bézout’s Identity: egcd gcdex

Bézout’s Identity (also known as Extended Greatest Common Divisor) states that for two polynomials A(x),B(x) with greatest common divisor D(x), there exist polynomials U(x) and V(x) such that

The egcd computes the greatest common divisor of two polynomials as well as the polynomials U(x) and V(x) in the above identity.
gcdex is a synonym for egcd.

• egcd takes two mandatory arguments and one optional argument:
  • A and B, polynomials given as expressions or lists of coefficients in decreasing order.
  • Optionally, if the polynomials are expressions, x, the variable (which defaults to x).
• egcd(A,B  ⟨ ,x⟩) returns a list [U,V,D], where D is the greatest common divisor of A and B, and U and V are the polynomials from Bézout’s identity.

Examples.

• Input:
  egcd(x^2+2*x+1,x^2-1)
  Output:

  ⎡ ⎣

  1,−1,2 x+2

  ⎤ ⎦

• Input:
  egcd([1,2,1],[1,0,-1])
  Output:

  ⎡ ⎣

  ⎡ ⎣

  1

  ⎤ ⎦

  ,

  ⎡ ⎣

  −1

  ⎤ ⎦

  ,

  ⎡ ⎣

  2,2

  ⎤ ⎦

  ⎤ ⎦

• Input:
  egcd(y^2-2*y+1,y^2-y+2,y)
  Output:

  ⎡ ⎣

  y−2,−y+3,4

  ⎤ ⎦

• Input:
  egcd([1,-2,1],[1,-1,2])
  Output:

  ⎡ ⎣

  ⎡ ⎣

  1,−2

  ⎤ ⎦

  ,

  ⎡ ⎣

  −1,3

  ⎤ ⎦

  ,

  ⎡ ⎣

  4

  ⎤ ⎦

  ⎤ ⎦