### 11.2.8 Bézout’s identity

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

U(x)A(x)+V(x)B(x)=D(x).

The egcd or gcdex command computes the greatest common divisor of two polynomials as well as the polynomials U(x) and V(x) in the above identity.

- 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

egcd(x^2+2*x+1,x^2-1)

| ⎡ ⎣ | 1,−1,2 x+2 | ⎤ ⎦

egcd([1,2,1],[1,0,-1])

| ⎡ ⎣ | ⎡ ⎣ | 1 | ⎤ ⎦ | , | ⎡ ⎣ | −1 | ⎤ ⎦ | , | ⎡ ⎣ | 2,2 | ⎤ ⎦ | ⎤ ⎦

egcd(y^2-2*y+1,y^2-y+2,y)

| ⎡ ⎣ | y−2,−y+3,4 | ⎤ ⎦

egcd([1,-2,1],[1,-1,2])

| ⎡ ⎣ | ⎡ ⎣ | 1,−2 | ⎤ ⎦ | , | ⎡ ⎣ | −1,3 | ⎤ ⎦ | , | ⎡ ⎣ | 4 | ⎤ ⎦ | ⎤ ⎦