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
|
| ⎡
⎣ | ⎡
⎣ | 1 | ⎤
⎦ | , | ⎡
⎣ | −1 | ⎤
⎦ | , | ⎡
⎣ | 2,2 | ⎤
⎦ | ⎤
⎦ |
| | | | | | | | | | |
|
egcd(y^2-2*y+1,y^2-y+2,y) |
|
| ⎡
⎣ | ⎡
⎣ | 1,−2 | ⎤
⎦ | , | ⎡
⎣ | −1,3 | ⎤
⎦ | , | ⎡
⎣ | 4 | ⎤
⎦ | ⎤
⎦ |
| | | | | | | | | | |
|