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{\mathbb{Z}}}_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{\mathbb{Z}}}_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.

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\&comma;x\right)<\mathrm{degree}\left(b\&comma;x\right)$ and $\mathrm{degree}\left(t\&comma;x\right)<\mathrm{degree}\left(a\&comma;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 $\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 $\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}$.

$\mathrm{with}\left(\mathrm{Algebraic}\right)\&colon;$

$\mathrm{ExtendedEuclideanAlgorithm}\left(x^3+\mathrm{I}\&comma;x^5-\mathrm{I}\&comma;x\&comma;'\mathrm{s1}'\&comma;'\mathrm{t1}'\right)$

$x-\mathrm{I}$

$\left[\mathrm{s1}\&comma;\mathrm{t1}\right]$

$\left[-\mathrm{I}{x}^3-1\&comma;\mathrm{I}x\right]$

$\mathrm{expand}\left(\left(x^3+\mathrm{I}\right)\left(-x^3\mathrm{I}-1\right)+\left(x^5-\mathrm{I}\right)x\mathrm{I}\right)$

$x-\mathrm{I}$

$\mathrm{r1}≔\mathrm{RootOf}\left({\mathrm{\_Z}}^2-\mathrm{\_Z}-1\right)$

$\mathrm{r1}≔\mathrm{RootOf}\left({\mathrm{\_Z}}^2-\mathrm{\_Z}-1\right)$

$\left[\mathrm{ExtendedEuclideanAlgorithm}\left(x^2-1-\mathrm{r1}\&comma;x^3-2\mathrm{r1}-1\&comma;x\&comma;'\mathrm{s2}'\&comma;'\mathrm{t2}'\right)\&comma;\mathrm{s2}\&comma;\mathrm{t2}\right]$

$\left[x-\mathrm{RootOf}\left({\mathrm{\_Z}}^2-\mathrm{\_Z}-1\right)\&comma;x\mathrm{RootOf}\left({\mathrm{\_Z}}^2-\mathrm{\_Z}-1\right)-2x\&comma;-\mathrm{RootOf}\left({\mathrm{\_Z}}^2-\mathrm{\_Z}-1\right)+2\right]$

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

$\left[x+\sqrt{2}\&comma;\frac{\sqrt{3}}{3}\&comma;-\frac{\sqrt{3}}{3}\right]$

$\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)\&comma;x^2+\mathrm{sqrt}\left(2\right)x\&comma;x\&comma;'\mathrm{s3}'\&comma;'\mathrm{t3}'\right)\&comma;\mathrm{s3}\&comma;\mathrm{t3}\right]$

$\left[x+\sqrt{2}\&comma;\frac{\mathrm{RootOf}\left({\mathrm{\_Z}}^2-3\right)}{3}\&comma;-\frac{\mathrm{RootOf}\left({\mathrm{\_Z}}^2-3\right)}{3}\right]$

$\left[\mathrm{ExtendedEuclideanAlgorithm}\left(x^3-{\mathrm{RootOf}\left({\mathrm{\_Z}}^2-\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;\mathrm{index}=1\right)\&comma;\mathrm{index}=1\right)}^3\&comma;x^2-\mathrm{sqrt}\left(2\right)\&comma;x\&comma;'\mathrm{s4}'\&comma;'\mathrm{t4}'\right)\&comma;\mathrm{s4}\&comma;\mathrm{t4}\right]$

$\left[x-2^{\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$4$}\right.}\&comma;\frac{\sqrt{2}}{2}\&comma;-\frac{\sqrt{2}x}{2}\right]$

$\mathrm{ExtendedEuclideanAlgorithm}\left(x^2+xy+y^2+1\&comma;x+y\&comma;x\right)$

Error, (in Algebraic:-ExtendedEuclideanAlgorithm) unable to compute gcdex of multivariate polynomials

$\left[\mathrm{ExtendedEuclideanAlgorithm}\left(24\&comma;66\&comma;x\&comma;'\mathrm{s5}'\&comma;'\mathrm{t5}'\right)\&comma;\mathrm{s5}\&comma;\mathrm{t5}\right]$

$\left[1\&comma;0\&comma;\frac{1}{66}\right]$

