GCD - Maple Help

Algebraic

 GreatestCommonDivisor
 gcd of polynomials with algebraic number coefficients

 Calling Sequence GreatestCommonDivisor(a, b, options) GreatestCommonDivisor(a, b, 'ca', 'cb', options) Gcd(a, b, options) Gcd(a, b, 'ca', 'cb', options)

Parameters

 a,b - polynomials with algebraic number coefficients ca,cb - names; will be assigned the cofactors 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, GreatestCommonDivisor 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 gcd is computed 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.  GreatestCommonDivisor will attempt to compute a gcd 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 GreatestCommonDivisor 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 GreatestCommonDivisor command computes the greatest common divisor of two (multivariate) polynomials whose coefficients contain radicals or RootOfs representing algebraic numbers.
 • The inputs a and b can be polynomials disguised as rational functions, in which case they are normalized first using Algebraic[Normal].
 • The inputs may even contain non-algebraic subexpressions such as $\mathrm{sin}\left(x\right)$ that are neither variables, numbers, or algebraic objects. These will be frozen and temporarily replaced by new local variables.
 • This command preserves partial factorizations in the input and expands polynomials only if necessary.
 • All non-constant factors in the gcd returned are monic with respect to a block-lexicographic ordering of the variables, where all global variables are considered larger than all local ones. If all variables have different names, then this ordering is session-independent.
 • All radicals and powers of RootOfs in the gcd returned are reduced with respect to their respective minimal polynomials.  That is, every radical is of the form ${a}^{r}$, where $0 is a rational number, and every integer exponent in a power of the form ${\mathrm{RootOf}\left(f,\mathrm{...}\right)}^{n}$ satisfies $0 .
 • Note that GreatestCommonDivisor cannot be used to compute the gcd of two constants, e.g., in the ring of integers of an algebraic number field. It returns $1$ for the gcd of two nonzero constants.
 • 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. GreatestCommonDivisor 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 compute a greatest common divisor anyway. If it does not succeed, it issues the error "reducible RootOf detected", unless the option 'symbolic'=true is given (see below).
 • If the optional arguments 'ca' and 'cb' are given, they are assigned the values of the cofactors $\frac{a}{g}$ and $\frac{b}{g}$, respectively, where $g$ is the gcd.
 • The cofactors are normalized as follows:
 – The leading coefficients, with respect to the same block-lexicographic ordering as described above, of all non-constant factors are positive integers (except possibly if there is only one non-constant factor).
 – There are at most two constant factors, and at most one of them is not a rational number.
 – All factors that are not rational numbers have integer content equal to $1$, except possibly if there is only one non-constant factor.
 – All radicals and powers of RootOfs are reduced with respect to their respective minimal polynomials, as described above.

Examples

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

Introductory examples:

 > $\mathrm{GreatestCommonDivisor}\left({x}^{5}+{y}^{5},{x}^{3}+{y}^{3}\right)$
 ${x}{+}{y}$ (1)
 > $\mathrm{GreatestCommonDivisor}\left(2{x}^{2}y+{x}^{2}-6y-3,{x}^{2}-Ixy-{3}^{\frac{1}{2}}x+I{3}^{\frac{1}{2}}y\right)$
 ${x}{-}\sqrt{{3}}$ (2)
 > $a≔\left(x+1\right)\left(x+2\right)\left(\frac{x}{\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-2,\mathrm{index}=1\right)}+1\right):$
 > $b≔{x}^{2}-2:$
 > $g≔\mathrm{GreatestCommonDivisor}\left(a,b,'\mathrm{ca}','\mathrm{cb}'\right)$
 ${g}{≔}{x}{+}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right)$ (3)
 > $\left[\mathrm{ca},\mathrm{cb}\right]$
 $\left[\frac{{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}\left({x}{+}{1}\right){}\left({x}{+}{2}\right)}{{2}}{,}{x}{-}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right)\right]$ (4)
 > $\left[\mathrm{Normal}\left(a-\mathrm{ca}g\right),\mathrm{Normal}\left(b-\mathrm{cb}g\right)\right]$
 $\left[{0}{,}{0}\right]$ (5)

Polynomials disguised as rational functions are accepted, but true rational functions are not. Neither are algebraic functions or floating point numbers in the coefficients:

 > $\mathrm{GreatestCommonDivisor}\left(\frac{{x}^{2}-2}{x+\mathrm{sqrt}\left(2\right)},{x}^{2}-2\mathrm{sqrt}\left(2\right)x+2\right)$
 ${x}{-}\sqrt{{2}}$ (6)
 > $\mathrm{GreatestCommonDivisor}\left(\frac{{x}^{2}+2}{x+\mathrm{sqrt}\left(2\right)},{x}^{2}-2\mathrm{sqrt}\left(2\right)x+2\right)$
 > $\mathrm{GreatestCommonDivisor}\left({x}^{2}-y,{x}^{2}+2\mathrm{sqrt}\left(y\right)x+y\right)$
 > $\mathrm{GreatestCommonDivisor}\left({x}^{2}-2.0,x+\mathrm{sqrt}\left(2\right)\right)$

