ExtendedEuclideanAlgorithm - Maple Help

# Online Help

###### All Products    Maple    MapleSim

Home : Support : Online Help : Mathematics : Algebra : Algebraic Numbers : ExtendedEuclideanAlgorithm

Algebraic

 ExtendedEuclideanAlgorithm
 extended Euclidean algorithm for polynomials with algebraic number coefficients

 Calling Sequence ExtendedEuclideanAlgorithm(a, b, x, 's', 't', options) Gcdex(a, b, x, 's', 't', options)

Parameters

 a,b - polynomials in x with algebraic number coefficients x - name s, t - (optional) unevaluated names options - (optional) equation(s) of the form keyword = value, where keyword is either 'symbolic', 'makeindependent', or 'characteristic'

Options

 • If the option 'symbolic'=true is given and a RootOf whose minimal polynomial factors nontrivially is detected, ExtendedEuclideanAlgorithm will reduce it to a RootOf of lower degree by picking one of the factors arbitrarily. This will eliminate the possibility of a "reducible RootOf detected" error. The default is 'symbolic'=false.
 • If the option characteristic=p is given, where p is a nonnegative integer, the computation is performed over an extension of the ring ${\mathrm{ℤ}}_{p}$ of integers modulo p. The default is characteristic=0 and means that the gcd is computed over an extension of the rational numbers.
 • Note that if p is positive but not a prime, then ${\mathrm{ℤ}}_{p}$ is not a field, and the greatest common divisor may not exist or may not be unique.  ExtendedEuclideanAlgorithm will attempt to perform the computation anyway. If it does not succeed because it encounters an integer that has no inverse modulo p, it issues the error "zero divisor modulo p detected".
 • If the option 'makeindependent'=true is given, then ExtendedEuclideanAlgorithm will always try to find a field representation for algebraic numbers in the input, regardless of how many algebraic objects the input contains. If the input contains many RootOfs, then this can be a very expensive calculation. If 'makeindependent'=false is given, then no independence checking is performed. The default is 'makeindependent'=FAIL, in which case algebraic dependencies will only be checked for if there are $4$ or fewer algebraic objects in the input.

Description

 • The ExtendedEuclideanAlgorithm command performs the extended Euclidean algorithm on a and b, polynomials in x. It computes and returns g, the greatest common divisor (gcd) of a and b, which is a monic polynomial in x. Additionally, the parameters s and t, if included, will be assigned the values of polynomials in x such that $as+bt=g$, where $\mathrm{degree}\left(s,x\right)<\mathrm{degree}\left(b,x\right)$ and $\mathrm{degree}\left(t,x\right)<\mathrm{degree}\left(a,x\right)$.
 • The inputs a and b may contain algebraic number coefficients. These may be represented by radicals or with the RootOf notation (see type,algnum, type,radnum). In general, algebraic numbers will be returned in the same representation as they were received in. Nested radicals and RootOfs are also supported.
 • Note that ExtendedEuclideanAlgorithm cannot be used to perform the extended Euclidean algorithm on two constants, e.g., in the ring of integers. It returns $1$ for the gcd of two nonzero constants. Use the igcdex command to perform the extended Euclidean algorithm on integers.
 • The arguments a and b must be univariate polynomials in the variable x, which is typically a name. If other names or non-algebraic sub-expressions are included and they cannot be evaluated to algebraic numbers, an "unable to compute gcdex of multivariate polynomials" error will be returned.
 • x can also be a function such as $\mathrm{sin}\left(x\right)$, in which case it will be frozen and replaced by a new local variable. However, functions that are also of type AlgebraicObject such as $\mathrm{sin}\left(\frac{\mathrm{\pi }}{3}\right)$ will be converted to algebraic numbers before proceeding, so they cannot be treated as variables. Proceed with caution when using a function for x, as treating some functions as variables may produce mathematically unsound results.
 • The inputs a and b can be polynomials disguised as rational functions, in which case they are normalized first using Algebraic[Normal].
 • The output will be normalized as follows:
 – All non-constant factors in the output are monic.
 – The gcd will always be monic, and s and t will each contain at most two constant factors, only one of which may not be rational.
 – All factors that are not rational numbers have integer content equal to $1$, except possibly if there is only one non-constant factor.
 – All algebraic numbers occurring in the results are reduced modulo their minimal polynomial (see Reduce), and all arguments of functions, if any, are normalized recursively (see Normal).
 • If the set of radicals and RootOfs in the inputs cannot be embedded into a field algebraically, the greatest common divisor may not always exist or may not be unique. ExtendedEuclideanAlgorithm will try to find a field representation if there are at most $4$ algebraic objects in the input (unless option 'makeindependent' is given; see below), and otherwise attempt to perform the computation anyway. If it does not succeed, it issues the error "reducible RootOf detected", unless the option 'symbolic'=true is given (see below).
 • These functions do not support input containing floats or radical functions such as $\sqrt{x}$.

