gcdex - Maple Help

gcdex

extended Euclidean algorithm for polynomials

 Calling Sequence gcdex(A, B, x, 's', 't') gcdex(A, B, C, x, 's','t')

Parameters

 A, B, C - polynomials in the variable x x - variable name s, t - (optional) unevaluated names

Description

 • If the number of parameters is less than six, gcdex applies the extended Euclidean algorithm to compute unique polynomials s, t and g in x such that $sA+tB=g$ where g is the monic GCD (Greatest Common Divisor) of A and B. The results computed satisfy $\mathrm{degree}\left(s\right)<\mathrm{degree}\left(\frac{B}{g}\right)$ and $\mathrm{degree}\left(t\right)<\mathrm{degree}\left(\frac{A}{g}\right)$. The GCD g is returned as the function value.
 • In the case of six parameters, gcdex solves the polynomial Diophantine equation $sA+tB=C$ for polynomials s and t in x. Let g be the GCD of A and B. The input polynomial C must be divisible by g. The polynomial s computed satisfies $\mathrm{degree}\left(s\right)<\mathrm{degree}\left(\frac{B}{g}\right)$. If $\mathrm{degree}\left(\frac{C}{g}\right)<\mathrm{degree}\left(\frac{A}{g}\right)+\mathrm{degree}\left(\frac{B}{g}\right)$ then the polynomial t will satisfy $\mathrm{degree}\left(t\right)<\mathrm{degree}\left(\frac{A}{g}\right)$. The NULL value is returned as the function value.
 • Note that if the input polynomials are multivariate then, in general, s and t will be rational functions in variables other than x.

Examples

 > $\mathrm{gcdex}\left({x}^{3}-1,{x}^{2}-1,x,'s','t'\right)$
 ${-}{1}{+}{x}$ (1)
 > $s,t$
 ${1}{,}{-}{x}$ (2)
 > $\mathrm{gcdex}\left({x}^{2}+a,{x}^{2}-1,{x}^{2}-a,x,'s','t'\right)$
 > $s,t$
 ${-}\frac{{-}{1}{+}{a}}{{a}{+}{1}}{,}\frac{{2}{}{a}}{{a}{+}{1}}$ (3)
 > $\mathrm{gcdex}\left(1,x,1-2x+4{x}^{2},x,'s','t'\right)$
 > $s,t$
 ${1}{,}{4}{}{x}{-}{2}$ (4)