Previous Up Next

2.25.11  Bézout’s Identity : egcd gcdex

This function compute the polynomial coefficients of the Bézout’s Identity (also known as Extended Greatest Common Divisor). Given two polynomials A(x),B(x), egcd computes 3 polynomials U(x),V(x) and D(x) such that :

U(x)*A(x)+V(x)*B(x)=D(x)=GCD(A(x),B(x)) 

egcd takes 2 or 3 arguments: the polynomials A and B as expressions in terms of a variable, if the variable is not specified it will default to x. Alternatively, A and B may be given as list-polynomials.
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]]

Previous Up Next