Examples

 > $\mathrm{with}\left(\mathrm{Algebraic}\right):$

Introductory examples:

 > $\mathrm{ExtendedEuclideanAlgorithm}\left({x}^{3}+I,{x}^{5}-I,x,'\mathrm{s1}','\mathrm{t1}'\right)$
 ${x}{-}{I}$ (1)
 > $\left[\mathrm{s1},\mathrm{t1}\right]$
 $\left[{-}{I}{}{{x}}^{{3}}{-}{1}{,}{I}{}{x}\right]$ (2)
 > $\mathrm{expand}\left(\left({x}^{3}+I\right)\left(-{x}^{3}I-1\right)+\left({x}^{5}-I\right)xI\right)$
 ${x}{-}{I}$ (3)
 > $\mathrm{r1}≔\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-\mathrm{_Z}-1\right)$
 ${\mathrm{r1}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{\mathrm{_Z}}{-}{1}\right)$ (4)
 > $\left[\mathrm{ExtendedEuclideanAlgorithm}\left({x}^{2}-1-\mathrm{r1},{x}^{3}-2\mathrm{r1}-1,x,'\mathrm{s2}','\mathrm{t2}'\right),\mathrm{s2},\mathrm{t2}\right]$
 $\left[{x}{-}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{\mathrm{_Z}}{-}{1}\right){,}{x}{}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{\mathrm{_Z}}{-}{1}\right){-}{2}{}{x}{,}{-}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{\mathrm{_Z}}{-}{1}\right){+}{2}\right]$ (5)

The input may contain both radicals and RootOfs, and ExtendedEuclideanAlgorithm will embed the coefficients into an algebraic field, if possible:

 > $\left[\mathrm{ExtendedEuclideanAlgorithm}\left({x}^{2}+\mathrm{sqrt}\left(2\right)x+\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-3,\mathrm{index}=1\right)x+\mathrm{sqrt}\left(6\right),{x}^{2}+\mathrm{sqrt}\left(2\right)x,x,'\mathrm{s3}','\mathrm{t3}'\right),\mathrm{s3},\mathrm{t3}\right]$
 $\left[{x}{+}\sqrt{{2}}{,}\frac{\sqrt{{3}}}{{3}}{,}{-}\frac{\sqrt{{3}}}{{3}}\right]$ (6)
 > $\left[\mathrm{ExtendedEuclideanAlgorithm}\left({x}^{2}+\mathrm{sqrt}\left(2\right)x+\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-3\right)x+\mathrm{sqrt}\left(6\right),{x}^{2}+\mathrm{sqrt}\left(2\right)x,x,'\mathrm{s3}','\mathrm{t3}'\right),\mathrm{s3},\mathrm{t3}\right]$
 $\left[{x}{+}\sqrt{{2}}{,}\frac{{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{3}\right)}{{3}}{,}{-}\frac{{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{3}\right)}{{3}}\right]$ (7)

Nested and mixed radicals and RootOfs are handled as well:

 > $\left[\mathrm{ExtendedEuclideanAlgorithm}\left({x}^{3}-{\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-2,\mathrm{index}=1\right),\mathrm{index}=1\right)}^{3},{x}^{2}-\mathrm{sqrt}\left(2\right),x,'\mathrm{s4}','\mathrm{t4}'\right),\mathrm{s4},\mathrm{t4}\right]$
 $\left[{x}{-}{{2}}^{{1}}{{4}}}{,}\frac{\sqrt{{2}}}{{2}}{,}{-}\frac{\sqrt{{2}}{}{x}}{{2}}\right]$ (8)

The input must contain univariate polynomials only.  Multiple variables are not supported and an error will be returned:

 > $\mathrm{ExtendedEuclideanAlgorithm}\left({x}^{2}+xy+{y}^{2}+1,x+y,x\right)$