$\left[\mathrm{igcdex}\left(24\&comma;66\&comma;'\mathrm{s5}'\&comma;'\mathrm{t5}'\right)\&comma;\mathrm{s5}\&comma;\mathrm{t5}\right]$

$\left[6\&comma;3\&comma;\mathrm{-1}\right]$

$\left[\mathrm{ExtendedEuclideanAlgorithm}\left({\sin \left(x\right)}^2+3\sin \left(x\right)+2\&comma;{\sin \left(x\right)}^2+4\sin \left(x\right)+3\&comma;\sin \left(x\right)\&comma;'\mathrm{s7}'\&comma;'\mathrm{t7}'\right)\&comma;\mathrm{s7}\&comma;\mathrm{t7}\right]$

$\left[\sin \left(x\right)+1\&comma;\mathrm{-1}\&comma;1\right]$

$\left[\mathrm{ExtendedEuclideanAlgorithm}\left(x-\tan \left(\frac{\mathrm{\pi }}{4}\right)\&comma;x+\exp \left(\mathrm{I}\mathrm{\pi }\right)\&comma;x\&comma;'\mathrm{s8}'\&comma;'\mathrm{t8}'\right)\&comma;\mathrm{s8}\&comma;\mathrm{t8}\right]$

$\left[x-1\&comma;0\&comma;1\right]$

$\mathrm{ExtendedEuclideanAlgorithm}\left(x^2-{\sin \left(y\right)}^2\&comma;x^2+2x\sin \left(y\right)+{\sin \left(y\right)}^2\&comma;x\right)$

Error, (in Algebraic:-ExtendedEuclideanAlgorithm) unable to compute gcdex of multivariate polynomials

$\mathrm{ExtendedEuclideanAlgorithm}\left(\frac{1}{x}\&comma;\frac{1}{x^2}\&comma;x\right)$

Error, (in Algebraic:-ExtendedEuclideanAlgorithm) polynom(s) in x expected

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

$\left[x+1\&comma;\frac{\mathrm{I}}{2}\&comma;-\frac{\mathrm{I}}{2}\right]$

$\mathrm{ExtendedEuclideanAlgorithm}\left(x^2-{\mathrm{RootOf}\left({\mathrm{\_Z}}^3-\mathrm{\_Z}-3\right)}^6\&comma;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\&comma;x\right)$

$x+\mathrm{RootOf}\left({\mathrm{\_Z}}^3-\mathrm{\_Z}-3\right)+3$

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

$x+\frac{\sqrt{2}}{2}$

$\mathrm{ExtendedEuclideanAlgorithm}\left(x^2-x+0.25\&comma;x-\frac{1}{2}\&comma;x\right)$

Error, (in Algebraic:-ExtendedEuclideanAlgorithm) polynom(s) with radalgnum coefficients expected

$\mathrm{ExtendedEuclideanAlgorithm}\left(x^2+2x\mathrm{sqrt}\left(x\right)\&comma;x+\mathrm{sqrt}\left(x\right)\&comma;x\right)$

Error, (in Algebraic:-ExtendedEuclideanAlgorithm) polynom(s) with radalgnum coefficients expected

$\left[\mathrm{ExtendedEuclideanAlgorithm}\left(x^2-2\&comma;x^3-\mathrm{RootOf}\left({\mathrm{\_Z}}^2-8\right)\&comma;x\&comma;'\mathrm{s10}'\&comma;'\mathrm{t10}'\right)\&comma;\mathrm{s10}\&comma;\mathrm{t10}\right]$

$\left[x-\frac{\mathrm{RootOf}\left({\mathrm{\_Z}}^2-8\right)}{2}\&comma;-\frac{x}{2}\&comma;\frac{1}{2}\right]$

$\left[\mathrm{ExtendedEuclideanAlgorithm}\left(x+\mathrm{sqrt}\left(2\right)\&comma;x+\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;\mathrm{index}=1\right)\&comma;x\&comma;'\mathrm{s11}'\&comma;'\mathrm{t11}'\right)\&comma;\mathrm{s11}\&comma;\mathrm{t11}\right]$

$\left[x+\sqrt{2}\&comma;0\&comma;1\right]$