Non-algebraic subexpressions are frozen and replaced by new variables:

 > $\mathrm{GreatestCommonDivisor}\left({x}^{2}-3{\mathrm{cos}\left(x\right)}^{2},{x}^{2}-2\mathrm{sqrt}\left(3\right)x\mathrm{cos}\left(x\right)+3{\mathrm{cos}\left(x\right)}^{2}\right)$
 ${-}{\mathrm{cos}}{}\left({x}\right){}\sqrt{{3}}{+}{x}$ (7)

Partial factorizations in the inputs are preserved:

 > $a≔\left({x}^{2}-1\right)\left({x}^{2}-2\right):$
 > $b≔\left({x}^{2}+2x+1\right){\left(x-\mathrm{sqrt}\left(2\right)\right)}^{2}:$
 > $\left[\mathrm{GreatestCommonDivisor}\left(a,b,'\mathrm{ca}','\mathrm{cb}'\right),\mathrm{ca},\mathrm{cb}\right]$
 $\left[\left({x}{+}{1}\right){}\left({x}{-}\sqrt{{2}}\right){,}\left({x}{-}{1}\right){}\left({x}{+}\sqrt{{2}}\right){,}\left({x}{+}{1}\right){}\left({x}{-}\sqrt{{2}}\right)\right]$ (8)
 > $\left[\mathrm{GreatestCommonDivisor}\left(\mathrm{expand}\left(a\right),\mathrm{expand}\left(b\right),'\mathrm{ca}','\mathrm{cb}'\right),\mathrm{ca},\mathrm{cb}\right]$
 $\left[{{x}}^{{2}}{-}\sqrt{{2}}{}{x}{+}{x}{-}\sqrt{{2}}{,}{{x}}^{{2}}{+}\sqrt{{2}}{}{x}{-}{x}{-}\sqrt{{2}}{,}{{x}}^{{2}}{-}\sqrt{{2}}{}{x}{+}{x}{-}\sqrt{{2}}\right]$ (9)

The gcd of two nonzero constants is always $1$:

 > $\mathrm{GreatestCommonDivisor}\left(1+I,{\left(1+I\right)}^{2}\right)$
 ${1}$ (10)

There is no way for GreatestCommonDivisor to know whether $\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-2\right)$ without an index represents $\sqrt{2}$ or $-\sqrt{2}$. Option 'symbolic'=true picks $-\sqrt{2}$ in this case:

 > $\mathrm{GreatestCommonDivisor}\left(x-\mathrm{sqrt}\left(2\right),x-\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-2,\mathrm{index}=1\right)\right)$
 ${x}{-}\sqrt{{2}}$ (11)
 > $\mathrm{GreatestCommonDivisor}\left(x-\mathrm{sqrt}\left(2\right),x-\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-2\right)\right)$
 > $\mathrm{GreatestCommonDivisor}\left(x-\mathrm{sqrt}\left(2\right),x-\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-2\right),'\mathrm{symbolic}'=\mathrm{true}\right)$
 ${1}$ (12)

An example where the gcd can be computed even though there is a non-indexed reducible RootOf:

 > $\mathrm{GreatestCommonDivisor}\left({x}^{2}-1,{x}^{2}+2\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-1\right)x+1\right)$
 ${x}{+}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{1}\right)$ (13)
 > $\mathrm{GreatestCommonDivisor}\left({x}^{2}-1,{x}^{2}+2\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-1,\mathrm{index}=2\right)x+1\right)$
 ${x}{-}{1}$ (14)

Using option 'characteristic', gcds over finite fields can be computed:

 > $\mathrm{GreatestCommonDivisor}\left({x}^{2}+1,{x}^{2}+x,'\mathrm{characteristic}'=2\right)$
 ${x}{+}{1}$ (15)
 > $\mathrm{GreatestCommonDivisor}\left({x}^{2}-6,{x}^{2}+2Ix-1\right)$
 ${1}$ (16)
 > $\mathrm{GreatestCommonDivisor}\left({x}^{2}-6,{x}^{2}+2Ix-1,'\mathrm{characteristic}'=7\right)$
 ${x}{+}{I}$ (17)

In contrast to characteristic $0$, the complex number $I$, radicals, and indexed RootOfs are not uniquely defined in positive characteristic, and they are treated as if they were non-indexed RootOfs:

 > $\mathrm{GreatestCommonDivisor}\left(x-2,x-I,'\mathrm{characteristic}'='5'\right)$
 > $\mathrm{GreatestCommonDivisor}\left(x-2,x-I,'\mathrm{characteristic}'='5','\mathrm{symbolic}'='\mathrm{true}'\right)$
 ${1}$ (18)

The gcd cannot always be computed in composite characteristic:

 > $\mathrm{GreatestCommonDivisor}\left({x}^{2}+1,{x}^{2}+9x+8,'\mathrm{characteristic}'=65\right)$
 ${x}{+}{8}$ (19)
 > $\mathrm{GreatestCommonDivisor}\left({x}^{2}+1,{x}^{2}-4,'\mathrm{characteristic}'=65\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)$ (20)
 > $\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)$ (21)
 > $\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)$ (22)
 > $\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)$ (23)
 > $\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)$ (24)
 > $\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)$ (25)
 > $\mathrm{GreatestCommonDivisor}\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]\right)$
 > $\mathrm{GreatestCommonDivisor}\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],'\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}$ (26)

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

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