This function does not perform the extended Euclidean algorithm over the integers. Use igcdex for that functionality:

 > $\left[\mathrm{ExtendedEuclideanAlgorithm}\left(24,66,x,'\mathrm{s5}','\mathrm{t5}'\right),\mathrm{s5},\mathrm{t5}\right]$
 $\left[{1}{,}{0}{,}\frac{{1}}{{66}}\right]$ (9)
 > $\left[\mathrm{igcdex}\left(24,66,'\mathrm{s5}','\mathrm{t5}'\right),\mathrm{s5},\mathrm{t5}\right]$
 $\left[{6}{,}{3}{,}{-1}\right]$ (10)

The input can also be treated as a pair of polynomials in a non-algebraic sub-expression such as $\mathrm{sin}\left(x\right)$, as it will be frozen and temporarily replaced by a new local variable:

 > $\left[\mathrm{ExtendedEuclideanAlgorithm}\left({\mathrm{sin}\left(x\right)}^{2}+3\mathrm{sin}\left(x\right)+2,{\mathrm{sin}\left(x\right)}^{2}+4\mathrm{sin}\left(x\right)+3,\mathrm{sin}\left(x\right),'\mathrm{s7}','\mathrm{t7}'\right),\mathrm{s7},\mathrm{t7}\right]$
 $\left[{\mathrm{sin}}{}\left({x}\right){+}{1}{,}{-1}{,}{1}\right]$ (11)

Other non-algebraic sub-expressions can only be included if they can be converted to algebraic numbers:

 > $\left[\mathrm{ExtendedEuclideanAlgorithm}\left(x-\mathrm{tan}\left(\frac{\mathrm{\pi }}{4}\right),x+\mathrm{exp}\left(I\mathrm{\pi }\right),x,'\mathrm{s8}','\mathrm{t8}'\right),\mathrm{s8},\mathrm{t8}\right]$
 $\left[{x}{-}{1}{,}{0}{,}{1}\right]$ (12)
 > $\mathrm{ExtendedEuclideanAlgorithm}\left({x}^{2}-{\mathrm{sin}\left(y\right)}^{2},{x}^{2}+2x\mathrm{sin}\left(y\right)+{\mathrm{sin}\left(y\right)}^{2},x\right)$

Rational functions are generally not accepted, but polynomials disguised as rational functions are allowed, because they will be simplified by Normal:

 > $\mathrm{ExtendedEuclideanAlgorithm}\left(\frac{1}{x},\frac{1}{{x}^{2}},x\right)$
 > $\left[\mathrm{ExtendedEuclideanAlgorithm}\left(\frac{{x}^{3}-{x}^{2}I-x+I}{x-1},\frac{{x}^{3}+{x}^{2}I-x-I}{x-1},x,'\mathrm{s9}','\mathrm{t9}'\right),\mathrm{s9},\mathrm{t9}\right]$
 $\left[{x}{+}{1}{,}\frac{{I}}{{2}}{,}{-}\frac{{I}}{{2}}\right]$ (13)

The output will always be fully reduced and normalized (see Reduce, Normal):

 > $\mathrm{ExtendedEuclideanAlgorithm}\left({x}^{2}-{\mathrm{RootOf}\left({\mathrm{_Z}}^{3}-\mathrm{_Z}-3\right)}^{6},{x}^{2}+6x+2\mathrm{RootOf}\left({\mathrm{_Z}}^{3}-\mathrm{_Z}-3\right)x+{\mathrm{RootOf}\left({\mathrm{_Z}}^{3}-\mathrm{_Z}-3\right)}^{6},x\right)$
 ${x}{+}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{\mathrm{_Z}}{-}{3}\right){+}{3}$ (14)

Non-algebraic sub-expressions in the input may become algebraic after being recursively normalized:

 > $\mathrm{ExtendedEuclideanAlgorithm}\left(x+\mathrm{sin}\left(\frac{\mathrm{\pi }\left(y-\mathrm{sqrt}\left(2\right)\right)}{4\left(y-\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-2,\mathrm{index}=1\right)\right)}\right),x+\frac{\mathrm{sqrt}\left(2\right)}{2},x\right)$
 ${x}{+}\frac{\sqrt{{2}}}{{2}}$ (15)