$\left[\mathrm{ExtendedEuclideanAlgorithm}\left(x+\mathrm{sqrt}\left(2\right)\&comma;x+\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;\mathrm{index}=2\right)\&comma;x\&comma;'\mathrm{s12}'\&comma;'\mathrm{t12}'\right)\&comma;\mathrm{s12}\&comma;\mathrm{t12}\right]$

$\left[1\&comma;\frac{\sqrt{2}}{4}\&comma;-\frac{\sqrt{2}}{4}\right]$

$\mathrm{ExtendedEuclideanAlgorithm}\left(x+\mathrm{sqrt}\left(2\right)\&comma;x+\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\right)\&comma;x\right)$

Error, (in Algebraic:-ExtendedEuclideanAlgorithm) reducible RootOf detected. Substitutions are {RootOf(_Z^2-2) = -RootOf(_Z^2-2,index = 1), RootOf(_Z^2-2) = RootOf(_Z^2-2,index = 1)}

$\left[\mathrm{ExtendedEuclideanAlgorithm}\left(x+\mathrm{sqrt}\left(2\right)\&comma;x+\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\right)\&comma;x\&comma;'\mathrm{s13}'\&comma;'\mathrm{t13}'\&comma;'\mathrm{symbolic}'=\mathrm{true}\right)\&comma;\mathrm{s13}\&comma;\mathrm{t13}\right]$

$\left[1\&comma;\frac{\sqrt{2}}{4}\&comma;-\frac{\sqrt{2}}{4}\right]$

$\left[\mathrm{ExtendedEuclideanAlgorithm}\left(x^2+5\&comma;x^2+6x+2\&comma;x\&comma;'\mathrm{s14}'\&comma;'\mathrm{t14}'\&comma;'\mathrm{characteristic}'=7\right)\&comma;\mathrm{s14}\&comma;\mathrm{t14}\right]$

$\left[x+3\&comma;1\&comma;6\right]$

$\left[\mathrm{ExtendedEuclideanAlgorithm}\left(x^2+2\mathrm{sqrt}\left(5\right)x+5\&comma;x^2+6\&comma;x\&comma;'\mathrm{s15}'\&comma;'\mathrm{t15}'\&comma;'\mathrm{characteristic}'=11\right)\&comma;\mathrm{s15}\&comma;\mathrm{t15}\right]$

$\left[x+\sqrt{5}\&comma;10\sqrt{5}\&comma;\sqrt{5}\right]$

$\left[\mathrm{ExtendedEuclideanAlgorithm}\left(x^2+5x+6\&comma;x^2+3x+2\&comma;x\&comma;'\mathrm{s16}'\&comma;'\mathrm{t16}'\&comma;'\mathrm{characteristic}'=9\right)\&comma;\mathrm{s16}\&comma;\mathrm{t16}\right]$

$\left[x+2\&comma;5\&comma;4\right]$

$\mathrm{ExtendedEuclideanAlgorithm}\left(x^2+5x+6\&comma;x^2+3x+2\&comma;x\&comma;'\mathrm{characteristic}'=10\right)$

Error, (in Algebraic:-ExtendedEuclideanAlgorithm) zero divisor modulo 10 detected

$\mathrm{CubeRootOf}\left[-4\right]≔\mathrm{RootOf}\left({\mathrm{\_Z}}^3+4\&comma;\mathrm{index}=1\right)$

${\mathrm{CubeRootOf}}_{\mathrm{-4}}≔\mathrm{RootOf}\left({\mathrm{\_Z}}^3+4\&comma;\mathrm{index}=1\right)$

$\mathrm{CubeRootOf}\left[-2\right]≔\mathrm{RootOf}\left({\mathrm{\_Z}}^3+2\&comma;\mathrm{index}=1\right)$

${\mathrm{CubeRootOf}}_{\mathrm{-2}}≔\mathrm{RootOf}\left({\mathrm{\_Z}}^3+2\&comma;\mathrm{index}=1\right)$

$\mathrm{CubeRootOf}\left[2\right]≔\mathrm{RootOf}\left({\mathrm{\_Z}}^3-2\&comma;\mathrm{index}=1\right)$

${\mathrm{CubeRootOf}}_2≔\mathrm{RootOf}\left({\mathrm{\_Z}}^3-2\&comma;\mathrm{index}=1\right)$

