suivant: Solving au+bv=c over polynomials: monter: Arithmetic and polynomials précédent: LCM of two polynomials   Table des matières   Index

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]]

giac documentation written by Renée De Graeve and Bernard Parisse