Floats are not accepted:

 > $\mathrm{ExtendedEuclideanAlgorithm}\left({x}^{2}-x+0.25,x-\frac{1}{2},x\right)$

Algebraic functions such as $\sqrt{x}$ are not accepted:

 > $\mathrm{ExtendedEuclideanAlgorithm}\left({x}^{2}+2x\mathrm{sqrt}\left(x\right),x+\mathrm{sqrt}\left(x\right),x\right)$

When non-indexed RootOfs are given in the input, often the extended Euclidean Algorithm can still be performed and the answer expressed in terms of the input:

 > $\left[\mathrm{ExtendedEuclideanAlgorithm}\left({x}^{2}-2,{x}^{3}-\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-8\right),x,'\mathrm{s10}','\mathrm{t10}'\right),\mathrm{s10},\mathrm{t10}\right]$
 $\left[{x}{-}\frac{{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{8}\right)}{{2}}{,}{-}\frac{{x}}{{2}}{,}\frac{{1}}{{2}}\right]$ (16)

However, in the following case, ExtendedEuclideanAlgorithm is unable to compute the gcd because it must know whether $\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-2\right)$ represents $\sqrt{2}$ or $-\sqrt{2}$ when no index is given. In such a case, it will return a "reducible RootOf detected" error:

 > $\left[\mathrm{ExtendedEuclideanAlgorithm}\left(x+\mathrm{sqrt}\left(2\right),x+\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-2,\mathrm{index}=1\right),x,'\mathrm{s11}','\mathrm{t11}'\right),\mathrm{s11},\mathrm{t11}\right]$
 $\left[{x}{+}\sqrt{{2}}{,}{0}{,}{1}\right]$ (17)
 > $\left[\mathrm{ExtendedEuclideanAlgorithm}\left(x+\mathrm{sqrt}\left(2\right),x+\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-2,\mathrm{index}=2\right),x,'\mathrm{s12}','\mathrm{t12}'\right),\mathrm{s12},\mathrm{t12}\right]$
 $\left[{1}{,}\frac{\sqrt{{2}}}{{4}}{,}{-}\frac{\sqrt{{2}}}{{4}}\right]$ (18)
 > $\mathrm{ExtendedEuclideanAlgorithm}\left(x+\mathrm{sqrt}\left(2\right),x+\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-2\right),x\right)$

By using option 'symbolic' = true, ExtendedEuclideanAlgorithm can be instructed to automatically select one of the possible substitutions and complete the computation.  Here, it picks $\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-2\right)=-\sqrt{2}$:

 > $\left[\mathrm{ExtendedEuclideanAlgorithm}\left(x+\mathrm{sqrt}\left(2\right),x+\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-2\right),x,'\mathrm{s13}','\mathrm{t13}','\mathrm{symbolic}'=\mathrm{true}\right),\mathrm{s13},\mathrm{t13}\right]$
 $\left[{1}{,}\frac{\sqrt{{2}}}{{4}}{,}{-}\frac{\sqrt{{2}}}{{4}}\right]$ (19)

Using option 'characteristic', the extended gcd computation can be performed over finite fields:

 > $\left[\mathrm{ExtendedEuclideanAlgorithm}\left({x}^{2}+5,{x}^{2}+6x+2,x,'\mathrm{s14}','\mathrm{t14}','\mathrm{characteristic}'=7\right),\mathrm{s14},\mathrm{t14}\right]$
 $\left[{x}{+}{3}{,}{1}{,}{6}\right]$ (20)
 > $\left[\mathrm{ExtendedEuclideanAlgorithm}\left({x}^{2}+2\mathrm{sqrt}\left(5\right)x+5,{x}^{2}+6,x,'\mathrm{s15}','\mathrm{t15}','\mathrm{characteristic}'=11\right),\mathrm{s15},\mathrm{t15}\right]$
 $\left[{x}{+}\sqrt{{5}}{,}{10}{}\sqrt{{5}}{,}\sqrt{{5}}\right]$ (21)

In composite characteristic, the gcd cannot always be computed. ExtendedEuclideanAlgorithm will return an error if it encounters a zero divisor:

 > $\left[\mathrm{ExtendedEuclideanAlgorithm}\left({x}^{2}+5x+6,{x}^{2}+3x+2,x,'\mathrm{s16}','\mathrm{t16}','\mathrm{characteristic}'=9\right),\mathrm{s16},\mathrm{t16}\right]$
 $\left[{x}{+}{2}{,}{5}{,}{4}\right]$ (22)
 > $\mathrm{ExtendedEuclideanAlgorithm}\left({x}^{2}+5x+6,{x}^{2}+3x+2,x,'\mathrm{characteristic}'=10\right)$