$\mathrm{CubeRootOf}\left[3\right]≔\mathrm{RootOf}\left({\mathrm{\_Z}}^3-3\&comma;\mathrm{index}=1\right)$

${\mathrm{CubeRootOf}}_3≔\mathrm{RootOf}\left({\mathrm{\_Z}}^3-3\&comma;\mathrm{index}=1\right)$

$\mathrm{CubeRootOf}\left[4\right]≔\mathrm{RootOf}\left({\mathrm{\_Z}}^3-4\&comma;\mathrm{index}=1\right)$

${\mathrm{CubeRootOf}}_4≔\mathrm{RootOf}\left({\mathrm{\_Z}}^3-4\&comma;\mathrm{index}=1\right)$

$\mathrm{CubeRootOf}\left[6\right]≔\mathrm{RootOf}\left({\mathrm{\_Z}}^3-6\&comma;\mathrm{index}=1\right)$

${\mathrm{CubeRootOf}}_6≔\mathrm{RootOf}\left({\mathrm{\_Z}}^3-6\&comma;\mathrm{index}=1\right)$

$\mathrm{ExtendedEuclideanAlgorithm}\left(x+\mathrm{CubeRootOf}\left[4\right]\mathrm{CubeRootOf}\left[-2\right]\mathrm{CubeRootOf}\left[3\right]\&comma;x+\mathrm{CubeRootOf}\left[-4\right]\mathrm{CubeRootOf}\left[6\right]\&comma;x\right)$

Error, (in Algebraic:-ExtendedEuclideanAlgorithm) reducible RootOf detected. Substitutions are {RootOf(_Z^3+4,index = 1) = 1/2*RootOf(_Z^3-4,index = 1)^2*RootOf(_Z^3+2,index = 1), RootOf(_Z^3+4,index = 1) = RootOf(RootOf(_Z^3-4,index = 1)^2*RootOf(_Z^3+2,index = 1)*_Z-2*RootOf(_Z^3-4,index = 1)^2+2*_Z^2+4*RootOf(_Z^3+2,index = 1))}

$\mathrm{ExtendedEuclideanAlgorithm}\left(x+\mathrm{CubeRootOf}\left[4\right]\mathrm{CubeRootOf}\left[-2\right]\mathrm{CubeRootOf}\left[3\right]\&comma;x+\mathrm{CubeRootOf}\left[-4\right]\mathrm{CubeRootOf}\left[6\right]\&comma;x\&comma;'\mathrm{makeindependent}'=\mathrm{true}\right)$

$\frac{\mathrm{RootOf}\left({\mathrm{\_Z}}^3+2\&comma;\mathrm{index}=1\right)\mathrm{RootOf}\left({\mathrm{\_Z}}^3-6\&comma;\mathrm{index}=1\right){\mathrm{RootOf}\left({\mathrm{\_Z}}^3-4\&comma;\mathrm{index}=1\right)}^2}{2}+x$

$\mathrm{ExtendedEuclideanAlgorithm}\left(x+\mathrm{CubeRootOf}\left[2\right]\mathrm{CubeRootOf}\left[3\right]\&comma;x+\mathrm{CubeRootOf}\left[6\right]\&comma;x\&comma;'\mathrm{makeindependent}'=\mathrm{FAIL}\right)$

$x+\mathrm{RootOf}\left({\mathrm{\_Z}}^3-6\&comma;\mathrm{index}=1\right)$

$\mathrm{ExtendedEuclideanAlgorithm}\left(x+\mathrm{CubeRootOf}\left[2\right]\mathrm{CubeRootOf}\left[3\right]\&comma;x+\mathrm{CubeRootOf}\left[6\right]\&comma;x\&comma;'\mathrm{makeindependent}'=\mathrm{false}\right)$

Error, (in Algebraic:-ExtendedEuclideanAlgorithm) reducible RootOf detected. Substitutions are {RootOf(_Z^3-2,index = 1) = 1/3*RootOf(_Z^3-6,index = 1)*RootOf(_Z^3-3,index = 1)^2, RootOf(_Z^3-2,index = 1) = RootOf(RootOf(_Z^3-6,index = 1)*RootOf(_Z^3-3,index = 1)^2*_Z+RootOf(_Z^3-6,index = 1)^2*RootOf(_Z^3-3,index = 1)+3*_Z^2)}