With option 'makeindependent'=true, the input will be checked for algebraic dependencies even if there are more than $4$ algebraic objects in the input:

 > $\mathrm{CubeRootOf}\left[-4\right]≔\mathrm{RootOf}\left({\mathrm{_Z}}^{3}+4,\mathrm{index}=1\right)$
 ${{\mathrm{CubeRootOf}}}_{{-4}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{+}{4}{,}{\mathrm{index}}{=}{1}\right)$ (23)
 > $\mathrm{CubeRootOf}\left[-2\right]≔\mathrm{RootOf}\left({\mathrm{_Z}}^{3}+2,\mathrm{index}=1\right)$
 ${{\mathrm{CubeRootOf}}}_{{-2}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{+}{2}{,}{\mathrm{index}}{=}{1}\right)$ (24)
 > $\mathrm{CubeRootOf}\left[2\right]≔\mathrm{RootOf}\left({\mathrm{_Z}}^{3}-2,\mathrm{index}=1\right)$
 ${{\mathrm{CubeRootOf}}}_{{2}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{2}{,}{\mathrm{index}}{=}{1}\right)$ (25)
 > $\mathrm{CubeRootOf}\left[3\right]≔\mathrm{RootOf}\left({\mathrm{_Z}}^{3}-3,\mathrm{index}=1\right)$
 ${{\mathrm{CubeRootOf}}}_{{3}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{3}{,}{\mathrm{index}}{=}{1}\right)$ (26)
 > $\mathrm{CubeRootOf}\left[4\right]≔\mathrm{RootOf}\left({\mathrm{_Z}}^{3}-4,\mathrm{index}=1\right)$
 ${{\mathrm{CubeRootOf}}}_{{4}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{4}{,}{\mathrm{index}}{=}{1}\right)$ (27)
 > $\mathrm{CubeRootOf}\left[6\right]≔\mathrm{RootOf}\left({\mathrm{_Z}}^{3}-6,\mathrm{index}=1\right)$
 ${{\mathrm{CubeRootOf}}}_{{6}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{6}{,}{\mathrm{index}}{=}{1}\right)$ (28)
 > $\mathrm{ExtendedEuclideanAlgorithm}\left(x+\mathrm{CubeRootOf}\left[4\right]\mathrm{CubeRootOf}\left[-2\right]\mathrm{CubeRootOf}\left[3\right],x+\mathrm{CubeRootOf}\left[-4\right]\mathrm{CubeRootOf}\left[6\right],x\right)$
 > $\mathrm{ExtendedEuclideanAlgorithm}\left(x+\mathrm{CubeRootOf}\left[4\right]\mathrm{CubeRootOf}\left[-2\right]\mathrm{CubeRootOf}\left[3\right],x+\mathrm{CubeRootOf}\left[-4\right]\mathrm{CubeRootOf}\left[6\right],x,'\mathrm{makeindependent}'=\mathrm{true}\right)$
 $\frac{{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{+}{2}{,}{\mathrm{index}}{=}{1}\right){}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{6}{,}{\mathrm{index}}{=}{1}\right){}{{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{4}{,}{\mathrm{index}}{=}{1}\right)}^{{2}}}{{2}}{+}{x}$ (29)

With option 'makeindependent'=false, the input will never be checked for algebraic dependencies:

 > $\mathrm{ExtendedEuclideanAlgorithm}\left(x+\mathrm{CubeRootOf}\left[2\right]\mathrm{CubeRootOf}\left[3\right],x+\mathrm{CubeRootOf}\left[6\right],x,'\mathrm{makeindependent}'=\mathrm{FAIL}\right)$
 ${x}{+}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{6}{,}{\mathrm{index}}{=}{1}\right)$ (30)
 > $\mathrm{ExtendedEuclideanAlgorithm}\left(x+\mathrm{CubeRootOf}\left[2\right]\mathrm{CubeRootOf}\left[3\right],x+\mathrm{CubeRootOf}\left[6\right],x,'\mathrm{makeindependent}'=\mathrm{false}\right)$

 See Also